[问题] 算法：国际象棋的马

FrostNova

以前有国际象棋的8王后问题,问8个王后在棋盘上怎么放置能够不互相冲突（不被吃掉），这个不算困难，用backtracking就可解决

现在有国际象棋的马问题：问在8x8国际象棋棋盘上最多能够放置多少的马且互相不冲突。
我是这样想的，例如判断坐标(j,k)，则坐标为(j+/- 1, k+/- 2)  (j+/-2, k+/-1)的8个点是跳马的冲突点，如果这8点任意1点已经有马了，则坐标j,k不能再放马

但是问题是，如何找到棋盘上放置最多数量且不互相冲突的马的算法，注意要求：最多！
是不是除了回溯backtracking以外，还需要用到最佳选择法Optimale Auswahl呢？
应该如何实现算法？或者说，如何判断该数量最多？

我是猪_

恩，这就是那个马踏棋盘那个吧
我原来做过data structure的作业，用的就是探测回嗍
不过效率狂低

leexp82

从8x8棋盘的某一点开始计算，考虑到棋盘的对称性，第一个马其实只有十种不同的放法，从其余的70格里开始，都不会产生不同的结果。
这样，从十格的每一格开始，遍历整个棋盘，遍历棋盘的方法相比大家已经很熟悉了。这样会得出一组无法到达的格，然后在这些格里重复第一步(还是先过滤对称的位置)。多步递归算法，只要有路线冲突，就可以结束当前的分支。

遍历棋盘的算法，我的心得是，对于n x n的棋盘，我们第一次生成一个 （2n-1)平方的大棋盘，bool 数组，这样就可以把马放在大棋盘的中心点，只要简单的吧小棋盘和大棋盘的局部作逻辑运算，就可以简单高效的实现遍历问题。这样，只要一开始对大棋盘做一次遍历，其后每次在小棋盘内的遍历只要做逻辑比较就可以。这样的(bitwise)运算是最高效的。基于对称的考虑则可以避免重复运算。

FrostNova

谢谢楼上，数学系的高手 (^_^)
你是在Darm做Dozent助教么？

不过我还是笨，不明白遍历在其中起什么作用

leexp82

比如说一个3x3的棋盘
000
000
000
就可以用5x5的大棋盘来判断马的走位,#代表马，1代表马下一步可以到达的位置
01010
10001
00#00
10001
01010
把大棋盘的局部和小棋盘重合（也就是把两个棋盘上的马位重合），布林运算就可以得出所有可到达或不可到达的位置。这个方法是独门秘技哦，有点怪。目的是较少运算量，否则你每一步都要遍历一次棋盘（大棋盘的内容就是一次性便利棋盘的结果）。遍历棋盘是为了找出不可到达的位置，也就是可以放下一个马的位置。这样你应该明白了吧。

ps:你怎么知道我当过助教？又是数学系的？我没有跟任何人讲过啊。难不成我连自己是个名人都不知道？

jiayun80

最初由 leexp82 发表
[B]ps:你怎么知道我当过助教？又是数学系的？我没有跟任何人讲过啊。难不成我连自己是个名人都不知道？
[/B]

hehe。。。殊不知。。。那位nova兄可是查底细的高手哦。。。他有他的独门算法。。。

FrostNova

jiayun你竟然把我说的这么恐怖！（最近abcdvbbs发生了一件很搞笑的事情，有空告诉你）
这些天我的理解能力迅速下降，反应迟钝了不少
算法，算法，Algorithmus真博大，到了编程序实现这步，又谋杀我不少脑细胞，变量一多就头疼……sigh!

谢谢leexp82的解释，名人！名人！

我是猪_

楼主，有了算法，实现起来都会头疼呀

leexp82是个高手，呵呵,看来数学功底果然。。。。

FrostNova

问题是，如何判断能在棋盘上放置尽可能最多的不冲突的马？？？
是否需要一个计数器？

不知道我有没有正确理解leexp82的意思，lee的算法是利用棋盘的对称性（大棋盘到小棋盘的位置映射），来算出马永远不可能到达的点？是否是这样？

嗯，再次召唤一下leexp82...：）

Khan

晕，你们到底是研究研究的是马的冲突问题还是马踏棋盘问题？说着说着就跑题！

大棋盘确实是不传秘笈啊！佩服佩服！

FrostNova

是马的冲突问题！

但是我在第9楼觉得leexp的算法是针对马踏棋盘的……
所以困惑……

Khan

别困惑啦，当然针对马踏棋盘，否则要那么大的棋盘干啥？

我是猪_

需要一个计数器

FrostNova

噜噜噜噜噜，再召唤一下……

leexp82

you are interested in how many knights you can place on the board, so with my solution, I basically put down the first knight, then mark all the positions which can be reached by that knight, and you can put down the next knight at each of the remaining unmarked positions. of course you will need to have a counter for each constellation of the knights, and another for the maximum number of knights you are able to place in the board with the best constellation.

for example, there are n possible positions for placing the first knight, FOR EACH of the n initial positions, you do the pattern matching thing with the big and small board, so you can easily mark the positions reachable by the knight, assuming that the big board already contain all these points(you do this calculation only ONCE at the beginning ie i+/- 2, k+/- 2 ...).

the next step would be to decide how you want to place your second knight(in one of the m remaining blocks). so you repeat the above procedure recursively FOR EACH of the remaining points, and after each recursive call you will have a smaller set of points. you will eventually find out that you can't put down any more knights, because when you overlap the two boards, the "1"'s in the big board will overlap onto the "1"'s in the small one. This means if you put the knight down, it will be able to meet one of the existing knights after some moves.

understood? now you may have realized that it will take n*m*.... iterations to to through all the constellations. but when you look at the check board, you will realize e.g. if you first put down a knight at a corner, no matter which one, your final result will be identical, due to the symmetry of the chess board. so you only consider the initial positions that will yield different outcomes. This trick will prevent lots of unnecessarily repeated computation.


<<晕，你们到底是研究研究的是马的冲突问题还是马踏棋盘问题？说着说着就跑题！

so now you should(hopefully) see that, these two are really the same problem; without traversing the whole chessboard in all possible paths, how do find the optimal solution? but theoretically, there should be a more elegent mathematical solution, which i don't know. That's why I have gone through all the trouble to describe this solution. let me know if you can solve the problem in a few lines(I really think it is possible).

leexp82

refering to my last words previously, I will give an example to give you an impression.

A classical problem: The tower of hanoi. the question is for how many moves are required to move all the discs to the target pole.

The typcial CS approach: (do the job and keep a count)
====================
moving all the discs according to the well known recursive solution, count the moves. so at the end, you have a counter and the actually discs moved to the target pole. the whole process can be visualized. you can find java applets on the web doing this.

Mathematical solution(from a friend): (assume that we are doing the job, let's count)
============================
doesn't move any thing, but only trying to find out the number of moves required. good enough in this case.
1 disc:    1 move.
2 discs:   1 +  1  + 1 moves. 3 steps: put the smaller disc on the TEMP pole, then the bigger bottom one to the TARGET, at last the disc on the TEMP back on the TARGET pole.
....
so for N discs:  ==== number of moves for moving N-1 disks to another pole TEMP, say M
                            +++number of moves for moing the last disk to the target pole , ie 1
                           +++ moving N-1 disks from TEMP to TARGET, so the same as above, M

2M+1!!!

This amounts to only about 10 lines of code, doesn't do much except telling you so many moves are required, but won't move the disks for you.

In the case of our problem with the knights on the chessboard, I think there is a solution to calculate the number of knights without actually placing them on the board. But with my solution, you will also see HOW the knights are positioned in the solution.

I hope I didn't comfuse you even more, I had to write English.

FrostNova

i will work it out as soon as possible : )

i thought before, it's very difficult to realise with backtracking because of the strange jumping-way of the horse. It's totally different from the queen.


And Hanoi ist a useful example in recursion.

Khan

Well, according to your description of the algorithmus, your big board is supposed to be 5x5 instead of (2n-1)^2, all position a knight can reach in a move ( a knight is no bishop or queen, which can go as far as the board allows). And is it really needed to research how far a knight can cover the board to solve the problem how many knights can be put on a board without conflicts? I think the two are seperate things. A knight can reach max 8 boxes in a 3x3 board, which according to your algorithmus leaves only the center box to put the second knight, but in fact 5 kights can be put in the board with 1 in the center 4 in each corner or in the middle of each ridge.

If I misunderstood your methode, would you please kindly remind me of it?

As to Honoi Tower, I'd like to say M=(N-1)^2-1, which may help the others to understand.

leexp82

<<your big board is supposed to be 5x5 instead of (2n-1)^2, all position a knight can reach in a <<move
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
you are right, (2n-1) is only useful in case the knight is allowed to make more than one move, which might be interesting in a generalized version of the problem. In case the knight moves once only, 5x5 will do.

>>A knight can reach max 8 boxes in a 3x3 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

This will not happen if you only allow one move, in this case, the bigger board will be 5x5.

<<which according to your algorithmus leaves only the center box to put the second knight, but in fact 5 kights can be put in the board with 1 in the center 4 in each corner or in the middle of each ridge.
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

you are confusing yourself with 2 sets of the rules for the same game:
#1# if you allow the knight to make infinitely many moves, all except the center can be reached. In this case, you can only put 2 knights onto this board.
#2# likewise, you will only be able to put 5 knights, if only 1 move is allowed.

But I do admit my solution and description is a little comfusing, as it is a generalized solution w.r.t. number of moves allowed and the manner of movement. eg. how many knights(or any other piece, such an imaginary piece that moves by a 2*5 block, in similar manner as a knight) can be placed on the board so that they won't get in each other's way in n moves.

In this case, where you allow one move only, you have to restrict the bigger board to 5x5, since that's how far a knight can ever after each move. But if more moves are allowed,  you will need a bigger board, AT MOST (2n-1)*(2n-1). that's what i didn't state clear enough earlier.

for a regular chessboard and regular chess pieces, you probably don't need a general solution as mine. A general solution is always correct, but too much effort for any one specific problem, therefore "almost" useless.

Khan

I fully agree with you on all the things till the relation of the two problems. I still think the connection of the two problems is weak and the algorithmuses applied to the two problems differ a lot from each other. But who cares? Whether two things are similiar or not is a matter of phylosophy. So thanks anyway!

Besides, I made a mistake. As to the Hanoi Tower, M = 2^(N-1)-1 instead of (N-1)^2-1

FrostNova

思路：题目问最多能放置几个马
只要在尽可能多的数量下给出一种成立的摆法就可以了

从1个马开始，不断加马，2，3，4……可用Backtracking 检验是否存在一种摆法，只要有那么一种摆法，则试试看，再加一个马，是否仍然有不冲突的摆法

加到32个马，都能找到一种不冲突的摆法

若再加一个马，到33个马，则回溯遍历整个棋盘，都无法找到不冲突的摆法
所以，得出32个马是最多，给出此时32个马的摆法，程序我过些时候附上

我觉得我一开始思路偏差，以我最初的算法，无法判断出是否马的数量为最多，而且效率极差

不过，大部分人，包括德国同学也是和我差不多想法，编出来后的程序运行了好几个小时，才得出最多的摆放数量