开始的话:这个程序现在还不稳定,有时出现运行时错误,跟踪是由于vector的size()方法引起的。调试发现中间的min_seq并没有完全按照作者的意图变化。 运行时,如果出现错误,就反复运行,运行成功即可出现一个正确的9*9数独矩阵。 如果要玩预先填充一些数的游戏,只需修改初始矩阵即可。 算法:为每个位置定义一个可选元素集合,每个更新是把它所在的行,列,所在的3×3方阵中已出现的元素从集合中去掉。填充时,从最小候选集合中选一个(可随即)填进去,更新候选集合,再填充,直到所有位置填充完毕,游戏结束。 /*******9×9数独游戏的计算机程序*******/ /*******作者:xiaocui******************/ /*******时间:2006.6.23****************/ /*******版本:v1.0*********************/ /*******算法思想***********************/ /******对每个位置的元素,考虑其可选取的数字 的集合,每次把候选元素个数最小的那个位置填充 从该最小候选集合中随机选取一个元素填充,重复 这个过程,直到所有元素填充完毕************/ /****适用填充全空的数独方格 和 填充已有一些数的数独方格*****/ /****对初始化的候选集的第一次更新正是为了解决第2类数独游戏***/ /****对于已填充一部分元素的,直接修改MATRIX矩阵即可*****/ /****数独游戏的结果不止一种********/ #include #include #include using namespace std; /**********初始9×9的矩阵*************/ /******元素为0,说明该位置还未填充***/ int MATRIX[9][9]={ {0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0} }; /*******初始给出的元素个数***********/ int INITIAL_COUNT; /********已填充元素个数,作为填充结束标志**********/ int FINISH_COUNT=0; /********各个元素的初始候选集合*******/ vector > IVEC(81); /**************函数原型******************/ /*********得到初始给出的元素个数*******/ int get_initialcount(); /*******初始化候选集合***************/ void initial_candidate(); /***********从vector中删除指定元素*******/ void delete_value(vector &ivec,int value); /********更新候选集合**************/ void refresh_candidate(); /*********返回9×9候选集合元素最少的候选集合序号*******/ int min_seq(); /********随机生成一个位置序号并取得该序号所对应的元素值******/ int choose_seq(int min_seq); /*******填充该元素并判断是否填充完毕********/ int is_finish(int min_seq, int choose_value); int main() { /******得到初始给出的元素个数*****/ INITIAL_COUNT=get_initialcount(); /******初始化候选集合*******/ initial_candidate(); /********先更新候选集合(为了应付已经填充一部分数的情况)******/ refresh_candidate(); int i; int MinSeq; int ChooseValue; MinSeq=min_seq(); ChooseValue=choose_seq(MinSeq); while(is_finish(MinSeq,ChooseValue)!=1) { refresh_candidate(); MinSeq=min_seq(); ChooseValue=choose_seq(MinSeq); } /**********输出填好的数独游戏结果*********/ for( i=0;i<9;++i) { for(int j=0;j<9;++j) { cout< &ivec,int value) { /*******如果ivec已经为空,直接退出**********/ if (ivec.size()==0) { return; } vector::iterator iter=ivec.begin(); while( iter