# 37. Sudoku Solver

題目：<https://leetcode.com/problems/sudoku-solver/>

解法：使用set紀錄出現的數字，一格一格嘗試每個數字是否符合規則，如果符合就去找下一格，若不符合就往回前一個繼續嘗試其他數字，直到所有格子都填完。

Python3：

class Solution:
    def solveSudoku(self, board: list[list[str]]) -> None:
        def backtrack(step):
            nonlocal isSolved
            if step == 81:
                isSolved = True
                return
            x = step // 9
            y = step % 9
            box = x // 3 * 3 + y // 3
            if board[x][y] != ".":
                backtrack(step + 1)
            else:
                for num in range(1, 10):
                    if isSolved == False \
                            and num not in rowCheck[x] \
                            and num not in colCheck[y] \
                            and num not in boxCheck[box]:
                        rowCheck[x].add(num)
                        colCheck[y].add(num)
                        boxCheck[box].add(num)
                        board[x][y] = str(num)
                        backtrack(step + 1)
                        if isSolved == False:
                            rowCheck[x].remove(num)
                            colCheck[y].remove(num)
                            boxCheck[box].remove(num)
                            board[x][y] = '.'
        
        rowCheck = [set() for _ in range(9)]
        colCheck = [set() for _ in range(9)]
        boxCheck = [set() for _ in range(9)]
        
        for x in range(9):
            for y in range(9):
                if board[x][y] != ".":
                    val = int(board[x][y])
                    rowCheck[x].add(val)
                    colCheck[y].add(val)
                    box = x // 3 * 3 + y // 3
                    boxCheck[box].add(val)
                    
        isSolved = False
        backtrack(0)

if __name__ == '__main__':
    board = [["5","3",".",".","7",".",".",".","."],
             ["6",".",".","1","9","5",".",".","."],
             [".","9","8",".",".",".",".","6","."],
             ["8",".",".",".","6",".",".",".","3"],
             ["4",".",".","8",".","3",".",".","1"],
             ["7",".",".",".","2",".",".",".","6"],
             [".","6",".",".",".",".","2","8","."],
             [".",".",".","4","1","9",".",".","5"],
             [".",".",".",".","8",".",".","7","9"]]

    Solution().solveSudoku(board)
    print(board)

C：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

void solveSudoku(char** board, int boardSize, int* boardColSize) {
    bool isSolved = false;
    
    int rowCheck[9][10] = {}, colCheck[9][10] = {}, boxCheck[9][10] = {};
    for (int x = 0; x < 9; x++) {
        for (int y = 0; y < 9; y++) {
            if (board[x][y] != '.') {
                int val = board[x][y] - '0';
                rowCheck[x][val] = 1;
                colCheck[y][val] = 1;
                int box = x / 3 * 3 + y / 3;
                boxCheck[box][val] = 1;
            }
        }
    }
    
    void backtrack(int step) {
        if (step == 81) {
            isSolved = true;
            return;
        }
        
        int x = step / 9, y = step % 9, box = x / 3 * 3 + y / 3;
        if (board[x][y] != '.')
            backtrack(step + 1);
        else {
            for (int num = 1; num < 10; num++) {
                if (isSolved == false && rowCheck[x][num] == 0
                        && colCheck[y][num] == 0 && boxCheck[box][num] == 0) {
                    rowCheck[x][num] = 1;
                    colCheck[y][num] = 1;
                    boxCheck[box][num] = 1;
                    board[x][y] = num + '0';
                    backtrack(step + 1);
                    if (isSolved == false) {
                        rowCheck[x][num] = 0;
                        colCheck[y][num] = 0;
                        boxCheck[box][num] = 0;
                        board[x][y] = '.';
                    }
                }
            }
        }
    }
    
    backtrack(0);
    return;
}

int main()
{
    char data[9][9] = {{'5','3','.','.','7','.','.','.','.'},
                        {'6','.','.','1','9','5','.','.','.'},
                        {'.','9','8','.','.','.','.','6','.'},
                        {'8','.','.','.','6','.','.','.','3'},
                        {'4','.','.','8','.','3','.','.','1'},
                        {'7','.','.','.','2','.','.','.','6'},
                        {'.','6','.','.','.','.','2','8','.'},
                        {'.','.','.','4','1','9','.','.','5'},
                        {'.','.','.','.','8','.','.','7','9'}};
    int boardSize = 9;
    int * boardColSize = (int*)malloc(sizeof(int) * boardSize);
    char ** board = (char**)malloc(sizeof(char*) * boardSize);
    for (int i = 0; i < boardSize; i++) {
        boardColSize[i] = 9;
        board[i] = (char*)malloc(sizeof(char) * boardColSize[i]);
        for (int j = 0; j < boardColSize[i]; j++)
            board[i][j] = data[i][j];
    }
    
    solveSudoku(board, boardSize, boardColSize);
    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < boardColSize[i]; j++)
            printf("%c", board[i][j]);
        printf("\n");
    }
    return 0;
}

###### tags: `leetcode` `backtracking`