IT小白

这个屌丝很懒，什么也没留下！

热门标签

python解最强大脑：黑白迭代_最强大脑黑白重叠游戏原理

作者：IT小白 | 2024-02-22 10:07:55

踩

最强大脑黑白重叠游戏原理

文章目录

黑白迭代规则
解法分析
可视化
代码实现
效果
复杂度分析

本文思路参考https://zhuanlan.zhihu.com/p/152349573

黑白迭代规则

（已经看过的可以直接跳到下一部分了）

B站视频：

最强大脑：B圈S圈层破圈突围赛，一对一挑战“黑白迭代”

解法分析

重要性质

黑白迭代游戏有以下几个重要性质：

所有方格只有两种状态：白和黑，程序中可以定义为BLACK和WHITE
最终状态与操作的顺序无关。(即random.shuffle了也没事)
同一方格改变偶数次状态后，不改变状态；同一方格改变奇数次状态，相当于只改变了一次状态。

简化问题

由空白盘面构造目标盘面，也可以简化为从目标盘面还原空白，两者操作顺序相同。

公式法

这时我们需要寻找一种只翻转某个特定方格，其余方格不变的公式。
设 $X_{\left( a,b\right) }$ 为只翻转(a, b)位方格的解法。

上图中，将找到的 $X_{\left( 8,3\right) }$ 与 $X_{\left( 8,4\right) }$ 合并，即可消除。

合并多个公式

根据黑白迭代的性质3，可根据偶消奇不消的规则将其整合成一个解法。
通过观察发现，这一规则实际上就是异或(XOR)

推导公式

点击(0, 0)后，出现三个黑色点，如下图所示：

根据合并解法的方法，可列出如下等式：

$X_{\left( 0,0\right) } \veebar X_{\left( 0,1\right) } \veebar X_{\left( 1,0\right) } = [ [1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0] ]$

$\veebar$ 表示异或

所以，可列出64个异或方程：

$X_{\left( 0,0\right) } \veebar X_{\left( 0,1\right) } \veebar X_{\left( 1,1\right) } \veebar {\left( 1,2\right) } = [ [0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0] ]$

$. . .$

$X_{\left( 7,7\right) } \veebar X_{\left( 7,6\right) } \veebar X_{\left( 6,7\right) } = [ [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1] ]$

用高斯消元法解这个方程组，得到答案。

高斯消元法

高斯消元解异或方程组的方法不介绍了，这里分析具体算法。
由于64个未知数的解是一个矩阵，为了简化计算，可以将矩阵转化为数字。
例如，下面的矩阵：

[
     [1, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0]
]
1
2
3
4
5
6
7
8
9
10

可以转变为如下二进制数，方便按位异或计算:

0b1000000000000000000000000000000000000000000000000000000000000000000000000000000000
1

解出X的值后，将整数转为二进制，不够64位前面补0，获得矩阵。

可视化

用pygame简单写一个，用到的黑白方块：

将上图保存为black.bmp和white.bmp

代码实现

项目结构

如下所示：

solve.py

解法部分，如下：

from math import ceil
from typing import List, Tuple

# 定义各种类型标注
SolveType = List[Tuple[int, int]]
BoardType = List[List[int]]
EquationType = List[Tuple[List[Tuple[int, int]], Tuple[int, int]]]

WIDTH = 8   # 格数
WHITE, BLACK = 0, 1


def get_blank_board():  # 获取一个空白盘面
    return [[WHITE] * WIDTH for _ in range(WIDTH)]


def get_periphery(x: int, y: int):  # 求所有周边点，包括自己
    res = [(x, y)]
    for tx, ty in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        nx, ny = x + tx, y + ty
        if 0 <= nx < WIDTH and 0 <= ny < WIDTH:
            res.append((nx, ny))
    return res


def equation():  # 列异或方程组
    res = []
    for x in range(WIDTH):
        for y in range(WIDTH):
            periphery = get_periphery(x, y)
            res.append((periphery, (x, y)))
    return res


def chunk(x: list, step: int):  # 按步长切割列表x
    step = int(step)
    return list(
        map(
            lambda n: x[n * step: n * step + step],
            list(range(0, ceil(len(x) / step)))
        )
    )


def gaussian(equ: EquationType):  # 异或方程组转矩阵
    matrix = []  # 增广矩阵
    # 系数1 系数2 ... 系数64 等号右侧
    for xs, pos in equ:
        p = []
        for x, y in xs:
            p.append(x * WIDTH + y)
        a = [0] * (WIDTH * WIDTH)
        for i in p:
            a[i] = 1  # 系数只有1或0
        a.append(array_to_int([pos]))  # 右端常数
        matrix.append(a)
    return matrix


def array_to_int(array: SolveType):  # 解法转十进制整数
    board = get_blank_board()
    for x, y in array:
        board[x][y] = BLACK
    flatten = lambda x: [y for L in x for y in flatten(L)] if type(x) is list else [x]   # 碾平二维列表
    a = flatten(board)
    del flatten
    res = [0] * (WIDTH * WIDTH)
    for inx, item in enumerate(a):
        if item == BLACK:
            res[inx] = 1
    res = ''.join(str(i) for i in res)   # 矩阵转二进制
    return int(res, base=2)   # 二进制转整数


def int_to_array(n: int):   # 十进制整数转解法
    lst = list(bin(n).replace('0b', ''))
    lst = ['0'] * (WIDTH * WIDTH - len(lst)) + lst   # 补0
    board = [0] * (WIDTH * WIDTH)
    for inx, item in enumerate(lst):
        if item == '1':
            board[inx] = BLACK
    board = chunk(board, WIDTH)
    return board
    

def guass(n: int, matrix: BoardType):  # 高斯消元法解异或方程组
    r = 0
    for c in range(n):
        t = r
        for i in range(r, n):  # 找1
            if matrix[i][c] == 1:
                t = i
                break
        
        if matrix[t][c] == 0:
            continue
        matrix[r], matrix[t] = matrix[t], matrix[r]  # 交换两行
        
        for i in range(r + 1, n):  # 1与r行异或
            if matrix[i][c] == 1:
                for j in range(c, n + 1):
                    matrix[i][j] ^= matrix[r][j]  # 合并
        
        r += 1
    
    if r < n:  # 这个BUG只在30阶出现
        for i in range(r, n):
            if matrix[i][n] == 1:
                raise SystemExit('方程组无解')
        raise SystemExit('方程组有多组解')
    
    for i in range(n - 1, -1, -1):  # 注意是倒序
        for j in range(i):
            if matrix[j][i] == 1:
                matrix[j][n] ^= matrix[i][n]
    
    for i in range(n):
        yield matrix[i][n]


def solve():  # 获取解方程的结果
    m = gaussian(equation())
    res = {}  # 哈希表存储
    for inx, num in enumerate(guass(WIDTH * WIDTH, m)):
        val = int_to_array(num)
        x, y = inx // WIDTH, inx % WIDTH  # 一维转二维公式
        res[(x, y)] = val
    return res


def merge(a: BoardType, b: BoardType):  # 合并两组解，实际上就是异或
    if not a:
        return b
    if not b:
        return a
    res = get_blank_board()
    for x, i in enumerate(a):
        for y, j in enumerate(i):
            k = b[x][y]
            if k == j:  # 异或核心
                res[x][y] = WHITE
            else:
                res[x][y] = BLACK
    return res
    

def get(board: BoardType):  # 主函数
    solution = solve()
    res = []
    for x, i in enumerate(board):
        for y, j in enumerate(i):
            if j == BLACK:
                res.append(solution[(x, y)])
    ans = []
    for i in res:
        ans = merge(ans, i)  # 合并解法，减少空间和可视化消耗
    
    res = []
    for x, i in enumerate(ans):
        for y, j in enumerate(i):
            if ans[x][y] == BLACK:
                res.append((x, y))
    return res


if __name__ == '__main__':
    test = [
        [0, 0, 1, 0, 0, 1, 0, 0],
        [0, 1, 0, 0, 0, 0, 1, 0],
        [0, 0, 0, 1, 1, 0, 0, 0],
        [1, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 0, 0, 1, 0, 1],
        [0, 1, 1, 0, 0, 1, 1, 0],
        [1, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 1, 1, 1, 0, 1]
    ]  # 节目最难的第三题
    print(get(test))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177

gui.py

可视化部分，如下：

import sys
import os

import pygame
from pygame.locals import *

from solve import *

BLACK_PATH = os.path.join('resources', 'black.bmp')  # 黑色图路径
WHITE_PATH = os.path.join('resources', 'white.bmp')
GRID_WIDTH = 40
SPEED = 5  # 显示速度，越高越慢
FPS = 60  # 帧率


def destroy():
    pygame.quit()
    sys.exit(0)


class Window(object):
    def __init__(self, solution: SolveType):
        pygame.init()  # 必不可少
        self.solution = solution
        
        self.screen = pygame.display.set_mode((GRID_WIDTH * WIDTH, GRID_WIDTH * WIDTH))
        pygame.display.set_caption('黑白迭代可视化')
        
        self.board = get_blank_board()
        self.black = pygame.image.load(BLACK_PATH)
        self.white = pygame.image.load(WHITE_PATH)
        
        self.inx = 0   # 播放索引
        self.clock = pygame.time.Clock()
        
    def draw_board(self):
        for r, i in enumerate(self.board):
            for c, j in enumerate(i):
                x, y = c * GRID_WIDTH, r * GRID_WIDTH  # 特别注意：c和r不能反
                if j == WHITE:
                    self.screen.blit(self.white, (x, y))
                if j == BLACK:
                    self.screen.blit(self.black, (x, y))
                    
    def reverse(self, x: int, y: int):
        lst = [(x, y)]
        for tx, ty in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            nx, ny = x + tx, y + ty
            if 0 <= nx < WIDTH and 0 <= ny < WIDTH:
                lst.append((nx, ny))
        for nx, ny in lst:
            self.board[nx][ny] = WHITE if self.board[nx][ny] == BLACK else BLACK
        
    def show(self):
        rates = 0
        while True:
            self.clock.tick(FPS)
            for event in pygame.event.get():
                if event.type == QUIT:
                    destroy()
            if rates % SPEED == 0:
                if self.inx >= len(self.solution):  # 溢出，结束
                    break
                self.reverse(*self.solution[self.inx])  # 翻转
                self.inx += 1
            rates += 1
            self.draw_board()
            pygame.display.update()
        while True:  # 第二循环，显示复原结果
            self.clock.tick(FPS)
            for event in pygame.event.get():
                if event.type == QUIT:
                    destroy()
            self.draw_board()
            pygame.display.update()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

main.py

入口程序，如下：

from gui import Window
from solve import get

test = [
    [0, 0, 1, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 1, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 1, 0, 1],
    [0, 1, 1, 0, 0, 1, 1, 0],
    [1, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 1, 1, 0, 1]
]  # 节目最难的第三题

solution = get(test)

Window(solution).show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

效果

复杂度分析

这里指解法部分。
设n为边长（阶数），高斯消元法时间复杂度 $O(n^{3})$
而一共要求解 $n^{2}$ 个格子的解法，所以时间复杂度为 $O(n^{5})$ 。

在最坏情况下（全部变黑），需要 $n^{2}$ 的空间，空间复杂度 $O(n^{2})$

	最好情况	最坏情况
时间复杂度	$O(n^{5})$	$O(n^{5})$
空间复杂度	$O (1)$	$O(n^{2})$

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/129639

python解最强大脑： 黑白迭代_最强大脑黑白重叠游戏原理