【文末福利】黑白子交换

01/08 13:49
阅读数 66

1.问题描述

有三个白子和三个黑子如图7.1所示布置。


图7.1  初始位置

游戏的目的是用最少的步数将图7.1中白子和黑子的位置进行交换,使得最终结果如图7.2所示。


图7.2  最终位置

游戏的规则是:

(1)一次只能移动一个棋子;

(2)棋子可以向空格中移动,也可以跳过一个对方的棋子进入空格;

(3)白色棋子只能往右移动,黑色棋子只能向左移动,不能跳过两个子。

请用计算机实现上述游戏。

2.问题分析

计算机解决胜这类问题的关键是要找出问题的规律,或者说是要制定一套计算机行动的规则。分析本题,先用人来解决问题,可总结出以下规则:

  • 黑子向左跳过白子落入空格,转(5);

  • 白子向右跳过黑子落入空格,转(5);

  • 黑子向左移动一格落入空格(但不应产生棋子阻塞现象),转(5);

  • 白子向右移动一格落入空格(但不应产生棋子阻塞现象),转(5);

  • 判断游戏是否结束,若没有结束,则转(1)继续。

所谓的“阻塞”现象指的是:在移动棋子的过程中,两个尚未到位的同色棋子连接在一起,使棋盘中的其他棋子无法继续移动。

例如,按下列方法移动棋子(“○”代表白子,“●”代表黑子,“△”代表空格):

0:○ ○ ○ △ ● ● ●

1:○ ○ △ ○ ● ● ●

2:○ ○ ● ○ △ ● ●

3:○ ○ ● △ ○ ● ●

4:两个●连在一起产生阻塞

○ ○ ● ● ○ △ ●

或两个○连在一起产生阻塞

○ △ ● ○ ○ ● ●

产生阻塞的现象的原因是在第2步时,棋子○不能向右移动,只能将●向左移动。

总结产生阻塞的原因,当棋盘出现“黑、白、空、黑”或“白、空、黑、白”状态时,不能向左或向右移动中间的棋子,只移动两边的棋子。按照上述规则,可以保证在移动棋子的过程中,不会出现棋子无法移动的现象,且可以用最少的步数完成白子和黑子的位置交换。

3.算法设计

可以有四种移动方式(“○”代表白子,“●”代表黑子,“△”代表空格,“~”代表任意):

白棋跳过黑棋:~ ○ ● △ ~ ~ ~

黑棋跳过白棋:~ ~ △ ○ ● ~ ~

白棋移向空格:~ ~ ~  ○ △ ~ ~

黑棋移向空格:~ ~ ~  △ ● ~ ~

(1)黑白棋要是能跳,则先跳

根据游戏规则,如果出现下列情况1,黑棋不能往右,此时只能白棋跳过黑棋往右;同样如果出现下列情况2,白棋不能往左,此时只能黑棋跳过白棋往左。

情况1:~ ○ ● △ ○ ~ ~

情况2:~ ● △ ○ ● ~ ~

是否存在黑棋既能往左跳,存在白棋又可往右跳的可能性呢?即,情况3或情况4同时存在的现象。

情况3:~ ○ ● △ ○ ● ~

情况4:○ ● △ ○ ● ~ ~

事实证明这两种情况是存在的。

(2)棋子只能移动时

①若向右移动白子不会产生阻塞,则白子向右移动,分i=1和i>1两种情况:

  • i=1时,白棋只能往右移:

○ △ ~ ~ ~ ~ ~

  • i>1时,i处的白棋只有在i-1和i+2位置上的棋子不同时才能往右移动,即情况5或情况6。

情况5:~ ● ○ △ ○ ~ ~

情况6:~ ○ ○ △ ● ~ ~

分析:如果i-1和i+2位置上的棋子相同时,即情况7。

情况7:~ ~ ● ○ △ ● ~

如果将白子(“○”)向左移动到空格(“△”)处,会转变成情况8。如果在情况7时,第二个任意子(“~”)位置是白子(“○”),白子跳过黑子右移,会出现两个白子相连的情况,如情况9,将产生阻塞;或者出现倒数第二个黑子跳过白子左移,出项两个黑子相连的情况,如情况10,同样产生阻塞。

情况8:~ ~ ● △ ○ ● ~

情况9:~ △ ● ○ ○ ● ~

情况10:~ ~ ● ● ○ △ ~

相应代码如下:

i = 0
while flag and i < 5:  # 若白子可以向右跳过黑子,则白子向右跳
    if t[i] == 1 and t[i + 1] == 2 and t[i + 2] == 0:

②若向左移动黑子不会产生阻塞,则黑子向左移动 ,分i=5和i>1两种情况:

  • i=5,黑棋只能往左移:

    ~ ~ ~ ~ ~ △ ●

  • i>1时,i+1处的黑棋只有在i-1和i+2位置上的棋子不同时才能往左移动,即,情况11或情况12。

情况11:~ ○ △ ● ● ~ ~

情况12:~ ● △ ● ○ ~ ~

相应代码如下:

i = 0
while flag and i < 5:  # 若黑子可以向左跳过白子,则黑子向左跳
    if t[i] == 0 and t[i + 1] == 1 and t[i + 2] == 2:

4.完整程序

根据上面的分析,编写程序如下:

#!/usr/bin/python3
# -*- coding: utf-8 -*- 
# @author : liuhefei
# @Time : 2019/7/13 10:07 
# @desc: 黑白子交换


# 打印输出结果
def printLine(a):
    global number


    print("No. %2d:……………………….." % number)
    number += 1
    print(" ", end='')


    for i in range(7):
        if a[i] == 1:
            print('| * ', end='')
        else:
            if a[i] == 2:
                print('| @ ', end='')
            else:
                print('|  ', end='')
    print(" |\n ………………………..\n")


# 交换
def change(t, i, j):
    term = t[i]
    t[i] = t[j]
    t[j] = term
    return t




if __name__ == '__main__':
    t = [1, 1, 1, 0, 2, 2, 2]  # 初始化数组 1:白子 2:黑子 0:空格
    number = 0
    printLine(t)
    # 若还没有完成棋子的交换则继续进行循环
    while t[0] + t[1] + t[2] != 6 or t[4] + t[5] + t[6] != 3:  # 判断游戏是否结束
        # flag为棋子移动一步的标记,flag=True表示尚未移动棋子,flag=Flase表示已经移动棋子
        flag = True


        i = 0
        while flag and i < 5:  # 若白子可以向右跳过黑子,则白子向右跳
            if t[i] == 1 and t[i + 1] == 2 and t[i + 2] == 0:
                t = change(t, i, i + 2) # 调用交换
                printLine(t)
                flag = False
            i += 1


        i = 0
        while flag and i < 5:  # 若黑子可以向左跳过白子,则黑子向左跳
            if t[i] == 0 and t[i + 1] == 1 and t[i + 2] == 2:
                t = change(t, i, i + 2)
                printLine(t)
                flag = False
            i += 1


        i = 0
        while flag and i < 6:  # 若向右移动白子不会产生阻塞,则白子向右移动
            f = True
            if i < 5:
                f = t[i - 1] != t[i + 2]
            if t[i] == 1 and t[i + 1] == 0 and (i == 0 or f):
                t = change(t, i, i + 1)
                printLine(t)
                flag = False
            i += 1


        i = 0
        while flag and i < 6:  # 若向左移动黑子不会产生阻塞,则黑子向左移动
            f = True
            if i < 5:
                f = t[i - 1] != t[i + 2]
            if t[i] == 0 and t[i + 1] == 2 and (i == 5 or f):
                t = change(t, i, i + 1)
                printLine(t)
                flag = False
            i += 1

5.运行结果

在PyCharm下运行程序,结果如图7.3所示。

E:\code\python\Interest-python\venv\Scripts\python.exe
No.  0:………………………..
| * | * | * |  | @ | @ | @  |
………………………..
No.  1:………………………..
| * | * |  | * | @ | @ | @  |
………………………..
No.  2:………………………..
| * | * | @ | * |  | @ | @  |
………………………..
No.  3:………………………..
| * | * | @ | * | @ |  | @  |
………………………..
No.  4:………………………..
| * | * | @ |  | @ | * | @  |
………………………..
No.  5:………………………..
| * |  | @ | * | @ | * | @  |
………………………..
No.  6:………………………..
|  | * | @ | * | @ | * | @  |
………………………..
No.  7:………………………..
| @ | * |  | * | @ | * | @  |
………………………..
No.  8:………………………..
| @ | * | @ | * |  | * | @  |
………………………..
No.  9:………………………..
| @ | * | @ | * | @ | * |   |
………………………..
No. 10:………………………..
| @ | * | @ | * | @ |  | *  |
………………………..
No. 11:………………………..
| @ | * | @ |  | @ | * | *  |
………………………..
No. 12:………………………..
| @ |  | @ | * | @ | * | *  |
………………………..
No. 13:………………………..
| @ | @ |  | * | @ | * | *  |
………………………..
No. 14:………………………..
| @ | @ | @ | * |  | * | *  |
………………………..
No. 15:………………………..
| @ | @ | @ |  | * | * | *  |
………………………..




Process finished with exit code 0

图7.3  运行结果

推荐阅读

《趣学python算法100例》


***粉丝福利时间***

评论区留言,点赞数前6可获得此书!!!

72个小计!

注:若是在活动截止日期后24小时内无法取得用户回复或联系,将按照留言点赞排名顺延。


展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部