題目在問什麼

給一個 9 x 9 的 Sudoku 棋盤，判斷目前填入的數字是否合法。

只需要檢查已填入的位置是否違規，不需要判斷這盤 Sudoku 能不能解出來。

合法條件有三個：

  1. 每一行不能有重複數字
  2. 每一列不能有重複數字
  3. 每個 3 x 3 子區塊不能有重複數字

例子

Input: board = valid sudoku board
Output: true

解題思路

這題本質上就是重複檢查，所以 HashSet 很適合。

整體分成兩部分：

  • 檢查每一行與每一列
  • 檢查 9 個 3 x 3 子區塊

只要某個數字在同一個檢查範圍內重複出現，就立即回傳 false。

行列檢查

外層迴圈固定一個索引 i：

  • board[i][j] 代表第 i 行
  • board[j][i] 代表第 i 列

每一輪都建立新的 row set 和 col set，掃完該行與該列即可。

子區塊檢查

Sudoku 共有 9 個 3 x 3 區塊。

可以用兩層迴圈跑 0..2：

  • i 決定區塊列
  • j 決定區塊行

再用：

  • boxStartX = 3 * i
  • boxStartY = 3 * j

去算出當前子區塊左上角，之後把那個 3 x 3 範圍掃完即可。

示意圖

代碼

public class Solution
{
    public bool IsValidSudoku(char[][] board)
    {
        for (int i = 0; i < board.Length; i++)
        {
            HashSet<char> rowHash = new HashSet<char>();
            HashSet<char> colHash = new HashSet<char>();

            for (int j = 0; j < board[0].Length; j++)
            {
                if (board[i][j] != '.' && !rowHash.Add(board[i][j])) { return false; }
                if (board[j][i] != '.' && !colHash.Add(board[j][i])) { return false; }
            }
        }

        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                HashSet<char> boxHash = new HashSet<char>();

                int boxStartX = 3 * i;
                int boxEndX = boxStartX + 3;
                int boxStartY = 3 * j;
                int boxEndY = boxStartY + 3;

                for (int bx = boxStartX; bx < boxEndX; bx++)
                {
                    for (int by = boxStartY; by < boxEndY; by++)
                    {
                        if (board[bx][by] != '.' && !boxHash.Add(board[bx][by])) { return false; }
                    }
                }
            }
        }

        return true;
    }
}

複雜度

因為棋盤大小固定是 9 x 9，嚴格來說這題可以視為常數時間。

  • 時間複雜度：O(1)
  • 空間複雜度：O(1)

這題先記住的重點

  • Sudoku 驗證題的核心就是三種範圍的重複檢查
  • 行、列、子區塊都可以各自用 HashSet 處理
  • 題目只問「目前是否合法」，不是問「能不能解」