Sudoku Solver: Backtracking Algorithm with Optimization

#include <iostream> #include <vector> #include <time.h> using namespace std;

int question[10][10]{}; //文件给出信息 int rowmark[10][10]{}; //行数据标签 标记第n行 数字m是否存在 int colmark[10][10]{}; //列数据标签 int blockmark[10][10]{}; //块数据标签 int row[10]{},col[10]{},block[10]{}; clock_t start,finish; class point { public: int r,c,n=0; point(int _r, int _c) { r=_r; c=_c; } }; vector<point>tofill; boolean judge(int r,int c,int n); boolean backtrack(int); void setmark(int r, int c, int n, bool flag); inline int getblocknum(int r,int c); void printboard(); void Clear(); int main(int argc, const char * argv[]) { start=clock(); int count; cin>>count; while(count--) { for(int r=1;r<10;r++)//from 1 to 9 { for(int c=1;c<10;c++)//from 1 to 9 { char ch; cin>>ch; question[r][c]=ch-'0'; if(question[r][c]==0) { tofill.push_back(point(r,c)); } else { setmark(r, c, question[r][c], 1); } } } if(backtrack(0)) { cout<<"\nResult:"<<endl; printboard(); } Clear(); } finish=clock(); //cout<<(finish-start)<<endl; return 0;

} // 修改标签，确定是否填入数据 void setmark(int r, int c, int n, bool flag) { rowmark[r][n]=flag; colmark[c][n]=flag; blockmark[getblocknum(r, c)][n]=flag; }

inline int getblocknum(int r,int c) { return ((r-1)/3)*3+((c-1)/3); }

boolean judge(int r,int c,int n) { return !rowmark[r][n]&&!colmark[c][n]&&!blockmark[getblocknum(r, c)][n]; }

void printboard() { for(int r=1;r<10;r++)//from 1 to 9 { for(int c=1;c<10;c++)//from 1 to 9 { cout<<question[r][c]; } cout<<endl; } } void Clear() { for(int i=0;i<=10;i++) { for(int j=0;j<=10;j++) { rowmark[i][j]=0; colmark[i][j]=0; blockmark[i][j]=0; question[i][j]=0; } } }

boolean backtrack(int step) { if(step==tofill.size()) { return true; } int reverse=(int)tofill.size()-step-1; int r=tofill[reverse].r,c=tofill[reverse].c; //int r=tofill[step].r,c=tofill[step].c; for(int i=1;i<10;i++) { if(judge(r, c, i)) { question[r][c]=i; setmark(r, c, question[r][c], 1); if(backtrack(step+1))return true; setmark(r, c, question[r][c], 0); question[r][c]=0; } } return false; } 分析这段代码中reverse的意义内容：在backtrack函数中，reverse的意义是tofill数组中剩余未填数字的反序索引。由于backtrack函数的参数step作表已填入数字的数量，所以reverse = tofill.size() - step - 1 表示未填入数字的反序索引。这样可以保证在退归回溯过程中，按照从后向前的顺序填入数字，使得填入的数字更加近于终止解&#x300