求解器

Question

如果您不熟悉逻辑益智游戏Takuzu，我就学会了如何玩它，并从这个挑战发布在reddit上中得到了灵感来完成这个项目。这个游戏的简短版本是，它是一个逻辑难题，在n×n网格上使用0和1s，它不允许一行中三个重复的数字，也不允许两行或两列相同。

如果可能的话，我希望得到关于风格、变量命名和效率可以提高的领域的建议。我特别想对其中一个功能提出建议，那就是build_perms。它是功能性的，并产生我想要的结果，但是它是用多层嵌套列表实现的。我也想知道我是否对清单的理解过分了。我以前没有广泛地使用过它们，所以我认为这可能是一个很好的学习方法。不管是哪种方式，这里都是一个项目：

import re, itertools, copy

def rotate_right(puzzle):
    """
    Rotates the puzzle right thus making
    our columns into our rows and vice versa
    """
    return [''.join(t) for t in zip(*puzzle[::-1])]

def rotate_left(puzzle):
    """
    Rotates the puzzle left thus making
    our rows back into our columns
    """
    return [''.join(t) for t in list(zip(*puzzle))[::-1]]

def replace_twos(line):
    """
    An easy placement of alternating numbers. 
    Helps fill out the initial board
    """
    line = line.replace('.00.', '1001')
    line = line.replace('00.', '001')
    line = line.replace('.00', '100')

    line = line.replace('.11.', '0110')
    line = line.replace('11.', '110')
    line = line.replace('.11', '011')

    line = line.replace('1.1', '101')
    line = line.replace('0.0', '010')

    return line

def half_filled(line):
    """
    Fills all .s with the opposite number
    if the board has half already filled
    """
    if line.count('1') == (len(line) // 2):
        line = line.replace('.', '0')
    elif line.count('0') == (len(line) // 2):
        line = line.replace('.', '1')

    return line

def solve_partial(puzzle):
    """
    Finds rows and columns that match a 
    criteria and replaces them 
    """
    for i in range(len(puzzle)):
        puzzle[i] = replace_twos(puzzle[i])
        puzzle[i] = half_filled(puzzle[i])

    rot_puzzle = rotate_right(puzzle)
    for i in range(len(rot_puzzle)):
        rot_puzzle[i] = replace_twos(rot_puzzle[i])
        rot_puzzle[i] = half_filled(rot_puzzle[i])

    puzzle = rotate_left(rot_puzzle)

    return puzzle

def fill_rest(puzzle, valid_lines):
    """
    Brute force solves the rest of the
    puzzle by populating potential 
    solutions for each line and validating
    whether the entire puzzle is valid
    """
    # In the unlikely scenario where we've already solved it
    if satisfy_constraints(puzzle):
        return puzzle

    line_solutions = []
    for i in range(len(puzzle)):
        sol = set()
        for line in valid_lines:
            if like_original(puzzle[i], line):
                sol.add(line)
        line_solutions.append(list(sol))

    filled_puzzles = list(itertools.product(*line_solutions))

    for p in filled_puzzles:
        if satisfy_constraints(p):
            return p

    print("UH OH")

def satisfy_constraints(puzzle):
    """
    Checks a bunch of criteria the puzzle must
    match before it satisfies the constraints.
    """
    rot_puzzle = rotate_right(puzzle)

    contain_dot = not any(['.' in line for line in puzzle])
    reg_eq = all([equal_num(line) for line in puzzle])
    rot_eq = all([equal_num(line) for line in rot_puzzle])

    # Make sure all of the rows/columns are unique
    reg_diff = [puzzle.count(line) for line in puzzle] == [1]*len(puzzle)
    rot_diff = [rot_puzzle.count(line) for line in rot_puzzle] == [1]*len(puzzle)

    # If any of them have three consecutive
    reg_consecutive = not any([three_consecutive(line) for line in puzzle])
    rot_consecutive = not any([three_consecutive(line) for line in rot_puzzle])

    return all([contain_dot, reg_eq, rot_eq, reg_diff, rot_diff, reg_consecutive, rot_consecutive])

def like_original(line, potential_solution):
    # Our line is already in the form of a regular
    # expression. '.' is a wildcard 
    return True if re.match(line, potential_solution) else False

def three_consecutive(line):
    """
    Returns a bool whether or not there are three
    consecutive numbers in a row on our line
    """
    return True if re.search('[0]{3,}|[1]{3,}', line) else False

def equal_num(line):
    """
    Returns a bool determining if there are more
    1s than half the length of our line
    """
    if line.count('1') > len(line) // 2 or line.count('0') > len(line) // 2:
        return False
    return True

def flatten(deep_list):
    while type(deep_list[0]) == type([]):
        deep_list = list(itertools.chain.from_iterable(deep_list))

    return deep_list

def build_perms(s, match, left):
    """
    A recursive function that takes an original 
    prefix, a dictionary that matches with the
    prefix, and the number of iterations we have
    left. Returns all the permutations for a prefix.
    """
    if left == 0:
        return s[:-2] # Cut off our last two appended 
    prefix = s[-2:]
    return [build_perms(s + postfix, match, left - 2) for postfix in match[prefix]]

def get_permutations(size):
    # A dictionary to match all of our valid 
    # prefixes with all valid postfixes
    match = {
        '00': ['10', '11'],
        '01': ['01', '10', '00'],
        '10': ['01', '10', '11'],
        '11': ['00', '01']
    }

    perms = [build_perms(key, match, size) for key in match]
    perms = list(set(flatten(perms)))
    return list(filter(equal_num, perms))

def print_puzzle(puzzle):
    for line in puzzle:
        print(line)
    print("")

if __name__ == '__main__':
    puzzle = open('puzzle.txt', 'r').readlines()
    puzzle = [line.replace('\n', '') for line in puzzle]

    print("ORIGINAL")
    print_puzzle(puzzle)

    puzzle_copy = []
    # Go until our solve partial returns the
    # same puzzle as before; this means we
    # can't get any more easy placements
    while puzzle != puzzle_copy:
        puzzle_copy = copy.deepcopy(puzzle)
        puzzle = solve_partial(puzzle)

    print("AFTER PARTIAL")
    print_puzzle(puzzle)

    valid_lines = get_permutations(len(puzzle))
    puzzle = fill_rest(puzzle, valid_lines)

    print("AFTER FILL")
    print_puzzle(puzzle)

下面是测试程序的一些输入。12×12的拼图需要特别长的时间。

110...
1...0.
..0...
11..10
....0.
......

0....11..0..
...1...0....
.0....1...00
1..1..11...1
.........1..
0.0...1.....
....0.......
....01.0....
..00..0.0..0
.....1....1.
10.0........
..1....1..00

Answer 1

对satisfy_costraints

的优化

正如您所说的，这个函数运行了200多万次，我将重点讨论如何改进它的运行时。

我建议您删除它包含的所有变量，将结果赋值给var强制计算，同时避免它允许利用all的懒散性(它在第一个false处停止)。

同时，对列表中的每个项目(线性)运行list.count (线性)是二次(线性x线性)，我建议您使用自己的线性set思想。

方括号创建一个立即被丢弃的列表，您应该使用圆形列表来创建生成器(没有空间/时间浪费)。

"Pythonic“风格

range(len

for i in range(len(puzzle)):
    puzzle[i] = replace_twos(puzzle[i]) 
    puzzle[i] = half_filled(puzzle[i])

通常情况下，range(len意味着您正在与语言作斗争。您可以在不使用列表理解或map (我建议使用列表理解)的显式索引的情况下编写这篇文章。

在另一个例子中：

for i in range(len(puzzle)):
    ....
    if like_original(puzzle[i], line)

您可以使用for直接迭代益智：

 for x in puzzle:
    ....
    if like_original(x, line)

更清楚的是，您可以在x之上选择任何描述性名称来进一步改进。

干法

line = line.replace('.00.', '1001') 
line = line.replace('00.', '001')
# .... Many more similar lines

重复太多了。DRY原则建议一个循环，其中只有字符串对发生变化：

for to_replace, replacement in ( ('.00.', '1001'), ...):
    line = line.replace(to_replace, replacement)

这提高了信噪比。

对

故障的正确处理

print("UH OH")

不是处理错误的正确方法。

您应该使用一个明确的错误消息来引发适当的异常(即使是代价异常，如果这会使代码更具描述性)。

类似于：

 raise ImpossiblePuzzleException("Puzzle could not be solved")

或SolvingFailureException.

不要让不正确的结束条件溜走，大声失败(调用者可以捕捉异常，但他无法避免打印，因此这也增强了调用方的能力)

使用标准术语提高对

的理解

# Go until our solve partial returns the 
# same puzzle as before

应用一个函数直到未见任何变化时，amymore称为找出该函数的不动点。说明在您的代码中，为了那些熟悉定点概念的人的利益。您可以编写一个fixed_point函数来进行更多的抽象。

避免列出一长串立即被

赶走的列表

filled_puzzles = list(itertools.product(*line_solutions))

然后遍历filled_puzzles。但是迭代并不需要一个列表，因为Iterable就足够了(按鸭子类型输入，这完全是为了提供正确的方法，您可以根据对象所能做的，而不是它们是什么来对待对象)。为了加快速度，请删除list .

bool

你做了两次：

return True if x else False

这相当于：

return bool(x)

这只是简单而已。

not

 if x: return False
 return True

这样做，而return not x就会更简单。

Answer 2

修改您的拼图

在solve_partial中，您正在进行两种修改：

• 通过在可能的情况下添加1和零来更新puzzle；
• 通过旋转创建新的puzzles。

由于您已经为您的益智创建了新的列表，所以您应该在每个阶段都这样做，这样您就不必在主循环中copy旧的谜题了：

def solve_partial(puzzle):
    """
    Finds rows and columns that match a 
    criteria and replaces them 
    """

    better_puzzle = [half_filled(replace_twos(line)) for line in puzzle]
    best_puzzle = [half_filled(replace_twos(line)) for line in rotate_right(puzzle)]
    return rotate_left(best_puzzle)

然后，您可以像这样使用它：

puzzle_copy = []
# Go until our solve partial returns the
# same puzzle as before; this means we
# can't get any more easy placements
while puzzle != puzzle_copy:
    puzzle_copy = puzzle
    puzzle = solve_partial(puzzle)

并消除了对import copy的需求。

轮调

a b c d e                        e j o t y                       a b c d e
f g h i j                        d i n s x                       f g h i j
k l m n o   -- rotate_right ->   c h m r w   -- rotate_left ->   k l m n o
p q r s t                        b g l q v                       p q r s t
u v w x y                        a f k p u                       u v w x y

使用[::-1]可以有效地使网格物理旋转。但是你并不需要这样做，因为你所有的操作都是在线的，所以你不关心他们的订单。通过使用：

def rotate(puzzle):
    return [''.join(t) for t in zip(*puzzle)]

您既简化了写操作，也简化了运行时(因为您不必为反向创建一个中间列表)，这将节省您的时间，因为在您的200万次迭代中，每次循环都会节省时间。

益智游戏的外观如下：

a b c d e                  a f k p u                  a b c d e
f g h i j                  b g l q v                  f g h i j
k l m n o   -- rotate ->   c h m r w   -- rotate ->   k l m n o
p q r s t                  d i n s x                  p q r s t
u v w x y                  e j o t y                  u v w x y

satisfy_constraints

您可以删除contain_dot，因为它包含在下一个检查中(也就是说，如果一行包含点，则0的计数或0的计数将不等于一行长度的一半)。您将看到您执行了两次相同的操作:一次是在原始拼图上，另一次是在旋转的拼图上。只需执行一次这些操作，就可以简化写作：

def satisfy_constraints(puzzle):
    """
    Checks a bunch of criteria the puzzle must
    match before it satisfies the constraints.
    """

    if any(not equal_num(line) for line in puzzle):
        return False
    # Make sure all of the rows/columns are unique
    if any(puzzle.count(line) != 1 for line in puzzle):
        return False
    # If any of them have three consecutive
    if any(re.search('[0]{3,}|[1]{3,}', line) for line in puzzle):
        return False

    return True

这假设对equal_num做了一些修改，以检查1和0的数目是否正好是行长度的一半：

def equal_num(line):
    return line.count('1') == len(line) // 2 == line.count('0')

您可以使用satisfy_constraint，例如：

for p in itertools.product(*line_solutions):
    if satisfy_constraints(p) and satisfy_constraints(rotate(p)):
        return p

这可以让你短路之前旋转拼图，这也可以节省你的时间。

您也不需要使用set来构建line_solutions，因为您已经在get_permutations中使用了set：

line_solutions = [
    [line for line in valid_lines if re.match(partial, line)]
    for partial in puzzle
]

您可能还注意到，我在代码中直接使用了re，而不是在它们自己的函数中使用:因为这些函数只在一个地方使用，因此减少了调用它们的开销。

构建搜索空间

由于您似乎在使用Python3，所以可以使用yield from构造来避免依赖itertools.chain.from_iterable：

MATCH = {
    '00': ['10', '11'],
    '01': ['01', '10', '00'],
    '10': ['01', '10', '11'],
    '11': ['00', '01'],
    '': ['00', '01', '10', '11'],
}

def build_perms(prefix, left, accumulator=''):
    """
    A recursive function that takes an original
    prefix, a dictionary that matches with the
    prefix, and the number of iterations we have
    left. Returns all the permutations for a prefix.
    """
    grown = accumulator + prefix
    remaining = left - len(prefix)
    if remaining < 1:
        yield grown
    else:
        for postfix in MATCH[prefix]:
            yield from build_perms(postfix, remaining, grown)


def get_permutations(size):
    return list(filter(equal_num, build_perms('', size)))

我还将MATCH提取为常量，因为它不会改变拼图的大小。

管理文件

益智=打开(‘ggle.txt’，'r').readlines()谜= Line.replace(‘\n’，‘)用于拼图中的行

您open的拼图文件，但从来没有close。为了避免这种情况，最好总是将open与with结合使用。您还应该使用strip，而不是用replace替换换行符。您还可以对整个文件使用splitlines：

with open('puzzle.txt') as takuzu:
    puzzle = takuzu.read().splitlines()

或

with open('puzzle.txt') as takuzu:
    puzzle = [line.strip() for line in takuzu]

Answer 3

一项建议是改变填充休息，使之一次又一次地变为正方形。如果您使用舞蹈链接解决方案(https://en.wikipedia.org/wiki/Dancing_链接)，您可能会发现一个相当大的加速。从根本上说，它的优势在于，如果不完成董事会的其余部分，解决方案就无法奏效。