优化我的 1D peg 纸牌解决方案

Question

首先我会解释一下接龙的规则（对于1维）：您最初从长度为 n 的一维板开始。 n-1 个元素是钉子（填充），1 个元素是孔（空）。因此起始位置可以是 [1, 1, 0, 1, 1, 1]，其中 1 代表钉子，0 代表 n = 6

的洞

游戏的目标是达到棋盘状态，其中 n-1 个元素是洞，1 个元素是任意给定位置的木桩。所以一个有效的解决方案可以是 [0, 0, 0, 1, 0, 0] for 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]
我们只需要检查一半的棋盘，因为另一半的解是对称的。

但尽管如此，代码仍然很慢。

Answer 1

这篇研究论文介绍了这种纸牌游戏算法：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是一个更简单的正则表达式匹配：

B 的解决方案：11(01)*(11)*01
C 的解决方案：10(11)*(10)*11

如果匹配（不过需要将其转换为字符串，例如 ''.join([str(i) for i in mylist])）1、011、110 或任何上面的模式，那么它是可以解决的。

优化我的 1D peg 纸牌解决方案

Optimizing my solution for 1D peg solitaire

python

algorithm