c++实现数算法假设检验法Word格式.docx
- 文档编号:8463058
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:17
- 大小:174.63KB
c++实现数算法假设检验法Word格式.docx
《c++实现数算法假设检验法Word格式.docx》由会员分享,可在线阅读,更多相关《c++实现数算法假设检验法Word格式.docx(17页珍藏版)》请在冰点文库上搜索。
Medium难度所需技巧:
独立值法(自创的名字,玩过数独的人肯定都用过)
除了排除法,Medium难度还需要我所谓的“独立值法”。
就是说,在一个数独集合(1-9不能重复的9个位置的集合,比如每一横、竖、3x3所包含的9个小格所组成的集合)中,一个数字在只在其中一个位置出现了一次,而并没有在其它位置出现,那么就可以断定该数字就应填入该位置。
这点应该很好理解,这里就不多说为什么了。
循环利用此法与排除法,就可全解Medium难度的所有数独。
Hard难度所需技巧:
其实Hard难度就是比Medium难度稍微复杂了一些,要多动动脑筋,使用的方法都一样。
VeryHard难度所需技巧:
假设检验(可能是刚学完《概率论与数理统计》的缘故)
当你循环使用排除法与独立值法共同解VeryHard难度时,发现到了一定阶段,你两种方法都已经无用武之地了,这时你就需要使用“假设检验”。
其实非常好理解,你先假设一个位置为一个该位置可能的取值,以此为依据,循环使用排除与独立值法,如果能解决,那最好;
如果经排除法发现有个别位置不可能填任何数,则说明假设错误,应更换假设;
如果发现扔无法解决,那么不好意思,你要再对另一个位置进行假设,直到算出最后结果。
具体方法就这些,接下来的数据结构和算法部分请见后续文章。
(未完待续...)
C++实现解数独算法——输入与输出
简单介绍完数独后,就开始介绍C++实现的数据结构和算法了。
首先先介绍数独的输入与输出,建立一个数独类。
/*sudoku.h*/
#pragmaonce//仅编译一次,防止重复编译
#include<
iostream>
bitset>
//使用位运算的容器模板类
usingnamespacestd;
classsudoku
{
public:
sudoku();
//构造函数,通过输入初始化数独矩阵
voiddisplay();
//输出数独结果
boolSTD_Remove();
//排除法,即在横、纵及3x3方向上不能有重复的排除法。
返回0:
没有修改;
1:
存在修改
private:
bitset<
9>
sudoku9[9][9];
//9x9数独矩阵
};
这里要说的是bitset这个东东,它是C++提供的位运算的标准模板库。
比如bitset<
a;
的意思是建立一个有9个位的变量a。
我这里私有成员是一个9x9的二维数组,其中每个元素都是占用9个位。
为什么要这样呢?
因为每个空位都有9种可能,有一个数的可能存在,就会在该位置置1,反之置0。
也就是说,如果这个位置是一个确定的数,比如6,那么这9个位中只有这个数的位置(6)上置1,其余全是0,即000001000;
如果这个位置有三种可能,分别是1、3、5,那么它在内存中就是101010000。
为了节省时间,具体bitset的一些相关函数,请读者参考C++相关书籍,在这里就不多说了。
下面我就介绍一下数独的构造函数。
在sudoku.cpp中:
//#defineTEST
sudoku:
:
sudoku()//构造函数,通过输入初始化数独矩阵
inti,j,num;
#ifdefTEST//为了方便测试而使用的,将数独数据写在程序中,每次调试时不必重新输入
constchartestSDK[9][10]={{"
600009000"
},{"
039000500"
504030809"
000005300"
050398020"
003700000"
302060904"
007000630"
000400008"
}};
for(i=0;
i<
9;
++i)
for(j=0;
j<
++j)
{
num=testSDK[i][j]-48;
if(num>
0&
&
num<
10)
sudoku9[i][j].set(num-1);
elsesudoku9[i][j].set();
}
#else
chartemp[10];
cin.read(temp,10);
//输入数独数据,每9个一组
num=temp[j]-48;
num<
#endif
}
输出函数:
voidsudoku:
display()//输出数独结果
inti,j,k;
++i,cout<
<
endl)
if(sudoku9[i][j].count()!
=1)//判断每一元素中1的个数,如果数量不为1,证明该位置还没有确定的值,则打印0
cout<
0<
'
'
;
continue;
else
for(k=0;
k<
++k)
if(sudoku9[i][j].test(k))
k+1<
break;
}
到这里,必要的输入与输出就结束了,本文重点在于掌握bitset和标准iostream的一些基本用法。
C++实现解数独算法——排除法
标准排除法的大体思路我已经在第一篇序中讲的比较清楚了,下面就差用编程实现了。
其实在看完大气思路之后,我相信大家就已经有思路了,就是通过一系列循环一个一个地进行排除。
首先重新把sudoku类写一遍。
//使用位运算的标准模板库
//标准排除法,即在横、纵及3x3方向上不能有重复的排除法。
然后再把我们的STD_Remove()实现。
boolsudoku:
STD_Remove()//标准排除法,即在横、纵及3x3方向上不能有重复的排除法。
inti,j,x,y,posbit;
boolflag=0;
if(sudoku9[i][j].count()==1)//如果已经有确定值
for(posbit=0;
posbit<
++posbit)//获得为1的位的位置
if(sudoku9[i][j].test(posbit))break;
for(y=0;
y<
++y)//横向扫描,排除候选
if(y==j)continue;
//同一个点则跳过,扫描下一个点
else
if(sudoku9[i][y].test(posbit))
sudoku9[i][y].reset(posbit);
if(sudoku9[i][y].count()==1)flag=1;
//排除使得该位置出现确定值时,置标志位
for(x=0;
x<
++x)//纵向扫描,排除候选
if(x==i)continue;
if(sudoku9[x][j].test(posbit))
sudoku9[x][j].reset(posbit);
if(sudoku9[x][j].count()==1)flag=1;
for(x=(i/3)*3;
(i/3)*3+3;
++x)//3*3扫描,排除候选
for(y=(j/3)*3;
(j/3)*3+3;
++y)
if((y==j)||(x==i))continue;
if(sudoku9[x][y].test(posbit))
sudoku9[x][y].reset(posbit);
if(sudoku9[x][y].count()==1)flag=1;
returnflag;
//flag取值0:
关键代码都给出了注释,如有疑问,敬请留言,欢迎指教。
C++实现解数独算法——独立值法
独立值法的大体思想与排除法大体思想类似,只要分别对每个位置的横、竖及3x3,这3个方向进行扫描,根据需要对相应的位置进行操作即可。
为了减少在该种方法上的计算量,我在写代码时,在每扫描一个集合后,进行一次判断(逐点扫描是很慢的)。
如果发现独立值,则确定它,并使用排除法进一步降低一些位置的可能性,同时直接跳过下一种扫描方式,进行下一个位置的扫描;
如果没有发现独立值,则直接进行下一个方向的扫描,直到3种方向(横、竖、3x3)都扫描完而进行下一个位置的扫描。
这样看来,因为发现独立值后,处理的方法均相同,所以使用的代码也相同。
如果同时写入程序,势必使代码冗长。
所以在这里我#define了一下,即:
#defineSDK_HANDLE{sudoku9[i][j].reset();
sudoku9[i][j].set(k);
flag=1;
if(STD_Remove(i,j))while(STD_Remove());
break;
这个SDK_HANDLE代码段的功能就是
1、将该位置(i,j)的变成一个确定的值k。
2、置标志位,函数返回时告诉外部“此次调用函数使数独产生了变化,又有新位置的值被确定”。
3、循环对该位置进行排除法,知道数独中没有可以被排除的值。
4、跳出循环,对下一个位置进行扫描
剩下的就没有什么了要解释的了,请看代码(.cpp中在之前文章讲过的代码就不重复发了):
sudoku.h:
sudoku(constsudoku&
original,intindex,intnum);
//构造函数,通过复制进行的初始化
boolSTD_Remove(intx,inty);
//针对想(x,y)位置进行横、纵、3x3排除运算
boolalone_determine();
//如果在一个数独集合中,一个数字在只出现了一次,那么就可以确定这个数字就应填在该位置
sudoku.cpp:
STD_Remove(inti,intj)
intx,y,posbit;
alone_determine()
inti,j,k,x,y;
boolflag=0,alone=1;
//flag是返回值,1:
数独有新变化,0:
数独无变化。
alone是独立值标志位,1:
未发现独立值,0:
发现独立值
if(sudoku9[i][j].count()>
1)
k++)
alone=1;
//标志位复位
++y)//横向扫描
elseif(sudoku9[i][y].test(k))//测试同一数独集合的第k位,发现有重复的候选
alone=0;
//不是唯一
if(alone)SDK_HANDLE//如果发现该数字是唯一的,则可以确定该为数字,同时在进行标准排除法
++x)//纵向扫描
e
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- c+ 实现 算法 假设检验