[LeetCode] Valid Sudoku, Sudoku Solver

Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

思路：Valid Sudoku

依次检查每一行、每一列以及每一个九宫格的数字元素是否在1-9之间，并且是否没有重复。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

class Solution { public: bool isValidSudoku(vector<vector<char> > &board) { if(board.size()!=9 || board[0].size()!=9) return false; // check row for(int i=0; i<9; i++) { vector<bool> used(9,false); for(int j=0; j<9; j++) { if(!isdigit(board[i][j])) continue; int k = board[i][j]-'0'; if(k==0 || used[k-1]) return false; used[k-1] = true; } } //check col for(int j=0; j<9; j++) { vector<bool> used(9,false); for(int i=0; i<9; i++) { if(!isdigit(board[i][j])) continue; int k = board[i][j]-'0'; if(k==0 || used[k-1]) return false; used[k-1] = true; } } // check subbox for(int i=0; i<3; i++) { for(int j=0; j<3; j++) { int row = 3*i; int col = 3*j; vector<bool> used(9,false); for(int m=row; m<row+3; m++) { for(int n=col; n<col+3; n++) { if(!isdigit(board[m][n])) continue; int k = board[m][n]-'0'; if(k==0 || used[k-1]) return false; used[k-1]=true; } } } } return true; } };

思路：Sudoku Solver

和N-Queen思路基本一样。对每个需要填充的位置枚举1-9，对每个枚举判断是否符合所在行、列、九宫格。如果符合则进行下一层递归。终止条件为填写完了整个棋盘。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

class Solution { public: void solveSudoku(vector<vector<char> > &board) { if(board.size()<9 || board[0].size()<9) return; bool findSol = solSudoku(board, 0, 0); } bool solSudoku(vector<vector<char>> &board, int irow, int icol) { if(irow==9) return true; int irow2, icol2; if(icol==8) { irow2 = irow+1; icol2 = 0; } else { irow2 = irow; icol2 = icol+1; } if(board[irow][icol]!='.') { if(!isValid(board, irow, icol)) return false; return solSudoku(board, irow2, icol2); } for(int i=1; i<=9; i++) { board[irow][icol] = '0'+i; if(isValid(board, irow, icol) && solSudoku(board, irow2, icol2)) return true; } // reset grid board[irow][icol] = '.'; return false; } bool isValid(vector<vector<char>> &board, int irow, int icol) { char val = board[irow][icol]; if(val-'0'<1 || val-'0'>9) return false; // check row & col for(int i=0; i<9; i++) { if(board[irow][i]==val && i!=icol) return false; if(board[i][icol]==val && i!=irow) return false; } //check 3x3 box int irow0 = irow/3*3; int icol0 = icol/3*3; for(int i=irow0; i<irow0+3; i++) { for(int j=icol0; j<icol0+3; j++) { if(board[i][j]==val && (i!=irow || j!=icol)) return false; } } return true; } };