# 37 - Sudoku Solver

解法一 - Backtracking

這題要直接想出來也有點不容易，可以學習花花醬影片裡面的剪枝技巧，主要概念是：

1. 儲存目前各 row, col, box 裡面已經有的數字

2. 一旦遇到重複就往回走，而不用一一枚舉（概念跟 # 52 - N-Queens II 的解法二很像，而 # 51 - N-Queens 的解法一 就是沒有剪枝的版本）

有一個小巧思的地方是如何判斷 (x,y) 落在哪一個 box 裡，公式 = $(y/3)*3 + x/3$

實作如下：

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        rows = vector<vector<int>>(9, vector<int>(10));
        cols = vector<vector<int>>(9, vector<int>(10));
        boxes = vector<vector<int>>(9, vector<int>(10));

        for(int i = 0; i < 9; i++)
            for(int j = 0; j < 9; j++) {
                const char c = board[i][j];                
                if ( c != '.') {
                    int n = c - '0';                    
                    int bx = j / 3;
                    int by = i / 3;
                    rows[i][n] = 1;
                    cols[j][n] = 1;
                    boxes[by * 3 + bx][n] = 1;
                }
            }

        fill(board, 0, 0);
    }

private:
    vector<vector<int>> rows, cols, boxes;

    bool fill(vector<vector<char>>& board, int x, int y) {
        if (y == 9)
            return true;

        int nx = (x + 1) % 9;
        int ny = (nx == 0) ? y + 1 : y;

        if (board[y][x] != '.') return fill(board, nx, ny);

        for (int i = 1; i <= 9; i++) {
            int bx = x / 3;
            int by = y / 3;
            int box_key = by * 3 + bx;
            if (!rows[y][i] && !cols[x][i] && !boxes[box_key][i]) {
                rows[y][i] = 1;
                cols[x][i] = 1;
                boxes[box_key][i] = 1;
                board[y][x] = i + '0';
                if (fill(board, nx, ny)) return true;
                board[y][x] = '.';
                boxes[box_key][i] = 0;
                cols[x][i] = 0;
                rows[y][i] = 0;
            }
        }
        return false;
    }
};