数独游戏，方框包含方块数
Sudoku Puzzle with boxes containing square numbers
两天前，有人给我一个数独问题，我试图用 Python 3 解决。我被告知确实存在一个解决方案，但我不确定是否存在多个解决方案.
问题如下：一个9x9的数独格完全是空的。但是它确实包含 colored boxes, and inside these boxes, the sum of the numbers has to be a square number. Other than that, normal sudoku rules apply.
这里的问题是 不是 解决数独谜题，而是生成满足 colored boxes 规则的可行谜题。
我的攻略
使用 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]]
正如您从 picture 或上面的数组中看到的那样，方框排列成 2、3、4 或 5 个块（8 个二、12 个三、3 个四、1 个五） ).
我还注意到一个盒子可以包含多个数字而不违反数独的任何规则，但一个数字中只有 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)])
但是，这些列表的任何排列都是 "square problem" 的可行解决方案。再次使用 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 次尝试中的表现感兴趣，这里有一些 stats（这是一个直方图，x 轴表示分数，y 轴表示在这些过程中每个分数出现的次数700 次尝试）。
我需要什么帮助
我正在努力寻找一种可行的方法来解决这个问题，实际上可以在有限的时间内 运行。我将不胜感激关于使我的某些代码更快或更好的任何提示、任何解决问题的不同方法的想法、任何问题的解决方案，或有关 Python/Numpy 与此问题相关的一些有用提示。
这是我要使用 SMT 求解器的地方。他们比人们认为的要强大得多。如果您能想到的最佳算法本质上是蛮力算法，请尝试使用求解器。只需列出您的约束条件，运行 它会在几秒钟内给出您独特的答案：
278195436
695743128
134628975
549812763
386457291
721369854
913286547
862574319
457931682
使用的代码（坐标reference image）：
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]))
创建了一个名为 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) ]
两天前，有人给我一个数独问题，我试图用 Python 3 解决。我被告知确实存在一个解决方案，但我不确定是否存在多个解决方案.
问题如下：一个9x9的数独格完全是空的。但是它确实包含 colored boxes, and inside these boxes, the sum of the numbers has to be a square number. Other than that, normal sudoku rules apply.
这里的问题是 不是 解决数独谜题，而是生成满足 colored boxes 规则的可行谜题。
我的攻略
使用 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]]
正如您从 picture 或上面的数组中看到的那样，方框排列成 2、3、4 或 5 个块（8 个二、12 个三、3 个四、1 个五） ). 我还注意到一个盒子可以包含多个数字而不违反数独的任何规则，但一个数字中只有 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)])
但是，这些列表的任何排列都是 "square problem" 的可行解决方案。再次使用 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 次尝试中的表现感兴趣，这里有一些 stats（这是一个直方图，x 轴表示分数，y 轴表示在这些过程中每个分数出现的次数700 次尝试）。
我需要什么帮助
我正在努力寻找一种可行的方法来解决这个问题，实际上可以在有限的时间内 运行。我将不胜感激关于使我的某些代码更快或更好的任何提示、任何解决问题的不同方法的想法、任何问题的解决方案，或有关 Python/Numpy 与此问题相关的一些有用提示。
这是我要使用 SMT 求解器的地方。他们比人们认为的要强大得多。如果您能想到的最佳算法本质上是蛮力算法，请尝试使用求解器。只需列出您的约束条件，运行 它会在几秒钟内给出您独特的答案：
278195436
695743128
134628975
549812763
386457291
721369854
913286547
862574319
457931682
使用的代码（坐标reference image）：
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]))
创建了一个名为 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) ]