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.
Solution: backtracking.
class Solution { public: const int SIZE = 9; bool isCollision(int& hashmap, char val){ if(isdigit(val)){ int digit = val-'0'; if((hashmap & (1<<digit)) ==0) hashmap |= (1<<digit); else return true; } return false; } bool isValid(vector<vector<char> > &board, int x, int y){ if(x>=SIZE || y>=SIZE || x<0 || y<0) return false; //the x-th row has any number in [1-9] occuring just once int hashmap = 0; for(int i=0; i<SIZE; ++i) if(isCollision(hashmap, board[x][i])) return false; //the y-th col has any number in [1-9] occuring just once hashmap = 0; for(int i=0; i<SIZE; ++i) if(isCollision(hashmap, board[i][y])) return false; //the subbox containing (x,y) has any number in [1-9] occuring just once hashmap = 0; x = x/3; y = y/3; //locate the subbox for(int i=0; i<3; ++i) for(int j=0; j<3; ++j){ int X = x*3+i, Y = y*3+j; if(X>=0 && X<SIZE && Y>=0 && Y<SIZE){ if(isCollision(hashmap, board[X][Y])) return false; } } return true; } bool solveSudoKuHelper(vector<vector<char> > &board, int x, int y){ if(x>=SIZE || y>=SIZE) return true; if(board[x][y]!='.'){ if(solveSudoKuHelper(board, x+(y+1)/SIZE, (y+1)%SIZE)) //all the rest empty cells can be filled out successfully return true; return false; } else{ for(int i=0; i<SIZE; ++i){ board[x][y] = '1'+i; if(isValid(board, x, y) && solveSudoKuHelper(board, x+(y+1)/SIZE, (y+1)%SIZE)) //the current cell and all the rest empty cells can be filled out successfully return true; } board[x][y] = '.'; return false; } } void solveSudoku(vector<vector<char> > &board) { // Note: The Solution object is instantiated only once and is reused by each test case. solveSudoKuHelper(board, 0, 0); } };
No comments:
Post a Comment