#1: 作者: 7thGuest, 时间: 2008-11-10 12:39

Problem:
On a 5x5 chess board, 5 black horses are on the top row, and 5 white on the bottom.
Please find a series of moves swap the positions of white and black horses.
Horse movement follows the standard chess rule ,no move out of board of course.
You DON'T have to move black/white in turns, at any step you can move any horse as long as the move is legal


Solution:
level1: write piece of code, solve the puzzle
level2: write piece of code, solve the puzzle fast
level3: write piece of code, solve the puzzle fast and with minimum steps of moves

#2: 作者: SARS, 时间: 2008-11-10 12:45

不懂国际象棋

马怎么个走法？和中国象棋的马一样，走横的或竖的“日”字？

#3: 作者: 7thGuest, 时间: 2008-11-10 12:48

yes, L shape move, but not 'block' rule like chinese chess

#4: 作者: deerlake, 时间: 2008-11-10 12:51

根据我的“人工智能”粗略想了一下，没有“绊马脚”的规则话，每只马走两步就可以了，总共16步。应该是最少的步数了吧，应为每只马不可能一步到位。

#5: 作者: deerlake, 时间: 2008-11-10 12:52

deerlake 写道:

根据我的“人工智能”粗略想了一下，没有“绊马脚”的规则话，每只马走两步就可以了，总共16步。应该是最少的步数了吧，因为任何一只马都不可能一步到位。

#6: 作者: 擎天柱, 时间: 2008-11-10 12:55

deerlake 写道:

根据我的“人工智能”粗略想了一下，没有“绊马脚”的规则话，每只马走两步就可以了，总共16步。应该是最少的步数了吧，应为每只马不可能一步到位。

I agree. 16 is the minimum.

#7: 作者: 擒流感, 时间: 2008-11-10 13:08

我想这里的swap是指黑1与白1互调，如此类推。。。这样远不止16步了

#8: 作者: bigbigloser, 时间: 2008-11-10 13:53

擒流感 写道:

我想这里的swap是指黑1与白1互调，如此类推。。。这样远不止16步了

There is no mark on black and white. I think all black are same. all white are same. I think swap means 4 whites swapping with 4 blacks.

16 steps should be enough.

1.

| B B B B
| _ W _ _
| _ _ _ _
| _ W W W

2.
| B B B B
| W W _ _
| _ _ _ _
| _ _ W W

3
| B B B B
| W W W _
|
| _ _ W _
4
| B B B B
| W W W W
| _ _ _ _
| _ _ _ _
5
| B _ B B
| W W W W
| B _ _ _
| _ _ _ _
6
| _ _ B B
| W W W W
| B B _ _
| _ _ _ _

7
| _ _ _ B
| W W W W
| B B _ B
| _ _ _ _
8
| _ _ _ _
| W W W W
| B B B B
| _ _ _ _
9
| _ _ W _
| _ W W W
| B B B B
| _ _ _ _
10
| _ _ W W
| _ _ W W
| B B B B
| _ _ _ _
11
| _ W W W
| _ _ W W
| B B B B
| _ _ _ _
12
| W W W W
| _ _ _ _
| B B B B
| _ _ _ _
13
| W W W W
| _ _ _ _
| _ B B B
| _ _ B _
14
| W W W W
| _ _ _ _
| _ _ B B
| _ _ B B
15
| W W W W
| _ _ _ _
| _ _ _ B
| B B B B

16
| W W W W
| _ _ _ _
| _ _ _ _
| B B B B

#9: 作者: deerlake, 时间: 2008-11-10 13:54

擒流感 写道:

我想这里的swap是指黑1与白1互调，如此类推。。。这样远不止16步了

"swap the positions of white and black horses."，没有要求一一对应。要是要求的话，例图上应该会标识。

#10: 作者: webdriver, 时间: 2008-11-10 14:03

deerlake 写道:

擒流感 写道: 我想这里的swap是指黑1与白1互调，如此类推。。。这样远不止16步了 "swap the positions of white and black horses."，没有要求一一对应。要是要求的话，例图上应该会标识。

可以当两种情况考虑好了
1）任意位置对换
2）指定位置对换