首页 > 代码库 > 【leetcode】Sudoku Solver
【leetcode】Sudoku Solver
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.
采用回溯法，利用递归实现
如果当前的元素满足数独条件，则继续判断下一个元素。
如果当前的元素不满足数独条件，则返回，递归回溯到上一个元素继续查找
由于肯定有解，所以在判断的时候可以不必使用hash表，直接判断其他位置的元素与当前要判断的元素是否相等就可以了。
1 class Solution { 2 public: 3 4 bool isValid(vector<vector<char> > &board,int i0,int j0) 5 { 6 char target=board[i0][j0]; 7 8 for(int i=0;i<9;i++) 9 {10 if(i==i0) continue;11 if(board[i][j0]==target)12 {13 return false;14 }15 }16 17 18 for(int j=0;j<9;j++)19 {20 if(j==j0) continue;21 if(board[i0][j]==target)22 {23 return false;24 }25 }26 27 for(int i=i0/3*3;i<i0/3*3+3;i++)28 {29 30 for(int j=j0/3*3;j<j0/3*3+3;j++)31 {32 if(i==i0&&j==j0) continue;33 if(board[i][j]==target)34 {35 return false;36 }37 }38 }39 40 return true;41 }42 43 44 bool scanPos(vector<vector<char> > &board,int pos)45 {46 if(pos==81) return true;47 48 49 bool flag=false;50 int i0=pos/9;51 int j0=pos%9;52 53 if(board[i0][j0]!=‘.‘)54 {55 return scanPos(board,pos+1);56 }57 58 for(int j=1;j<=9;j++)59 {60 61 board[i0][j0]=‘0‘+j;62 if(isValid(board,i0,j0))63 {64 if(scanPos(board,pos+1))65 {66 flag=true;67 break;68 }69 }70 }71 72 if(flag==false)73 {74 board[i0][j0]=‘.‘;75 return false;76 }77 else78 {79 return true;80 }81 }82 83 84 void solveSudoku(vector<vector<char> > &board) {85 scanPos(board,0);86 }87 };
【leetcode】Sudoku Solver
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。