Leetcode#37 Sudoku Solver

原題アドレス
 
さかのぼると,何も言うことはない.
 

 1 bool row[9][9];

 2 bool col[9][9];

 3 bool grid[9][9];

 4 bool mark[9][9];

 5 

 6 bool solve(vector<vector<char> > &board, int r, int c) {

 7   if (r == 9)

 8     return true;

 9   if (mark[r][c])

10     return solve(board, r + (c + 1) / 9, (c + 1) % 9);

11   for (int i = 0; i < 9; i++) {

12     if (!row[r][i] && !col[c][i] && !grid[(r / 3) * 3 + c / 3][i]) {

13       row[r][i] = col[c][i] = grid[(r / 3) * 3 + c / 3][i] = true;

14       board[r][c] = i + '1';

15       if (solve(board, r + (c + 1) / 9, (c + 1) % 9))

16         return true;

17       board[r][c] = '.';

18       row[r][i] = col[c][i] = grid[(r / 3) * 3 + c / 3][i] = false;

19     }

20   }

21 

22   return false;

23 }

24 

25 void solveSudoku(vector<vector<char> > &board) {

26   memset(row, 9 * 9 * sizeof(bool), false);

27   memset(col, 9 * 9 * sizeof(bool), false);

28   memset(grid, 9 * 9 * sizeof(bool), false);

29   memset(mark, 9 * 9 * sizeof(bool), false);

30 

31   for (int r = 0; r < 9; r++)

32     for (int c = 0; c < 9; c++)

33       if (board[r][c] != '.') {

34         row[r][board[r][c] - '1']

35           = col[c][board[r][c] - '1']

36           = grid[(r / 3) * 3 + c / 3][board[r][c] - '1']

37           = mark[r][c]

38           = true;

39       }

40 

41   solve(board, 0, 0);

42 }