## Tuesday, November 18, 2014

### [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.

 ``` 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 > &board) { if(board.size()!=9 || board[0].size()!=9) return false; // check row for(int i=0; i<9; i++) { vector 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 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 used(9,false); for(int m=row; m

 ``` 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 > &board) { if(board.size()<9 || board[0].size()<9) return; bool findSol = solSudoku(board, 0, 0); } bool solSudoku(vector> &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> &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