首先，我將解釋 peg solitaire 的規則（對于 1 維）：您最初從長度為 n 的 1 維板開始。n-1 個元素是釘子（填充），1 個元素是孔（空）。因此，起始位置可以是[1, 1, 0, 1, 1, 1]1 代表釘子，0 代表孔n = 6
游戲的目標是達到一個棋盤狀態，其中 n-1 個元素是孔，1 個元素是任何給定位置的釘子。所以一個有效的解決方案可以[0, 0, 0, 1, 0, 0]是n = 6
您在任何給定位置的可用移動是當且僅當兩個位置之間有一個釘子時，將一個釘子向右或向左移動兩個位置，然后一旦您移動，用一個孔替換中間釘子。
因此，對于諸如此類的棋盤，board = [0, 1, 1, 0, 1, 1, 0]有兩個可用的動作。
- 移動
board[1]到board[3]并設定board[2] = 0 - 移動
board[5]到board[3]并設定board[4] = 0 - 移動
board[2]到board[0]并設定board[1] = 0 - 移動
board[4]到board[6]并設定board[5] = 0
我正在嘗試制作的演算法的目標是輸入 n ，其中 n > 2 且 n 是偶數，然后對于長度為 n 的板，找到可以在其中孔的起始狀態的所有位置放置以產生有效的解決方案。
我創建了一個蠻力演算法，它可以找到所有可能的移動，直到達到有效的解決方案，但是它開始需要很長時間才能找到超過 n > 20 的解決方案。所以我想知道是否有一些優化我可以做或不同的解決方法。
這是我的代碼：
import re
def generateBoard(n):
return [1]*n
def solve(board):
if checkBoard(board):
return True
elif checkUnsolvable(board):
return False
moves = []
for i in range(len(board)):
if i < len(board)-2:
if board[i] and board[i 1] and not board[i 2]:
moves.append((i, 'right'))
if i > 1:
if board[i] and board[i-1] and not board[i-2]:
moves.append((i, 'left'))
for move in moves:
newBoard = makeMove(board, move)
if solve(newBoard):
return True
continue
return False
def makeMove(board, move):
index, direction = move
b = [element for element in board]
if direction == 'right':
b[index] = 0
b[index 1] = 0
b[index 2] = 1
elif direction == 'left':
b[index] = 0
b[index-1] = 0
b[index-2] = 1
return b
def checkBoard(board):
if sum(board) == 1:
return True
return False
def checkUnsolvable(board):
expression1 = '1000 1' #RE for a proven to be unsolvable board
expression2 = '00100' #RE for a proven to be unsolvable board
string = ''.join([str(element) for element in board])
if re.search(expression1, string) or re.search(expression2, string):
return True
return False
def countSolutions(board):
indices = []
for i in range(len(board)):
b = [element for element in board]
b[i] = 0
if solve(b):
indices.append(i 1)
return indices
n = int(input())
print(countSolutions(generateBoard(n)))
到目前為止我提出的優化：
- 一個板包含
[1, 0, 0, ..., 0, 1]是無法解決的。所以當我們找到這種模式時，我們跳過 - 對于包含
[0, 0, .. 0, 1, 0, 0, ..,0] - 我們只需要檢查棋盤的一半，因為另一半的解是對稱的。
但盡管如此，代碼仍然很慢。
uj5u.com熱心網友回復：
本研究論文介紹了這種紙牌游戲演算法：https ://arxiv.org/pdf/math/0006067.pdf 。
它聲稱存在線性時間演算法。
一個有效的解決方案如下所示：
L = 1 or 011 or 110 or 11 (01)* [ 00 | 00(11) | (11) 00 | (11)*1011 | 1101(11)* ] (10)*11 # (A) or 11 (01)* (11)* 01 # (B) or 10 (11)* (10)* 11 # (C)
要解決 A，您可以使用正則運算式來檢查字串。但是，由于中間部分，它有多種情況。
第一種情況：11(01)*00(10)*11
第二種情況：11(01)*(00)(11) (10)*11
第三種情況：11(01)*(11) (00)(10)*11
第四種情況：第三種情況11(01)*(11)*(1011)(10)*11
：11(01)*1101(11)*(10)*11
解決 B 和 C 是一個更簡單的正則運算式匹配：
B11(01)*(11)*01
的解決方案： C 的解決方案：10(11)*(10)*11
如果匹配（但您需要將其轉換為字串，''.join([str(i) for i in mylist])例如）1、011、110或上述任何模式，那么它將是可解的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/464733.html
上一篇：用亂數填充向量