问题来源：leetCode Sudoku Solver
Write a program to solve aSudoku puzzle by filling the empty cells. Empty cells are indicated by the character *.*. You may assume that there will be only one unique solution.
问题链接：
https://oj.leetcode.com/problems/sudoku-solver/
功能：
自动解数独题
大概方案： 采用以行为单位的DFS来寻找答案。 提纲： 0、对全部数据进行候选数预处理，记录下每个空格的候选数。 1、根据候选数表和当前结果表，以行为单位，递归产生所有可能的行，并加入结果数组，然后对每一个产生的可能行进行新一轮的递归调用。这里有一个互相递归调用的行为。 2、若无法产生可能的行或产生完所有行的下一级返回假，则返回假。 3、若有一个下级递归返回真或者最后一行中成功产生了可能的行，返回真。 主要方法概览： （注意：候选数表为全局数组，所有方法可以直接访问） 0、bool tryRow(introw,vector<vector<int> > &res)； 该方法为对某行进行数字试填，row为某行的行号，res为当前结果数组。 1、bool fillRow(introw,int col,vector<int> &now,vector<vector<int> >&res)； 该方法为对特定的格子进行数字试填，row为行号，col为列号，now为当前行中已填的数字，res为结果数组。 2、以上两种方法互相递归调用。对于特定新行，调用tryRow方法，而填新行内的数则递归调用fillRow，当当前行已经填满后，在fillRow中调用新一轮的tryRow方法进入下一行。 Solution类的全部代码和注释：（\t被吞，用/*...*/来缩进）#include <iostream>
#include <vector> #include <cstdio> using namespace std; class Solution { public: /*......*/ int sel[9][9][10]; // 候选数数组，sel[x][y][0]标记横坐标为x，纵坐标为y的格子是否有数字，有则为该数字， // 待填则sel[x][y][num](1<= num <=9)为1表示该格子可选数包括num. /*......*/ Solution() /*......*/ { /*.........*/ for (int i = 0;i < 9;i++) /*............*/ for (int j = 0;j <9;j++) /*...............*/ for (int p = 0;p <10;p++) /*..................*/ sel[i][j][p] = 1; /*......*/ } /*......*/ voidsolveSudoku(vector<vector<char> > &board) // 主处理方法 /*......*/ { /*.........*/ vector<vector<int>> res; /*.........*/ init(board); // 进行候选数初始化处理 /*.........*/ tryRow(0,res); /*.........*/ int len1 = board.size(); /*.........*/ int len2 = board[0].size(); /*.........*/ for (int i = 0;i <len1;i++) /*............*/ for (int j = 0;j <len2;j++) /*...............*/ if (board[i][j] == *.*) /*..................*/ board[i][j] =res[i][j] + *0*; /*......*/ } /*......*/ bool tryRow(introw,vector<vector<int> > &res) /*......*/ { /*.........*/ if (row >= 9) /*.........*/ { /*............*/ return true; /*.........*/ } /*.........*/ bool flag = false; /*.........*/ vector<int> now(10); /*.........*/ flag =fillRow(row,0,now,res); /*.........*/ return flag; /*......*/ } /*......*/ bool fillRow(int row,intcol,vector<int> &now,vector<vector<int> > &res) /*......*/ { /*.........*/ bool flag = false; /*.........*/ if (col >= 9) /*.........*/ { /*............*/ res.push_back(now); /*............*/ flag = tryRow(row +1,res); /*............*/ if (flag == false) /*...............*/ res.pop_back(); /*............*/ return flag; /*.........*/ } /*.........*/ if (sel[row][col][0] != 0) /*.........*/ { /*...............*/ now[col] =sel[row][col][0]; /*...............*/ flag = fillRow(row,col+ 1,now,res); /*...............*/ return flag; /*.........*/ } /*.........*/ int hash[10] = {0}; // now中现存的数为1,该数组中为1的数不能选 /*.........*/ for (int i = col - 1;i >=0;i--) // 判断当前行中需要更新的候选数 /*............*/ hash[now[i]] = 1; /*.........*/ update(row,col,hash,res); // 该函数继续更新该格子的候选数 /*......*/ for (int i = 1;i <= 9;i++) /*.........*/ { /*............*/ if (hash[i] == 0&& sel[row][col][i] == 1) /*............*/ { /*...............*/ now[col] = i; /*...............*/ flag = fillRow(row,col+ 1,now,res); /*...............*/ if (flag) /*..................*/ return true; /*............*/ } /*.........*/ }/*...*/ /*.........*/ return flag; /*......*/ }/*...*/ /*......*/ /*......*/ void update(int row,int col,int*hash,vector<vector<int> > &res) /*......*/ { /*.........*/ int top = getTop(row); /*.........*/ int left = getLeft(col); /*.........*/ for (int i = row - 1;i >=0;i--) // 既有结果列中的数不能选 /*.........*/ { /*...............*/ hash[res[i][col]] = 1; /*.........*/ } /*.........*/ if (row > top) /*.........*/ { /*............*/ int count = row - top; /*............*/ for (int i = 0;i <count;i++) /*...............*/ for (int j = 0;j <3;j++) /*..................*/hash[res[top+i][left+j]] = 1; /*.........*/ } /*......*/ } /*......*/ voidinit(vector<vector<char> > &board) /*......*/ { /*.........*/ int len1 = board.size(); /*.........*/ int len2 = board[0].size(); /*.........*/ for (int i = 0;i <len1;i++) /*............*/ for (int j = 0;j <len2;j++) /*............*/ { /*...............*/ if (board[i][j] != *.*) /*...............*/ { /*..................*/ setRow(i,board[i][j]- *0*); /*..................*/ setCol(j,board[i][j]- *0*); /*..................*/setCel(i,j,board[i][j] - *0*); /*..................*/ sel[i][j][0] =board[i][j] - *0*;/*...*/ /*...............*/ } /*...............*/ else /*..................*/ sel[i][j][0] = 0; /*............*/ } /*......*/ } /*......*/ void setRow(int i,int num) /*......*/ { /*.........*/ for (int j = 0;j < 9;j++) /*.........*/ { /*............*/ sel[i][j][num] = 0; /*.........*/ } /*......*/ } /*......*/ void setCol(int j,int num) /*......*/ { /*.........*/ for (int i = 0;i < 9;i++) /*.........*/ { /*............*/ sel[i][j][num] = 0; /*.........*/ } /*......*/ } /*......*/ void setCel(int x,int y,intnum)// 求方格的左上坐标 /*......*/ { /*.........*/ int top,left; /*.........*/ top = getTop(x); /*.........*/ left = getLeft(y); /*.........*/ for (int i = 0;i < 3;i++) /*............*/ for (int j = 0;j <3;j++) /*...............*/ sel[i+top][j+left][num]= 0; /*......*/ // 该函数同getTop一样，用来求位于x行y列的格子所在的正方形格的位置。 /*......*/ int getLeft(int col) /*......*/ { /*.........*/ int tmp; /*.........*/ int left; /*.........*/ tmp = col % 9; /*.........*/ if (tmp >= 6) /*.........*/ { /*............*/ left = 6; /*.........*/ } /*.........*/ else if (tmp >= 3) /*............*/ left = 3; /*.........*/ else /*............*/ left = 0; /*.........*/ return left; /*......*/ } /*......*/ int getTop(int row) /*......*/ { /*.........*/ int tmp; /*.........*/ int top; /*.........*/ tmp = row % 9; /*.........*/ if (tmp >= 6) /*.........*/ { /*............*/ top = 6; /*.........*/ } /*.........*/ else if (tmp >= 3) /*.........*/ { /*............*/ top = 3; /*.........*/ } /*.........*/ else /*............*/ top = 0; /*.........*/ return top; /*......*/ } }; // 测试函数 int main(void) { /*...*/ vector<char> now; /*...*/ vector<vector<char> >res; /*...*/ int c; /*...*/ Solution *p = new Solution(); /*...*/ while ((c = getchar()) != EOF) /*...*/ { /*......*/ if (c != '\n') /*.........*/ now.push_back(c); /*......*/ else /*......*/ { /*.........*/ res.push_back(now); /*.........*/ now.clear(); /*......*/ } } /*...*/ p->solveSudoku(res); /*...*/ return 0; }