前一段时间写的数独计算器,由于代码太长,这里只贴出算法思路和用到的功能函数,以及主函数.有感兴趣的可以向我索要完整的源代码.

/*
  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); //把根据推导得到的新的确定位置值添加到九宫格中，若没有确定新位置，则返回0
bool 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;
}

评论