37. Sudoku Solver
Hard
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits
1-9
must occur exactly once in each row. - Each of the digits
1-9
must occur exactly once in each column. - Each of the digits
1-9
must occur exactly once in each of the 93x3
sub-boxes of the grid.
The '.'
character indicates empty cells.
Example 1:
Input: board = [["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"]] Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]] Explanation: The input board is shown above and the only valid solution is shown below:
Constraints:
board.length == 9
board[i].length == 9
board[i][j]
is a digit or'.'
.- It is guaranteed that the input board has only one solution.
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 | class Solution { void update(int n, int i, int j, int k, vector<int> &mr, vector<int> &mc, vector<int> &mb){ int mask = 1<<n; mr[i] ^= mask; mc[j] ^= mask; mb[k] ^= mask; } bool valid(int n, int i, int j, int k, vector<int> &mr, vector<int> &mc, vector<int> &mb){ int mask = 1<<n; return (((mr[i]&mask)==0) && ((mc[j]&mask)==0) && ((mb[k]&mask)==0)); } public: bool bt(vector<vector<char> > &board, int N, vector<int> &mr, vector<int> &mc, vector<int> &mb){ if(N==81) return true; for(int i=N/9; i<9; ++i){ for(int j=N%9; j<9; ++j){ int k = i/3*3+j/3; if(board[i][j]!='.'){ return bt(board, i*9+j+1, mr, mc, mb); }else{ for(int c=1; c<=9; ++c){ if(valid(c, i, j, k, mr, mc, mb)){ update(c, i, j, k, mr, mc, mb); board[i][j]=('0'+c); if(bt(board, i*9+j+1, mr, mc, mb)) return true; update(c, i, j, k, mr, mc, mb); board[i][j]='.'; } } return false; } } } return false; } void solveSudoku(vector<vector<char> > &board) { vector<int> mr(9, 0); vector<int> mc(9, 0); vector<int> mb(9, 0); for(int i=0; i<9; ++i){ for(int j=0; j<9; ++j){ int k = i/3*3+j/3; if(board[i][j]!='.'){ int n = board[i][j]-'0'; update(n, i, j, k, mr, mc, mb); } } } bt(board, 0, mr, mc, mb); } }; class Solution { public: void solveSudoku(vector<vector<char>>& board) { int row[9][10] = {0}; int col[9][10] = {0}; int blk[9][10] = {0}; for(int pos=0; pos<81; ++pos){ int i = pos/9, j = pos%9, k = i/3*3+j/3; if(board[i][j]!='.'){ int v = board[i][j]-'0'; row[i][v]=1; col[j][v]=1; blk[k][v]=1; } } bt(board, 0, row, col, blk); } bool bt(vector<vector<char>>&board, int pos, int row[][10], int col[][10], int blk[][10]){ if(pos==81) return true; else{ int i = pos/9, j = pos%9, k = i/3*3+j/3; if(board[i][j]=='.'){ for(int v = 1; v<=9; ++v){ if(row[i][v]==0 && col[j][v]==0 && blk[k][v]==0){ row[i][v]=1; col[j][v]=1; blk[k][v]=1; board[i][j] = char('0'+v); if(bt(board, pos+1, row, col, blk)) return true; row[i][v]=0; col[j][v]=0; blk[k][v]=0; board[i][j] = '.'; } } }else{ return bt(board, pos+1, row, col, blk); } } return false; } }; |
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 | class Solution { Set<Integer>[] setsR = new HashSet[9]; Set<Integer>[] setsC = new HashSet[9]; Set<Integer>[] setsB = new HashSet[9]; public void solveSudoku(char[][] board) { for(int i=0; i<9; ++i){ setsR[i] = new HashSet<>(); setsC[i] = new HashSet<>(); setsB[i] = new HashSet<>(); } for(int i=0; i<9; ++i){ for(int j=0; j<9; ++j){ if(board[i][j]!='.'){ int k = board[i][j]-'0'; setsR[i].add(k); setsC[j].add(k); setsB[i/3*3 + j/3].add(k); } } } dfs(board, 0, 0); } boolean dfs(char[][] board, int i0, int j0){ if(i0==9) return true; if(j0==9) return dfs(board, i0+1, 0); if(board[i0][j0]!='.') return dfs(board, i0, j0+1); for(int k=1; k<=9; ++k){ if(setsR[i0].contains(k)) continue; if(setsC[j0].contains(k)) continue; if(setsB[i0/3*3 + j0/3].contains(k)) continue; setsR[i0].add(k); setsC[j0].add(k); setsB[i0/3*3 + j0/3].add(k); board[i0][j0] = (char)(k+'0'); if(dfs(board, i0, j0+1)) return true; board[i0][j0] = '.'; setsR[i0].remove(k); setsC[j0].remove(k); setsB[i0/3*3 + j0/3].remove(k); } return false; } } |
No comments:
Post a Comment