华容道求解器 klotski solver
好久好久没写代码了，前段时间打印了个华容道 (klotski) 玩玩，写个 solver 复健一下。
小时候一直有听说这玩意，也有同学带到学校过，短暂的下课上手试过，印象中很难。
人脑求解
手动尝试最有名的初始摆法，横刀立马，花了一个小时左右。稍微上手玩后可以发现一些规律，比如朝长边方向移动 2 格长的块后，一定是 2 块 1x1 的块填补空缺，又比如 1x1 的小块总是两两联合移动，否则后续难以进行。不过仅凭这些还不足以从繁多的可能中找到正解。经过一些尝试后，最后是靠盯住最大的 2x2 块，在保证它下一步能移动到更接近出口的方向的前提下，反推/猜测其他块的排布，然后再设法构造出这种盘面。这样一步一步推出，必然是绕了很多弯子，离最优解肯定差很远。
编程求解
观察到盘面的可能态总量并不大；对每个盘面，可能的移动方式也很少，一般是4种左右；最优解的步数并不算长 (100 左右)。很自然想到用 BFS 暴力求解。
为了方便编写，使用 2 维字符串数组 board 表示盘面状态，压平拼接成单个字符串做 hashKey，维护一个 hashTable (python 的字典类)，键为当前盘面，值为移动任意块1格，到达当前盘面的序列，记录搜索过的内容。
写好一些 helper function，比如 board 和 hashKey 的相互转换，检查是否求解完成，清晰画出盘面。接下来就是如何遍历节点的边 (即每个盘面中某块移动一格后所有可能的盘面)。移动总是发生在空格子周边，分成了两种情况编写：其一是块朝边长 1 的方向向空格移动 1 格；其二是对两个相连的空格，块朝边长 2 的方向向相连的空格移动 1 格。对4个方向和块沿移动方向的长度，分各种情况写好逻辑。
Fixing bugs, and it works.
一些可能的优化
hashTable 的值并不用保存整个移动列表，只需保存上一步的键，生成解法时只需链式查找即可，如此免去列表复制可以快速许多；用更快的语言，使用一些编码技巧，使用比字符串更简洁的数据做 hashKey，应该也能提高一些性能；然后就是省去 hashKey 和 board 列表的转换，只使用编码后的 hashKey 完成程序的逻辑，可读性会差一些，但相应的也会快一些。
以上这些都并未实现，查找出解也仅需 1s 左右，完全可以接受，所以就不做了。
普遍的步数计算方法，并不是计移动的格数，而是记方块移动的次数。像是 2x1 方块朝短边方向移动2格，或是 1x1 方块拐弯连续移动两格，都是记 1 步的。格数最优往往不是这种计法的最优，但多跑几个 loop，稍微加点代码计算方块移动次数就可以解决，不过懒得写了 (
附上代码：
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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
import operator
# 横刀立马
init = [['21', '22', '22', '21'],
['21', '22', '22', '21'],
['21', '12', '12', '21'],
['21', '11', '11', '21'],
['11', '00', '00', '11'],]
# 横竖皆将
# init = [["21", "22", "22", "21"],
# ["21", "22", "22", "21"],
# ["21", "12", "12", "11"],
# ["21", "12", "12", "11"],
# ["11", "00", "00", "11"]]
# possible moves
height = len(init)
width = len(init[0])
def nextState(board):
ret = []
for row in range(height):
for col in range(width):
if board[row][col] == '00':
# width = 1
# Up
i = row - 1
j = col
if i >= 0:
if board[i][j] == '11':
b = [l[:] for l in board]
b[row][col] = '11'
b[i][j] = '00'
key = toKey(b)
ret.append(key)
elif board[i][j] == '21':
b = [l[:] for l in board]
b[row][col] = '21'
b[i-1][j] = '00'
key = toKey(b)
ret.append(key)
# Down
i = row + 1
j = col
if i < height:
if board[i][j] == '11':
b = [l[:] for l in board]
b[row][col] = '11'
b[i][j] = '00'
key = toKey(b)
ret.append(key)
elif board[i][j] == '21':
b = [l[:] for l in board]
b[row][col] = '21'
b[i+1][j] = '00'
key = toKey(b)
ret.append(key)
# Left
i = row
j = col - 1
if j >= 0:
if board[i][j] == '11':
b = [l[:] for l in board]
b[row][col] = '11'
b[i][j] = '00'
key = toKey(b)
ret.append(key)
elif board[i][j] == '12':
b = [l[:] for l in board]
b[row][col] = '12'
b[i][j-1] = '00'
key = toKey(b)
ret.append(key)
# Right
i = row
j = col + 1
if j < width:
if board[i][j] == '11':
b = [l[:] for l in board]
b[row][col] = '11'
b[i][j] = '00'
key = toKey(b)
ret.append(key)
elif board[i][j] == '12':
b = [l[:] for l in board]
b[row][col] = '12'
b[i][j+1] = '00'
key = toKey(b)
ret.append(key)
# width = 2
# 2x1 blank
i = row + 1
j = col
if i < height and board[i][j] == '00':
if j-1 >= 0:
if board[i][j-1] == board[row][col-1] == '21':
legal = True
if row-1 >= 0 and i+1 < height:
if board[row-1][col-1] == board[i+1][j-1] == '21':
legal = False
if legal:
b = [l[:] for l in board]
b[i][j-1] = '00'
b[row][col-1] = '00'
b[row][col] = '21'
b[i][j] = '21'
key = toKey(b)
ret.append(key)
elif board[i][j-1] == board[row][col-1] == '22':
b = [l[:] for l in board]
b[i][j-2] = '00'
b[row][col-2] = '00'
b[i][j] = '22'
b[row][col] = '22'
key = toKey(b)
ret.append(key)
if j+1 < width:
if board[i][j+1] == board[row][col+1] == '21':
legal = True
if row-1 >= 0 and i+1 < height:
if board[row-1][col+1] == board[i+1][j+1] == '21':
legal = False
if legal:
b = [l[:] for l in board]
b[i][j+1] = '00'
b[row][col+1] = '00'
b[i][j] = '21'
b[row][col] = '21'
key = toKey(b)
ret.append(key)
elif board[i][j+1] == board[row][col+1] == '22':
b = [l[:] for l in board]
b[i][j+2] = '00'
b[row][col+2] = '00'
b[i][j] = '22'
b[row][col] = '22'
key = toKey(b)
ret.append(key)
# 1x2 blank
i = row
j = col + 1
if j < width and board[i][j] == '00':
if i-1 >= 0:
if board[i-1][j] == board[row-1][col] == '12':
legal = True
if col-1 >= 0 and j+1 < width:
if board[row-1][col-1] == board[i-1][j+1] == '12':
legal = False
if legal:
b = [l[:] for l in board]
b[i-1][j] = '00'
b[row-1][col] = '00'
b[i][j] = '12'
b[row][col] = '12'
key = toKey(b)
ret.append(key)
elif board[i-1][j] == board[row-1][col] == '22':
b = [l[:] for l in board]
b[i-2][j] = '00'
b[row-2][col] = '00'
b[i][j] = '22'
b[row][col] = '22'
key = toKey(b)
ret.append(key)
if i+1 < height:
if board[i+1][j] == board[row+1][col] == '12':
legal = True
if col-1 >= 0 and j+1 < width:
if board[row+1][col-1] == board[i+1][j+1] == '12':
legal = False
if legal:
b = [l[:] for l in board]
b[i+1][j] = '00'
b[row+1][col] = '00'
b[i][j] = '12'
b[row][col] = '12'
key = toKey(b)
ret.append(key)
elif board[i+1][j] == board[row+1][col] == '22':
b = [l[:] for l in board]
b[i+2][j] = '00'
b[row+2][col] = '00'
b[i][j] = '22'
b[row][col] = '22'
key = toKey(b)
ret.append(key)
return ret
# board to hashkey
def toKey(board):
return ''.join([''.join(l) for l in board])
# hashKey to board
def toBoard(key):
return [[key[2*(4*row+col):2*(4*row+col+1)] for col in range(width)] for row in range(height)]
# check if solved
def solved(board):
if board[4][1] == board[4][2] == '22':
return True
else:
return False
hashTable = {toKey(init): [toKey(init)]}
# draw board
def drawBoard(board):
for row in board:
for elem in row:
if elem == '22':
c='曹'
elif elem == '21':
c='丨'
elif elem == '12':
c='一'
elif elem == '11':
c='兵'
else:
c=' '
print(c, end='')
print('', end='\n')
print()
# draw moves
def drawMoves(key):
for (i, k) in enumerate(hashTable[key]):
print(i)
drawBoard(toBoard(k))
loop = True
buf1 = [(toKey(init), [toKey(init)])]
for i in range(200):
if loop:
print(i, len(hashTable))
buf = []
for (key, val) in buf1:
nxt = nextState(toBoard(key))
for newKey in nxt:
if newKey in hashTable:
pass
else:
if not newKey in map(operator.itemgetter(0), buf):
buf.append((newKey, hashTable[key] + [newKey]))
for (k, v) in buf:
hashTable[k] = v
if solved(toBoard(k)):
print("final state:", len(hashTable[k]) - 1, k)
loop = False
buf1 = buf[:]
This post is licensed under
CC BY 4.0
by the author.
Comments powered by Disqus.