我一直在玩我最近試圖解決的
請注意，坐標系是 (-y,x)。例如，(6,6) 表示向下 7 個空格，向右 7 個空格，然后單擊該方塊。
當有更多顏色時，我一直遇到問題，例如 6 種顏色而不是 2 種顏色，因為程式似乎永遠無法完成解決。
因此，我想知道是否有比隨機暴力破解更好的方法（可能是演算法？），以及是否有辦法確定開始游戲狀態是否可解決。
感謝您通讀。
uj5u.com熱心網友回復：
我實際上認為這是一個有趣的游戲，所以我寫了一個快速解決方案：
- 定義游戲，以便您可以玩它
- 通過構建所有可能動作的樹來解決游戲（沒有重復）
- 告訴您游戲所需的最少移動次數是多少，并向您顯示結果步驟（對于可能的解決方案之一）
編輯：我發布的第一個版本實際上并沒有洗掉空列并允許移動 1 個塊 - 所以我在這里更新了答案，但同樣的主要思想。
import random
# plays and solves http://g.fromgame.com/game/13/
class Game:
def __init__(self, width, height, colours=2):
self.width = width
self.height = height
self.colours = colours
self.board = [[0 for __ in range(width)] for __ in range(height)]
def generate(self, seed=0):
# very naive way to generate a board,
# heavily biased towards horizontal runs, not really important
random.seed(seed)
self.board = []
while len(self.board) < self.width * self.height:
self.board.extend([random.randint(0, self.colours)] * random.randint(1, self.width // 2))
self.board = [self.board[i*self.width:(i 1)*self.width] for i in range(self.height)]
self.drop()
def drop(self):
# simply gravity, keeps dropping blocks until they are all at the 'bottom'
dropped = True
while dropped:
dropped = False
for lower, above in zip(reversed(self.board), list(reversed(self.board))[1:]):
for i in range(len(lower)):
if lower[i] == 0 and above[i] != 0:
lower[i] = above[i]
above[i] = 0
dropped = True
# move columns to the left, leaving no empties
rc = [i for i, c in enumerate(self.board[-1]) if c == 0]
self.board = [[c for i, c in enumerate(line) if i not in rc] [0 for __ in range(len(rc))] for line in self.board]
def copy(self):
# returns a completely new copy of this game
game = self.__class__(self.width, self.height, self.colours)
game.board = [line.copy() for line in self.board]
return game
def print(self):
for line in self.board:
print(''.join(map(str,line)))
def get_move(self, start_x, start_y):
# returns all the pairs x, y that would be removed if the block at x, y is removed
if self.board[start_y][start_x] == 0:
return []
colour = self.board[start_y][start_x]
queue = [(start_x, start_y)]
result = {(start_x, start_y)}
def add(a, b):
if (a, b) not in result and self.board[b][a] == colour:
result.add((a, b))
queue.append((a, b))
while queue:
x, y = queue.pop(0)
if x 1 < self.width:
add(x 1, y)
if y 1 < self.height:
add(x, y 1)
if x-1 >= 0:
add(x-1, y)
if y-1 >= 0:
add(x, y-1)
return result
def get_all_moves(self):
# finds a set of all possible moves (as tuples of moves that are all the same move)
moves = set()
for y in range(self.height):
for x in range(self.width):
if self.board[y][x] > 0 and not any((x, y) in m for m in moves):
m = self.get_move(x, y)
# only moves of more than one block are valid
if len(m) > 1:
moves.add(tuple(m))
return moves
def make_move(self, move):
for x, y in move:
self.board[y][x] = 0
self.drop()
def check_won(self):
# returns whether the game has been completed assumes all positive colours
return sum(sum(line) for line in self.board) == 0
def play(self):
# trivial if there's nothing on the board, win in 0 moves, 1 path, empty moves
if self.check_won():
return 0, 1, {}
# otherwise play all possible moves until conclusion
moves = {}
size = self.width * self.height
min_d = size # worst case as many moves as squares
total = 0
for move in self.get_all_moves():
next_state = self.copy()
next_state.make_move(move)
d, n, rest = next_state.play()
# only save the move if there's a way to win the game after this move
if d < size:
moves[(move[0], d)] = rest
total = n
min_d = min(min_d, d 1)
return min_d, total, moves
def main():
g = Game(4, 5)
g.generate(seed=1)
print('Start of the game:')
g.print()
min_moves, paths, moves = g.play()
if min_moves == g.width * g.height:
print('Game cannot be won!')
else:
g_copy = g.copy()
print(f'The first winning play in {min_moves} moves, out of {paths} possible different games:')
options = moves
n = min_moves
x, y = 0, 0
next_options = {}
while n > 0:
for ((x, y), c), next_options in options.items():
if c == n:
break
print(f'Make move {(x, y)}:')
g_copy.make_move(g_copy.get_move(x, y))
g_copy.print()
n -= 1
options = next_options
if __name__ == '__main__':
main()
這用一塊 4x5 的小棋盤玩游戲，輸出：
Start of the game:
0101
0111
1122
1121
2211
The first winning play in 3 moves, out of 11 possible different games:
Make move (2, 3):
0100
0101
1101
1111
2211
Make move (2, 4):
0000
0000
0000
0000
2200
Make move (0, 4):
0000
0000
0000
0000
0000
請注意，它從左上角到右下角對板進行編號，因此在此示例中，0,0 是左上角，4,5 是右下角。設定了隨機種子，因此每次運行時都會得到相同的結果，盡管不一定在每臺計算機上都運行相同的游戲，這取決于隨機的實作 -如果需要更多可重復性，可以添加.save()and函式。.load()
請注意，您的問題的答案實際上只是play方法以及get_move和get_all_moves方法 - 它顯示了如何構建可能的移動樹，深度優先和回溯（使用遞回 - 因此通過遞回深度限制棋盤大小，它是可行的但如果沒有遞回，可讀性會差一些）。
還要注意，在這行之后：min_moves, paths, moves = g.play()，moves包含所有可能動作的完整樹，給定游戲g，玩到結論。值得在除錯器中查看實際生成的內容 - 它太大，無法在此處列印。
要查看每種長度的解有多少：
from collections import defaultdict
counts = defaultdict(int)
def count(ms, n):
for m, k in ms:
if k == 0:
counts[n] = 1
else:
count(ms[(m, k)], n 1)
count(moves, 0)
print(counts)
對于這個例子：
defaultdict(<class 'int'>, {2: 7, 3: 4})
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/415946.html
標籤：
上一篇：如果飛鏢中有[1::]？
下一篇：陣列中有多少個數小于或等于x？