首页 > 代码库 > Sudoku Solver
Sudoku Solver
就是回溯吧。。
class Solution {public: void solveSudoku(vector<vector<char> > &board) { huisu(0,0,board); } bool huisu(int row,int col ,vector<vector<char> > &board ){ if(board[row][col]!=‘.‘)//如果不是.的话,说明不需要赋值 { if(row==8&&col==8) {return true;}//如果到了最后一个点,返回true; else if(col==8)//如果到了第八列,则移上新的一行, { return huisu(row+1,0,board); } else { return huisu(row,col+1,board); } } else//如果是.的话,说明需要赋值。 { for(int i=1;i<=9;i++) { board[row][col]=‘0‘+i; if(isValidSudoku(board,col,row))//如果合格的话 { if(row==8&&col==8) {return true ;} else if(col==8) { if(huisu(row+1,0,board)) {return true;} else { board[row][col]=‘.‘;continue;} } else { if(huisu(row,col+1,board)) return true; else { board[row][col]=‘.‘;continue;} } } else { board[row][col]=‘.‘;} } } return false; } bool isValidSudoku(vector<vector<char> > &board, int x, int y) { int row, col; for (row = 0; row < 9; ++row) { if ((x != row) && (board[row][y] == board[x][y])) { return false; } } for (col = 0; col < 9; ++col) { if ((y != col) && (board[x][col] == board[x][y])) { return false; } } for (row = (x / 3) * 3; row < (x / 3 + 1) * 3; ++row) { for (col = (y / 3) * 3; col < (y / 3 + 1) * 3; ++col) { if ((x != row) && (y != col) && (board[row][col] == board[x][y])) { return false; } } } return true; }};
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。