[两天前,我遇到了一个数独问题,尝试使用Python 3解决。我已获悉确实存在一个解决方案,但不确定是否存在多个解决方案。
问题如下:数独的9x9网格完全为空。但是,它确实包含colored boxes,并且在这些框中,数字的总和必须为square number。除此之外,适用普通sudoku rules。
这里的问题是not解决数独难题,而是生成一个可行的难题,满足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个,3个四个,1个5r)的块。我还注意到,一个盒子可以包含多个数字而不会破坏数独的任何规则,但是一个数字只能是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包含二进制的块,依此类推。]
,可能的盒子总数(无数独规则)总计为8782。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
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)
在上面的代码中,可变分数是指算法在尝试期间可以找到多少个块。正确的变量是指可以完成多少个数独板。如果您对它在700次尝试中的表现感兴趣,请参考stats(这是一个直方图,x轴表示得分,y轴表示在这700次尝试中每个得分有多少)。
我需要什么帮助
我正在努力寻找一种可行的方法来找到该问题的解决方案,该方法实际上可以在有限的时间内运行。我将不胜感激有关使我的某些代码更快或更佳的任何技巧,对问题采取不同方法的任何想法,对问题的任何解决方案,或与该问题相关的一些有关Python / Numpy的有用技巧。
两天前,我遇到了一个数独问题,我试图用Python 3解决。我被告知确实存在一个解决方案,但是我不确定是否存在多个解决方案。问题是...
这是我要使用SMT求解器的地方。它们比人们认为的要强大得多。如果您能想到的最佳算法本质上是暴力破解,请尝试使用求解器。只需列出您的约束并运行它即可在几秒钟内给出答案: