前一段时间写的数独计算器,由于代码太长,这里只贴出算法思路和用到的功能函数,以及主函数.有感兴趣的可以向我索要完整的源代码. /*  Name: 数独   Copyright: 自由软件   Author: goal00001111  Date: 02-12-06 17:00  Description: 版本号3.0 对2.0版本进行了优化，使输出更合理，并能输出多个解   算法思想：1。利用不重复原理（即每个数字在每行，列，小九宫中只能出现一次），根据已确定位置，  排除与其同行，同列和同小九宫位置不能取的值。  2。根据完备性原理（即每个数字在每行，列，小九宫中必须出现一次），  若某个数字只能在某行，列，小九宫中的一个位置出现，则该位置的确定值就为该数字。  3。根据双隐数对方法，即同一行，列，小九宫中，若有两个位置都有且仅有两个相同的可能值，  则同一行，列，小九宫中的其他位置不能取该两个值。或在同一行，列，小九宫中，若某两个数字  存且仅存在于两个位置中，则这两个位置只可能取这两个值。  4。经过上面三个步骤以后，一般的数独题目都可以解决了。  若通过前面三种方法还不能确定全部位置，则调用杀手锏---穷举法。  因为经过前面三个步骤以后，未知位置已经不多了，而且未知位置的可能值也不多了，这时候只要  猜中某一个位置，则可能得到答案。  因此可以遍历所有未知位置，穷举某一个（注意不是每一个）位置的可能值，再由它得到其他位置的值，  如果出错或不能得到最终结果（确定全部位置），则分析下一个位置。  注意：这里不是采用回溯的方法----因为回溯所需空间太大，而是利用只要猜中某一个位置，  则可得到答案的原理，遍历所有未知位置。这样只需要一个辅助空间，花费很小。*/  #include <cstdlib>#include <iostream>#include <fstream> using namespace std; const int N = 9;const int POSSIBLE = 1;  //表示九宫格中的位置可以某个值 const int IMPOSSIBLE = 0; //表示九宫格中的位置不可以某个值 const bool GUESS = false; //猜测模式 const bool REALITY = true; //实际模式 struct NODE{ int data[N+1]; //数组的下标对应1-9，data[k]可以取值POSSIBLE或IMPOSSIBLE  bool only; //表示该位置的值是否确定 } ; void Input(struct NODE lib[][N]); //输入初试数据 void ShowBlock(const struct NODE lib[][N]); //输出九宫格bool IsWrongLib(const struct NODE lib[][N], int & x, int & y);//判断是否输入了错误的数据 int BasicMeans(struct NODE lib[][N]); //使用基本方法解题，并返回需要的步数 void Build(struct NODE lib[][N]); //根据输入的数据，初步排除每个位置不可能的取值void TheSameRow(struct NODE lib[][N], int row, int cel); //根据同一行的已知数据排除该位置不可能的取值void TheSameCel(struct NODE lib[][N], int row, int cel); //根据同一列的已知数据排除该位置不可能的取值void TheSameBlock(struct NODE lib[][N], int row, int cel); //根据同一小九宫格的已知数据排除该位置不可能的取值 int ChooseOnly(struct NODE lib[][N], int & count, bool mode); //把根据推导得到的新的确定位置值添加到九宫格中，若没有确定新位置，则返回0bool IsOnly(int pos[], int & num); //判断该位置的值是否唯一//判断同行，列，小九宫中是否有n相同的值  bool IsRepeated(const struct NODE lib[][N], int row, int cel, int n); int AnalyseNumber(struct NODE lib[][N], int & count, bool mode); //遍历数字1-9，进一步确定每个位置可能的取值 //累积每行中可以取值为n的位置的个数，如果只有一个位置可以取值为n，则可以断定该位置的值只能为n int JudgeRow(struct NODE lib[][N], int n, int & count, bool mode);//累积每列中可以取值为n的位置的个数，如果只有一个位置可以取值为n，则可以断定该位置的值只能为n int JudgeCel(struct NODE lib[][N], int n, int & count, bool mode);//累积每个小九宫格中可以取值为n的位置的个数，如果只有一个位置可以取值为n，则可以断定该位置的值只能为n int JudgeBlock(struct NODE lib[][N], int n, int & count, bool mode); bool DoubleNumble(struct NODE lib[][N], bool mode);//处理双隐数对 //处理某一行的双隐数对：该行有两个位置有且仅有两个相同的值 bool RowJudgeByPosition(struct NODE lib[][N], int store[][N+1], int row, bool mode);//处理某一行的双隐数对：该行有两个数字存在且仅存在于两个位置中 bool RowJudgeByNumber(struct NODE lib[][N], int store[][N+1], int row, bool mode);//处理某一列的双隐数对：该列有两个位置有且仅有两个相同的值 bool CelJudgeByPosition(struct NODE lib[][N], int store[][N+1], int cel, bool mode);//处理某一列的双隐数对：该列有两个数字存在且仅存在于两个位置中 bool CelJudgeByNumber(struct NODE lib[][N], int store[][N+1], int cel, bool mode);//处理某一小九宫格的双隐数对：该小九宫格有两个数字存在且仅存在于两个位置中 bool BlockJudgeByNumber(struct NODE lib[][N], int store[][N+1], int row, int cel, bool mode);//处理某一小九宫格的双隐数对：该小九宫格有两个位置有且仅有两个相同的值 bool BlockJudgeByPosition(struct NODE lib[][N], int store[][N+1], int row, int cel, bool mode); //处理与双隐数对处在同一行的其他位置 void DoTheRow(struct NODE lib[][N], int row, int cel_1, int cel_2);//处理与双隐数对处在同一列的其他位置 void DoTheCel(struct NODE lib[][N], int cel, int row_1, int row_2);//处理与双隐数对处在同一小九宫格的其他位置 void DoTheBlock(struct NODE lib[][N], int row, int cel, int row_1, int cel_1, int row_2, int cel_2); bool IsTwo(const struct NODE lib[][N], int row, int cel);//判断该位置是否只有两个可能值 bool Equal(const struct NODE & a, const struct NODE & b);//判断两个位置的可能值是否相等int BlockPosition(int row, int cel);//获取小九宫格的序号 bool IsEnd(const struct NODE lib[][N]); //已经得到正确结果 void Guess(const struct NODE lib[][N], int step);//使用穷举法进行猜测，以得到一个可能的答案 void CopyData(struct NODE to[][N], const struct NODE from[][N]);//复制九宫格数据到一个临时数组 void AddToLib(struct NODE lib[][N], int x, int y, int n);//把猜测的位置放到九宫格中bool GetAnswer(struct NODE lib[][N], int & step, bool mode);//判断猜测是否正确，若正确则输出该结果 void ShowProcess(const struct NODE lib[][N], int x, int y, int n, int & step, bool getOne);//演示得到正确结果的步骤 int main(int argc, char *argv[]){ struct NODE lib[N][N]; //存储九宫格所有数据   Input(lib); //输入初试数据  ShowBlock(lib); //输出九宫格   int x, y; if (IsWrongLib(lib, x, y))//判断是否输入了错误的数据 {  cout << "(" << x << "," << y << ")重复"<< endl;  system("pause");  return 0; }   Build(lib); //根据输入的数据，初步排除每个位置不可能的取值  int count = BasicMeans(lib);//使用基本方法解题，并返回需要的步数   if (count == -1) {  cout << "无解" << endl;  system("pause");  return 0; }  if (!IsEnd(lib)) //如果基本方法不能确定全部位置，则调用杀手锏---穷举法   Guess(lib, count); else {  ShowBlock(lib); //输出九宫格   cout << "共需要" << count << "步 " << endl; }  cout << "花了" << clock() << "毫秒 " << endl;     system("PAUSE");    return EXIT_SUCCESS;}

评论