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.
Hide Tags
这题是解数独，这个嘛，我用的是递归写法，简单描述就是填写当前空格，递归下一格，遇到不行返回，不过逻辑写的不好，很多奇奇怪怪的细节的判断。
算法逻辑：
- 创建一个辅助函数，help(vector<vector<char> > & board,int i,int ii,int j,int jj)，其中i为第几行，j 第几列，ii 小框中的第几行，jj 小框中第几列。
- help 函数4层for 循环遍历整个9*9 矩阵，说是4层，跟两次for 是一样的，i 和j 的步长是3，for(;i<9;i+=3)，因为这4个变量的初始化在函数传入的时候，所以在其循环结束时候尾部赋0，其中一个不好的地方。
- 4层循环内部，首先判断当前格board[i+ii][j+jj]是否为数字，不然继续循环。
- 创建标记finish = false，标记接下来的填入（当前格为空）能否完成整个矩阵，用于控制跳出填写，和如果填写失败修复当前格为'.' 回溯。
- 遍历1-9 尝试填写，需要用到bool canIn=true，判断行，列，框中的情况，如果通过判断则修改当框为遍历的数字，递归下一格，输入当前格的i ii j jj，便可以，这是第二个不好的地方，判断没有写为外部函数，另外函数的参数设置导致了很多细节问题。
- 下层返回的值赋予 finish ，如果为false ，表示当前填写不行，继续遍历，如果为true，跳出填写的遍历。
- 结束遍历后判断是否已经填写整个矩阵，如果finish 为false，表示失败了，则当前格，然后返回false，成功先别返回。
- 外部4层循环结束返回true。
所以在外层循环后返回true，是假如例子上的情况，最后一个格不为空，那么按上面逻辑是不会进入内部的，而如果能够全部遍历完整个矩阵，那么表示没有在内部返回，等价于成功填写了。
之所以使用 ii jj，是为了可以方便处理3*3框，在能否填写的时候，需要注意跳过自身与自身判断，先判断行列，然后框的时候变可以跳过当前框所在的行列了。
#include <vector>
#include <iostream>
#include <iterator>
using namespace std; class Solution {
public:
void solveSudoku(vector<vector<char> > &board) {
help(board,,,,);
}
bool help(vector<vector<char> > & board,int i,int ii,int j,int jj){
for(;i<;i+=){
for(;ii<;ii++){
for(;j<;j+=){
for(;jj<;jj++){
if(board[i+ii][j+jj]!='.') continue;
bool finish = false;
for(char c='';c<=''&&!finish;c++){
bool canIn= true;
for(int k=;k<&&canIn;k++){
if(k!=i+ii&&board[k][j+jj]==c) canIn = false;
if(k!=j+jj&&board[i+ii][k]==c) canIn = false;
}
for(int ti=;ti<&&canIn;ti++){
if(ti == ii) continue;
for(int tj=;tj<&&canIn;tj++){
if(tj==jj) continue;
if(board[ti+i][tj+j]==c) canIn = false;
}
}
if(canIn==false) continue;
board[i+ii][j+jj] = c;
finish = help(board,i,ii,j,jj);
}
if(!finish){ board[i+ii][j+jj] = '.'; return false; }
}
jj = ;
}
j=;
}
ii=;
}
return true;
}
}; int main()
{
vector<char> line;
vector<vector<char> > board;
line = {'','','.','.','','.','.','.','.'};
board.push_back(line);
line.clear();
line = {'','.','.','','','','.','.','.'};
board.push_back(line);
line.clear();
line = {'.','','','.','.','.','.','','.'};
board.push_back(line);
line.clear();
line = {'','.','.','.','','.','.','.',''};
board.push_back(line);
line.clear();
line = {'','.','.','','.','','.','.',''};
board.push_back(line);
line.clear();
line = {'','.','.','.','','.','.','.',''};
board.push_back(line);
line.clear();
line = {'.','','.','.','.','.','','','.'};
board.push_back(line);
line.clear();
line = {'.','.','.','','','','.','.',''};
board.push_back(line);
line.clear();
line = {'.','.','.','.','','.','.','',''};
board.push_back(line);
Solution sol;
sol.solveSudoku(board);
for(int i=;i<board.size();i++){
copy(board[i].begin(),board[i].end(),ostream_iterator<char>(cout," "));
cout<<endl;
}
return ;
}