Hopping dots (独立钻石棋变种)攻略

版权规定:本文是视频博客作者的独创的文字。,不博主批准,不得武断地转载。。

采用:本文,我以为议论人家使完满的游玩。,呼叫跳频 dots,翻译成逻辑谜语。

关键词:独立钻石棋、吃水第一流的搜索、可能性辨析、条款紧缩、静态设计备查簿方式

一,下载关联

点击翻开关联(是人互联网网络) 或许点击翻开的关联(是人我的百度云)

我的版本:Hopping dots 1.1

二,游玩相互作用、西洋跳棋盘、国际象棋的棋子

(下面是第一个)

西洋跳棋盘是由13点结合的。


国际象棋的棋子:1颗白色的种子和稍许的绿色的种子。

三,规定的

因独立钻石棋的规定的停止吃子,只剩人家孩子了。,为了红小伙子,那就是赢。轻视白色在哪里。

这是我本人的规定的。,与众不同的简明的,开端时瞧是不对的。,温存认真思考在世界上和学术权威精确地解释相似的。。

四,初步认得

1,国际象棋的棋子的号码

至多有12件。,无论若何有1个。。

这13片必然是死了。,因缺乏办法操纵。。

12卒境遇,缺乏生活环境。,这是瞬间地未知的。。

2,国际象棋的棋子数的找头

每个操纵,件数少于1件。,因而,若干景象,至多独自地11个手术。

3,成绩使单纯

成绩使单纯版:独自地绿色的小伙子缺乏白色的树或花草总算。,鉴于只剩人家孩子了。那就是赢(异样无论评价)

这么的版本就更接近于独立钻石棋了,精确,此外西洋跳棋盘和独立钻石棋不相似的远处,缺乏辨别。。

为球员,原成绩和成绩使单纯版多样化并做错很大,这差不多是很难玩的。。

关闭那个残忍的做实际辨析的人,,为了的成绩辨析起来很复杂。,掩饰数不清的法度。

假如你只想直觉的写吃水第一流的搜索顺序到S,缺乏必要停止使单纯。,再假如你想变成更僵硬的。,率先,从实际上辨析了可能性上浆。,因而使单纯是要做的第一步。。

4,景象的号码(成绩使单纯版)

有13点可能会有孩子。,因而境遇的号码是2 ^ 13=8192。

它也包罗很多穷途末路。,有很具体境遇?,我们家无形的。。

5,编号


6,记载承认边(不思索面貌)

不难计数,有16个面貌。

以2、6、8、12关闭居切中要害每一侧,有1个。,如1-2-3

以4、5、9、10个居中有2个边。,如1-4-7,2-4-6

以7为居中点,有4个面貌。,如2-7—12,4-7-10

不思索面貌,因若干工夫。,一面对应于人家可能的的操纵。,

以边1-2-3为例,在异样的境遇下,从1到3和从3到1都是不克不及整个操纵的。。

注意到,每边的3个数字是相当的衣服。,因而一只必要记载2位数字。,

这么,你可以运用2个16个广大地域的衣服来记载16个边。。

int st[16]={1,1,3,11,1,2,2,3,6,7,8,7,4,5,6,2};int en[16]={3,11,13,13,7,6,8,7,12,11,12,13,10,9,8,12};

五,吃水第一流的搜索的可能性辨析(成绩使单纯版)

因至多独自地11个手术。,因而吃水第一流的搜索做错很深。。如今必要计算的是,每个操纵有很种选择?

1,在若干境遇下有很选择?

我们家必要人家作用。,输入人家景象,输入数值,通知我们家我们家有很选择。。

若何输入?运用条款紧缩是最实用的的。。

13点,每个点对应于人家微不足道的。,1辱骂孩子。,0辱骂缺乏孩子。,这么,8192个景象便可以和8192个13位二元系数一一对应了。

输入以前,该作用可以直觉的计算选择的号码。,工夫是O(1)。

用这人作用,只从0到8191详表n。,你可以找出f(n)的山峰。,出狱10

指定遗传密码:

#includeusingnamespace std;int st[16]={1,1,3,11,1,2,2,3,6,7,8,7,4,5,6,2};int en[16]={3,11,13,13,7,6,8,7,12,11,12,13,10,9,8,12};intf(int n){int r =0, s, e, m;for(int i =0; i <16; i++){
		s = st[i], e = en[i], m =(s + e)/2;if((n >>(13- m))&1)r +=((n >>(13- s))&1)^((n >>(13- e))&1);}return r;}intmain(){int maxx =0;for(int n =0; n <8192; n++)if(maxx <f(n))maxx =f(n);
	cout << maxx;return0;}

2,吃水第一流的搜索的不均一

找出后面。,人家境遇至多可以运转11次以上所述。,每个操纵至多10种选择,这么,用吃水第一流的搜索处理这人成绩至多必要10^11次详表计算。这是人家与众不同的大的数字。,普通必须花费的钱要花很长工夫。。

只因为,我们家可以舒适的地发觉。,并非每个操纵都有10种选择,比方只剩2构筑的时辰至多独自地2种选择。

假如境遇有K(1)

只需运用下面作用f。。

指定遗传密码:

#includeusingnamespace std;int st[16]={1,1,3,11,1,2,2,3,6,7,8,7,4,5,6,2};int en[16]={3,11,13,13,7,6,8,7,12,11,12,13,10,9,8,12};int num[14];voidf(int n){int r =0, s, e, m, k =0;for(int i =0; i <16; i++){
		s = st[i], e = en[i], m =(s + e)/2;if((n >>(13- m))&1)r +=((n >>(13- s))&1)^((n >>(13- e))&1);}while(n){
		k += n &1;
		n /=2;}if(num[k]< r)num[k]= r;}intmain(){for(int i =0; i <14; i++)num[i]=0;for(int n =0; n <8192; n++)f(n);for(int i =2; i <=12; i++)cout << num[i]<<"  ";return0;}

运转总算:

2  4  7  7  9  10  9  9  8  6  4

2*4*7*7*9*10*9*9*8*6*4=548674560,因而若干境遇下。,停止吃水第一流的搜索的话,至多必要约5亿次详表计算

计算性能在一秒钟内计算大概1亿次。,因而这次是可以同意的。。

七,处理原始成绩

最初的的成绩是鉴于对白色孥的限度局限。,乃规划更为复杂。,但缺乏必要倾斜。。

这么,你可以经过吃水第一流的搜索来处理这人成绩。,同时,因境遇的号码是高级快车的。,因而用静态设计备查簿方式来克制不要反复任务。

指定遗传密码:

#include#includeusingnamespace std;int r[8192][14];int st[16]={1,1,3,11,1,2,2,3,6,7,8,7,4,5,6,2};int en[16]={3,11,13,13,7,6,8,7,12,11,12,13,10,9,8,12};
stack<int>ans;boolf(int n,int k){if(n ==(n&-n))returntrue;if(r[n][k]<0)returnfalse;int s, e, m;for(int i =0; i <16; i++){
		s = st[i], e = en[i], m =(s + e)/2;if(m == k)continue;if(!((n >>(13- m))&1))continue;if(!(((n >>(13- s))&1)^((n >>(13- e))&1)))continue;int nn, kk = k, tem;if(k == s || k == e)kk = s + e - k;
		tem =(1<<(13- s))+(1<<(13- e));
		nn = n -(n&tem)+ tem -(n&tem)-(1<<(13- m));if(f(nn, kk)){
			ans.push(i);
			m =-1;break;}}if(m ==-1)returntrue;
	r[n][k]=-1;returnfalse;}intmain(){int n =0, k;
	cout <<按编号\n1    2    3\n  4    5\n6    7    8\n  9    10\n11   12   13\n";
	cout <<上上下下。,从左往右,授权代理输入每个点阵。\n1辱骂孩子。,0辱骂缺乏孩子。,全部情况都被空白隔开了。\n";for(int i =1; i <=13; i++){
		cin >> k;
		n = n *2+ k;}
	cout <<"输入红子外景格子的序号(1-13)\n";
	cin >> k;for(int i =0; i <8192; i++)for(int j =0; j <14; j++)r[i][j]=0;while(!ans.empty())ans.pop();f(n, k);
	cout <<"答案为:(社交的表现人家操纵),每个行切中要害2个圆整数辨别表现胚芽点和完毕点。\n";while(!ans.empty()){int i = ans.top();
		ans.pop();
		cout << st[i]<<"   "<< en[i]<< endl;}return0;}

示例:




发表评论

电子邮件地址不会被公开。 必填项已用*标注