// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem37.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=37 lang=cpp
 *
 * [37] 解数独
 */

// @lc code=start
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        backtrack(board, 0, 0);
    }
    bool isValid(vector<vector<char>>& board, int r, int c, char n) {
        for (int i = 0; i < 9; ++i) {
            if (board[r][i] == n) return false;
            if (board[i][c] == n) return false;
            if (board[(r/3)*3 + i / 3][(c/3)*3 + i % 3] == n) return false;
        }
        return true;
    }
    bool backtrack(vector<vector<char>>& board, int i, int j) {
        if (j == 9) return backtrack(board, i + 1, 0);
        if (i == 9) return true;
        if(board[i][j] != '.') return backtrack(board, i, j + 1);
        for (char ch = '1'; ch <= '9'; ++ch) {
            if (!isValid(board, i, j, ch)) continue;
            board[i][j] = ch;
            if (backtrack(board, i, j + 1)) return true;
            board[i][j] = '.';
        }
        return false;
    }
};
// @lc code=end