Vor zwei Tagen erhielt ich ein Sudoku-Problem, das ich mit Python 3 lösen wollte. Ich wurde informiert, dass es eine Lösung gibt, bin mir aber nicht sicher, ob es mehrere Lösungen gibt.
Das Problem ist wie folgt: Ein 9x9-Sudoku-Gitter ist vollständig leer. Es enthält jedoch farbige Kästchen , und innerhalb dieser Kästchen muss die Summe der Zahlen eine quadratische Zahl sein . Ansonsten gelten die normalen Sudoku-Regeln .
Hier geht es nicht darum , ein Sudoku-Puzzle zu lösen, sondern ein brauchbares Puzzle zu erstellen, das den Regeln der farbigen Kästchen entspricht .
Meine Strategie
Mit numpy Arrays habe ich das Raster in 81 Indizes unterteilt, die in ein 9x9-Raster umgewandelt werden können.
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]]
Hier ist eine Liste mit allen Indexblöcken.
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]]
Wie Sie auf dem Bild oder in der obigen Anordnung sehen können, sind die Kästchen in Blöcken von 2, 3, 4 oder 5 angeordnet (8 Zweien, 12 Dreien, 3 Vieren, 1 Fünfer). Ich habe auch bemerkt, dass eine Box mehrere Zahlen enthalten kann, ohne gegen die Regeln von Sudoku zu verstoßen, aber nur 2 von einer Zahl sind möglich. Angesichts dieser Informationen wäre das größtmögliche Quadrat 36, da 9 + 9 + 8 + 7 + 6 = 39, und somit könnte keine Summe eines Blocks jemals 49 erreichen. Um herauszufinden, ob die Summe einer Liste eine Quadratzahl enthält Ich habe folgende Funktion gemacht:
def isSquare(array):
if np.sum(array) in [i**2 for i in range(1,7)]:
return True
else:
return False
Um herauszufinden, ob eine Liste die richtige Anzahl von Duplikaten enthält, dh mehr als ein Duplikat von nur einer Zahl, habe ich die folgende Funktion ausgeführt:
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
Angesichts der Ziffern 1 bis 9 gibt es nur begrenzte Lösungsmöglichkeiten für eine Liste, wenn die Liste zu einer quadratischen Zahl summiert werden muss. Mit itertools konnte ich die Lösungen finden und sie in ein Array unterteilen, wobei Index 0 Zweierblöcke, Index 1 Dreierblöcke usw. enthält.
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)])
Jede Permutation dieser Listen ist jedoch eine praktikable Lösung für das "Quadratproblem". Bei erneuter Verwendung von itertools summiert sich die Gesamtzahl der möglichen Boxen (ohne die Sudoku-Regeln) auf 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
Dies sollte ausreichen, um Funktionen zu implementieren, die entscheiden, ob eine Karte zulässig ist, dh Zeilen, Spalten und Felder enthalten jeweils nur eine der Ziffern 1 bis 9. Meine Implementierung:
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))
Schwierigkeiten mit der Laufzeit
Ein einfacher Ansatz wäre, jede einzelne Kombination jedes einzelnen Blocks zu überprüfen. Ich habe dies getan und einige brauchbare Probleme verursacht, aber die Komplexität meines Algorithmus lässt dies viel zu lange dauern.
Stattdessen habe ich versucht, einige der Eigenschaften zufällig zu sortieren: Die Reihenfolge der Blöcke und die Reihenfolge der Lösungen. Auf diese Weise habe ich die Anzahl der Versuche begrenzt und überprüft, ob eine Lösung realisierbar ist:
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)
Im obigen Code bezieht sich die variable Bewertung darauf, wie viele Blöcke der Algorithmus während eines Versuchs finden konnte. Die Variable korrekt bezieht sich darauf, wie viele der generierten Sudoku-Boards fertiggestellt werden konnten. Wenn Sie daran interessiert sind, wie gut es in 700 Versuchen war, finden Sie hier einige Statistiken (Dies ist ein historisches Gramm, die x-Achse repräsentiert die Punktzahlen und die y-Achse repräsentiert, wie viele von jeder Punktzahl während dieser 700 Versuche vorhanden waren).
Womit ich Hilfe brauche
Ich habe Mühe, einen praktikablen Weg zu finden, um eine Lösung für dieses Problem zu finden, die tatsächlich in einer begrenzten Zeitspanne ausgeführt werden kann. Ich würde mich sehr über Tipps freuen, wie Sie einen Teil meines Codes schneller oder besser machen können, über Ideen für eine andere Herangehensweise an das Problem, über Lösungen für das Problem oder über nützliche Tipps zu Python / Numpy, die für dieses Problem relevant sind.
quelle
isSquare(a): return math.sqrt(sum(a)) % 1.0 == 0
oder so. Ziemlich sicher, dass dies viel schneller ist, als[i**2 for i in range(1,7)]
jedes Mal neu zu berechnen und eine lineare Suche darin durchzuführen. Gibt auchin
bereits einen Booleschen Wert zurück. Keine Notwendigkeit für dieif
.Antworten:
Hier würde ich einen SMT-Solver verwenden. Sie sind viel mächtiger, als die Leute glauben. Wenn der beste Algorithmus, den Sie sich vorstellen können, im Wesentlichen Bruteforce ist, versuchen Sie stattdessen einen Solver. Wenn Sie einfach Ihre Einschränkungen auflisten und ausführen, erhalten Sie in wenigen Sekunden eine eindeutige Antwort:
Der verwendete Code (und das Referenzbild für die Koordinaten):
quelle
python -m pip install z3-solver
sollte Z3 bekommen. Nach dem Bearbeiten des Codes werden nun alle zufriedenstellenden Lösungen gedruckt.