logo标签列表

数独谜题，其中包含平方数的盒子

pythonpython-3.xnumpysudoku
9
两天前，我得到了一道数独问题，尝试用Python 3解决。已经告知有解，但不确定是否存在多种解决方案。
问题如下：一个9x9的数独网格完全为空。然而，它包含彩色框，并且这些框内数字的总和必须是平方数。除此之外，普通的数独规则也适用。
问题在于不是解决数独难题，而是生成一个可行的拼图，满足彩色框的规则。 我的策略 使用numpy数组，我将网格分成81个索引，可以重新排列为9x9的网格。
import numpy as np
print(np.array([i for i in range(81)]).reshape((9, 9)))

->
[[ 0  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]]

这是一个包含所有索引块的列表。
boxes = [[44, 43, 42, 53],[46, 47, 38],[61, 60],[69, 70],[71, 62],
         [0, 9, 18],[1, 10, 11, 20],[2, 3, 12],[4, 13, 14],[5, 6],
         [7, 8],[17, 26, 35],[21, 22, 23],[15, 16, 24, 25, 34],
         [27, 36, 37],[19, 28, 29],[45, 54],[55, 56],[63, 64, 65],
         [72, 73, 74],[57, 66, 75 ],[58, 59, 67, 68],[76, 77],[78, 79, 80]]

从图片或上面的数组可以看出，这些方框被分成2、3、4或5个块（8个2，12个3，3个4，1个5）。我还注意到一个方格可以包含多个数字而不违反数独规则，但只能有2个相同的数字。考虑到这些信息，最大可能的正方形是36，因为9+9+8+7+6=39，因此任何块的总和都不能达到49。为了找出列表总和是否包含平方数，我编写了以下函数：

def isSquare(array):
    if np.sum(array) in [i**2 for i in range(1,7)]:
        return True
    else:
        return False

为了确定列表是否包含正确数量的重复项，也就是只有一个数字的多个副本，我编写了以下函数：
def twice(array):
    counter = [0]*9
    for i in range(len(array)):
        counter[array[i]-1]+=1
        if 3 in counter:
            return False
    if counter.count(2)>1:
        return False
    return True

现在，假设有数字1-9，如果一个列表必须加起来形成一个完全平方数，那么这个列表的解决方案就是有限的。使用itertools，我可以找到这些解决方案，并将它们分成一个数组，其中索引0包含两个数字的块，索引1包含三个数字的块，以此类推。

from itertools combinations_with_replacement
solutions = []
for k in range(2, 6):
    solutions.append([list(i) for i in combinations_with_replacement(np.arange(1, 10), k) if 
    isSquare(i) and twice(i)])

然而，这些列表的任何排列都是“方阵问题”的可行解。再次使用itertools，在不考虑数独规则的情况下，可能的盒子总数为8782。
from itertools import permutations

def find_squares():
    solutions = []
    for k in range(2, 6):
        solutions.append([list(i) for i in combinations_with_replacement(np.arange(1, 10), k) if 
            isSquare(i) and twice(i)])
    s = []
    for item in solutions:
        d=[]
        for arr in item:
            for k in permutations(arr):
                d.append(list(k))
        s.append(d)
    return s # 4-dimensional array, max 2 of each

solutions = find_squares()

total = sum([len(i) for i in solutions])
print(total)
-> 8782

这足以实现一个判断棋盘是否合法的功能，即每行、每列和每个九宫格都只包含数字1-9中的一个。我的实现如下：

def legal_row(arr):
    for k in range(len(arr)):
        values = []
        for i in range(len(arr[k])):
            if (arr[k][i] != 0):
                if (arr[k][i] in values):
                    return False
                else:
                    values.append(arr[k][i])
    return True

def legal_column(arr):
    return legal_row(np.array(arr, dtype=int).T)


def legal_box(arr):
    return legal_row(arr.reshape(3,3,3,3).swapaxes(1,2).reshape(9,9))


def legal(arr):
    return (legal_row(arr) and legal_column(arr) and legal_box(arr))

运行时的困难

一种直接的方法是检查每个块的每个组合。我已经尝试过这样做，并且产生了几个可行的问题，但我的算法复杂度使得这需要太长时间。

相反，我尝试随机化一些属性：块的顺序和解决方案的顺序。使用这种方法，我限制了尝试的次数，并检查了一个解决方案是否可行：

attempts = 1000
correct = 0
possibleBoards = []
for i in range(1, attempts+1):
    board = np.zeros((9, 9), dtype=int)
    score = 0
    shapes = boxes
    np.random.shuffle(shapes)
    for block in shapes:
        new_board = board
        new_1d = board.reshape(81)
        all_sols = solutions[len(block)-2]
        np.random.shuffle(all_sols)
        for sols in all_sols:
            #print(len(sols))
            new_1d[block] = sols
            new_board = new_1d.reshape((9, 9))
            if legal(new_board):
                board = new_board
                score+=1
                break
    confirm = board.reshape(81)
    #solve(board) # Using my solve function, not important here
    # Note that without it, correct would always be 0 as the middle of the puzzle has no boxes
    confirm = board.reshape(81)
    if (i%1000==0 or i==1):
        print("Attempt",i)
    if 0 not in confirm:
        correct+=1
        print(correct)
        possibleBoards.append(board)

在上面的代码中，变量score代表算法在尝试中找到了多少个方块。变量correct代表可以完成生成的数独棋盘的数量。如果您对它在700次尝试中的表现感兴趣，这里有一些统计数据（这是一个直方图，x轴表示得分，y轴表示这700次尝试中每个得分出现的次数）。 我需要帮助的内容 我正在努力寻找一种可行的方法来解决这个问题，可以在有限的时间内运行。我非常感谢任何关于如何使我的代码更快或更好的提示，任何不同方法的想法，问题的解决方案，或与此问题相关的Python/Numpy有用的技巧。
1
isSquare(a)：返回math.sqrt(sum(a)) % 1.0 == 0或类似的结果。我相信这比每次重新计算[i**2 for i in range(1,7)]并在其中进行线性搜索要快得多。此外，in已经返回一个布尔值，不需要使用if。 - Mad Physicist
请记住，solutions = find_squares() 这一部分只需要不到一秒钟的时间，而最后一部分——实现部分，即查找答案是否正确的部分才是较慢的。 - balways
2
顺便提一下（也是给其他读者看的），你可以在这里观看这个谜题的解释：https://www.youtube.com/watch?v=myGqOF6blPI，描述中还有一个在线游戏链接。这是一个很棒的谜题，那个频道也很不错。我昨天刚好解决了这个谜题，所以看到这个视频感到很惊讶！ - Alex Hall
哇，太棒了，我真的很喜欢看他解决这个问题。谢谢你的提示！ - balways
2个回答
6

我可以使用SMT求解器来帮助你。它们比人们想象的更加强大。如果你最好的算法实质上是暴力算法，那么请尝试使用求解器。只需列出您的约束条件并运行它，即可在几秒钟内得到唯一的答案。

278195436
695743128
134628975
549812763
386457291
721369854
913286547
862574319
457931682

使用的代码（以及坐标的参考图像）：

import z3

letters = "ABCDEFGHI"
numbers = "123456789"
boxes = """
A1 A2 A3
B1 B2 C2 C3
C1 D1 D2
E1 E2 F2
F1 G1
H1 I1
G2 H2 G3 H3 H4
I2 I3 I4
B3 B4 C4
D3 E3 F3
A4 A5 B5
C5 B6 C6
G5 H5 I5 I6
A6 A7
B7 C7
D7 D8 D9
E7 E8 F7 F8
G7 H7
I7 I8
A8 B8 C8
G8 H8
A9 B9 C9
E9 F9
G9 H9 I9
"""
positions = [letter + number
             for letter in letters
             for number in numbers]
S = {pos: z3.Int(pos) for pos in positions}

solver = z3.Solver()

# Every symbol must be a number from 1-9.
for symbol in S.values():
    solver.add(z3.Or([symbol == i for i in range(1, 10)]))

# Every row value must be unique.
for row in numbers:
    solver.add(z3.Distinct([S[col + row] for col in letters]))

# Every column value must be unique.
for col in letters:
    solver.add(z3.Distinct([S[col + row] for row in numbers]))

# Every block must contain every value.
for i in range(3):
    for j in range(3):
        solver.add(z3.Distinct([S[letters[m + i * 3] + numbers[n + j * 3]]
                                for m in range(3)
                                for n in range(3)]))

# Colored boxes.
for box in boxes.split("\n"):
    box = box.strip()
    if not box: continue
    boxsum = z3.Sum([S[pos] for pos in box.split()])
    solver.add(z3.Or([boxsum == 1, boxsum == 4, boxsum == 9,
                      boxsum == 16, boxsum == 25, boxsum == 36]))

# Print solutions.
while solver.check() == z3.sat:
    model = solver.model()
    for row in numbers:
        print("".join(model.evaluate(S[col+row]).as_string()
                    for col in letters))
    print()

    # Prevent next solution from being equivalent.
    solver.add(z3.Or([S[col+row] != model.evaluate(S[col+row])
                      for col in letters
                      for row in numbers]))
看起来很有前途！我从来没有想过那个。你有z3安装的任何文档吗？此外，这是否意味着只有一个解决方案？ - balways
1
使用命令 python -m pip install z3-solver 可以安装 Z3。在编辑代码后，现在它会打印出所有可满足的解决方案。 - orlp
1
@balways 在修复了一个 bug 后，现在它会迭代所有可满足的解。然而，它只找到一种解，因此这个解是唯一的。 - orlp
0
创建了一个名为Boxes的列表，其中包含9个元素，每个元素又是另一个列表。这9个列表对应于9个盒子中的每一个，每个列表都包含元组作为元素，其中包含该盒子中每个方格的行和列索引。以类似以下方式明确输入值将具有相同的效果（但会浪费时间）： 

# The boxes list is created, with the row and column index of each square in each box
Boxes = [
    [(3*i+k+1, 3*j+l+1) for k in range(3) for l in range(3)]
    for i in range(3) for j in range(3) ]

嘿！您的代码片段无法运行。那很有趣，但如果我有一个创建盒子的明确公式，我可能也会有解决方案... - balways
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接