国际象棋中马的遍历问题

georgek

怎樣我玩的電腦國際象棋全都是啊? 我就怕太久沒玩早兩日才下了一隻?硗嬉粯邮切腥盏陌~ 改了嗎?

home_king

最初由 georgek 发表
怎樣我玩的電腦國際象棋全都是啊? 我就怕太久沒玩早兩日才下了一隻?硗嬉粯邮切腥盏陌~ 改了嗎?

马每步棋先横走或直走一格，然后再斜走一格。从原来的格看去，就像是日字。
我重申一点：马可以无重复地遍历整个棋盘。

georgek

01234
56789
abcde
那麼馬在2 他5去便行了1,5  如果他去9便行3,9 是這樣嗎?

home_king

大家还是想想算法吧。

devel

先整几组数组，按照马的走法每走一步就推出一个数组元素。直到每有。试试看。。

上面马的走法越说越糊涂了。就先当着中国象棋马的走法写个先。wait....

georgek

呵呵, 這樣得想想, 看?聿惶菀 樓主有頭緒沒有?~~

home

最初由 devel 发表
先整几组数组，按照马的走法每走一步就推出一个数组元素。直到每有。试试看。。

上面马的走法越说越糊涂了。就先当着中国象棋马的走法写个先。wait....

这个方法不错，先整两个0到7的随机数@{ 随机数A}[随机数B]

home_king

在棋盘角上的马，能走到的格子只有2个；在棋盘边上的马能走到的格子有3到4个；在棋盘中间的方形区内，马最灵活，一共有8个格子可以走。根据马的走法，每一步，白格上的马只能走到黑格上去，黑格上的马只能走到白格上去。

经过分析，我改进了棋盘图的存储结构。
辅助空间：构造64bit的位图保存64棋格的访问标识，已访问的赋值为1，未访问的赋值为0。在实现时，可构造char bitmap[1..8]以方便索引及进行C的位运算。
坐标轴：以坐标(row, col)标识马步走的棋格的位置，左上角到右上角为col轴从0到8，左上角到左下角为row轴从0到8。
分析可得，马有八种可能走法：

1. 
   
2. 前        (row-2,col-1)        or         (row-2,col+1)
   
3. 后        (row+2,col-1)        or        (row+2,col+1)
   
4. 左        (row+1,col-2)        or        (row-1,col-2)
   
5. 右        (row+1,col+2)        or        (row-1,col+2)
   

复制代码

坐标与位图的对应关系：
bitmap==row
bitmap.bit==col （char变量有8位，bit为8位中的某一位）
标识已访问的位(赋值为1)可用语句

1. 
   
2. bitmap[row]=bitmap[row] | (1<<col);
   

复制代码

测试是否访问可用语句如

1. 
   
2. if ( bitmap[row+2] & (1<<(col-1)) ) step=4; else break;
   

复制代码

另外，还得注意棋盘角及棋盘边上的步是否越出棋盘。

这样，既使用了图的深度搜索算法，又保证了很小的空间复杂度(64bits=8 bytes，远小于原来使用的邻接链表。

嗬嗬，课业繁忙，最近正在备考复习期间。源代码我以后奉上。

devel

home_king和我想的相似啊。。。。

谢谢大家的努力，这道题好研究呀！！
写了个不成功的，但实在弄不明白为什么不行。
#!/usr/bin/perl -w
%0=( 0,"00", 1,"01", 2,"02", 3,"03", 4,"04", 5,"05", 6,"06", 7,"07" );
%1=( 0,"10", 1,"11", 2,"12", 3,"13", 4,"14", 5,"15", 6,"16", 7,"17" );
%2=( 0,"20", 1,"21", 2,"22", 3,"23", 4,"24", 5,"25", 6,"26", 7,"27" );
%3=( 0,"30", 1,"31", 2,"32", 3,"33", 4,"34", 5,"35", 6,"36", 7,"37" );
%4=( 0,"40", 1,"41", 2,"42", 3,"43", 4,"44", 5,"45", 6,"46", 7,"47" );
%5=( 0,"50", 1,"51", 2,"52", 3,"53", 4,"54", 5,"55", 6,"56", 7,"57" );
%6=( 0,"60", 1,"61", 2,"62", 3,"63", 4,"64", 5,"65", 6,"66", 7,"67" );
%7=( 0,"70", 1,"71", 2,"72", 3,"73", 4,"74", 5,"75", 6,"76", 7,"77" );
srand; $i=int(rand(8)); $j=int(rand(8));delete${$i}{$j};
for ($count=1;$count<=63;$count++) {
if    (($i+1) =~ /[0-7]/ && ($j+2) =~ /[0-7]/ ) {delete${($i+1)}{($j+2)}; @a=%{($i+1)} ; print "@a\n"; }
elsif (($i+1) =~ /[0-7]/ && ($j-2) =~ /[0-7]/ ) {delete${($i+1)}{($j-2)}; @a=%{($i+1)} ; print "@a\n"; }
elsif (($i-1) =~ /[0-7]/ && ($j+2) =~ /[0-7]/ ) {delete${($i-1)}{($j+2)}; @a=%{($i-1)} ; print "@a\n"; }
elsif (($i-1) =~ /[0-7]/ && ($j-2) =~ /[0-7]/ ) {delete${($i-1)}{($j-2)}; @a=%{($i-1)} ; print "@a\n"; }
elsif (($i+2) =~ /[0-7]/ && ($j+1) =~ /[0-7]/ ) {delete${($i+2)}{($j+1)}; @a=%{($i+2)} ; print "@a\n"; }
elsif (($i+2) =~ /[0-7]/ && ($j-1) =~ /[0-7]/ ) {delete${($i+2)}{($j-1)}; @a=%{($i+2)} ; print "@a\n"; }
elsif (($i-2) =~ /[0-7]/ && ($j+1) =~ /[0-7]/ ) {delete${($i-2)}{($j+1)}; @a=%{($i-2)} ; print "@a\n"; }
elsif (($i-2) =~ /[0-7]/ && ($j-1) =~ /[0-7]/ ) {delete${($i-1)}{($j-1)}; @a=%{($i-1)} ; print "@a\n"; }
else { print "not match, the scripte will exit\n"; exit ; } }


先整8个关联数组，每个数组元素代表一个格，其实只要key和关联数组名就行了，元素可以任意设。
产生随机数$i and $j 代表马的走步。
$i+1，$j+2
$i+1，$j-2
$i-1，$j+2
$i-1，$j-2
$i+2，$j+1
$i+2，$j-1
$i-2，$j+1
$i-2，$j-1
这表示马的8种走法，后面的[0-7]限制了它永远走在棋盘内。
if {} elsif{} elsif {}.........决定了要是第一种情况不行，就第二种，要不就下一种，以此类推。。这样马就能自动走到下一格(走到哪一格我们并不需要关心它)。
后面的delete ${}{}是删除马走到的一格元素。就这样，有64步棋，把8个关联数组全清空为止。
举个例子：产生了随机数$i ==3.$j==3.
---->$i+1，$j+2,now，$i==4,$j==5,
---->$i+1，$j+2,now, $i==5,$j==7
---->$i+1，$j-2,now, $i==6,$j==5 #第一种情况不行了，自动选择第二种。
---->$i+1，$j-2,now, $i==7,$j==3 #第二种。
---->$i-1，$j+2,now, $i==6,$j==5 #第一和第二种都不行了。选择第三种。
就这样自动选择，直到所有的关联数组为空就行了。

问题是，为什么不能把元素删去，觉得道理是对的。。。。:ask:ask:ask
请大家给我释疑！！

devel

home_king的方法也不错，大家一起努力！
马的走法无论走哪一步都和原来的颜色不同。