/*
 * @lc app=leetcode.cn id=37 lang=cpp
 *
 * [37] 解数独
 */
#include <bits/stdc++.h>
using namespace std;
// @lc code=start

void print(const vector<vector<char>>& board) {
  for (int i = 0; i < 9; ++i) {
    for (int j = 0; j < 9; ++j) {
      cout << board[i][j] << ",";
    }
    cout << endl;
  }
}

class Solution {
 public:
  void solveSudoku(vector<vector<char>>& board) {
    // 需要求解的位置坐标，最长81
    vector<pair<int, int>> empty;
    for (int i = 0; i < 9; ++i) {
      for (int j = 0; j < 9; ++j) {
        if (board[i][j] == '.') {
          empty.emplace_back(i, j);
        }
      }
    }
    int n = empty.size();
    // 检查一个位置合法性，无递归，空间O(m)，m==9
    function<bool(int, int)> vaild = [&](int i, int j) -> bool {
      array<int, 9> exist1 = {0, 0, 0, 0, 0, 0, 0, 0, 0};
      array<int, 9> exist2 = {0, 0, 0, 0, 0, 0, 0, 0, 0};
      array<int, 9> exist3 = {0, 0, 0, 0, 0, 0, 0, 0, 0};
      for (int k = 0; k < 9; ++k) {
        if (board[i][k] != '.') {
          if (exist1[board[i][k] - '1']) {
            return false;
          }
          exist1[board[i][k] - '1'] = 1;
        }
        if (board[k][j] != '.') {
          if (exist2[board[k][j] - '1']) {
            return false;
          }
          exist2[board[k][j] - '1'] = 1;
        }
      }
      int r = i / 3 * 3;
      int c = j / 3 * 3;
      for (int k = 0; k < 3; ++k) {
        for (int l = 0; l < 3; ++l) {
          if (board[r + k][c + l] != '.') {
            if (exist3[board[r + k][c + l] - '1']) {
              return false;
            }
            exist3[board[r + k][c + l] - '1'] = 1;
          }
        }
      }
      return true;
    };
    // 递归回溯求解，内存O(1)，调用深度最多n(n<=81)
    function<void(int)> f = [&](int i) {
      if (i == n) {
        throw exception();
      }
      for (int j = 0; j < 9; ++j) {
        board[empty[i].first][empty[i].second] = j + '1';
        if (vaild(empty[i].first, empty[i].second)) {
          f(i + 1);
        }
        board[empty[i].first][empty[i].second] = '.';
      }
    };
    try {
      f(0);
    } catch (const exception& e) {
    }
    // cant be solved
  }
};
// @lc code=end
int main() {
  Solution s;
  vector<vector<char>> b = {{'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'}};
  s.solveSudoku(b);
  print(b);
}