Hab für Sudoku eine Loesung-Suche geschrieben
Sudoku? Infos hier: http://www.tagesschau.de/aktuell/meldun ... 68,00.html
Hierzu musste ich Zahlen permutieren. Da ich für Python kein Code gefunden hatte, aber dafür für Pascal, hab ich es "übersetzt". Der Code stammt von hier: http://www.schoenleber.org/pascal/pascal2-03.html. Ich weiss bloß nicht ob ich den so veröffentlichen darf..., deshalb lasse ich es.
Code: Alles auswählen
import permute
Sudoku1 = [
[0,6,0,1,0,4,0,5,0], # Original
[0,0,8,3,0,5,6,0,0], # viele Zahlen zu checken
[2,0,0,0,0,0,0,0,1],
[8,0,0,4,0,7,0,0,6],
[0,0,6,0,0,0,3,0,0],
[7,0,0,9,0,1,0,0,4],
[5,0,0,0,0,0,0,0,2],
[0,0,7,2,0,6,9,0,0],
[0,4,0,5,0,8,0,7,0]]
Sudoku1 = [
[0,6,0,1,0,4,0,5,0], # schnelle Variante zum Testen
[0,0,8,3,0,5,6,4,9], # wenige Zahlen zu checken
[2,0,0,6,8,9,7,3,1],
[8,2,1,4,0,7,0,9,6],
[0,0,6,8,5,2,3,0,7],
[7,0,0,9,6,1,8,2,4],
[5,8,9,7,1,3,0,0,2],
[0,0,7,2,0,6,9,8,5],
[6,4,2,5,0,8,1,7,0]]
# Zahlen 1..9 alle da?
def Reihe(r):
check = [0,0,0,0,0,0,0,0,0,0]
for i in range(9):
if (r[i]>0) and (check[r[i]] == 0):
check[r[i]] = 1
else:
return 0
for i in range(1,10):
if check[i] <> 1:
return 0
return 1
def Zahl_doppelt(r):
z = []
for i in r:
if i in z:
return 1
else:
z.append(i)
return 0
# Zahlen die erraten werden muessen
def Zahlen(r):
nein = []
for i in range(len(r)):
if r[i] > 0:
nein.append(r[i])
z = []
for i in range(1,10):
if not i in nein:
z.append(i)
return z
def Zahlen_Vorgabe(r):
zv = []
for i in range(len(r)):
if r[i] > 0:
zv.append([i,r[i]])
return zv
# 3 Reihen a 3 Inseln werden gecheckt - 1..9 vorhanden?
def inseln(r):
for x in [0,3,6]:
Insel = []
for y in range(3):
for x2 in range(3):
Insel.append(r[y][x+x2])
if not Reihe(Insel):
return 0
return 1
# Permutieren der 9 waagerechten Reihen
print "Schritt 1/5 - Zahlen permutieren"
s = Sudoku1[:]
permu_list = []
for i in range(9):
permu_list.append(permute.permute(Zahlen(s[i])))
zv = Zahlen_Vorgabe(s[i])
for x in range(len(permu_list[i])):
l1 = permu_list[i][x]
for i2 in range(len(zv)):
zvx = zv[i2]
l1.insert(zvx[0],zvx[1])
permu_list[i][x] = l1
# jeweils 3 uebereinanderliegende Reihen werden gecheckt
def L3Check(Liste1,Liste2,Liste3,OKListe):
for x0 in range(len(Liste1)):
for x1 in range(len(Liste2)):
for x2 in range(len(Liste3)):
weiter = 1
for i in range(9):
if Zahl_doppelt([Liste1[x0][i],Liste2[x1][i],Liste3[x2][i]]):
weiter = 0
break
if not weiter:
continue
if not inseln([Liste1[x0],Liste2[x1],Liste3[x2]]):
continue
OKListe.append([Liste1[x0],Liste2[x1],Liste3[x2]])
OK012Listen = []
OK345Listen = []
OK678Listen = []
print "Schritt 2/5 - Zeilen 1-3 checken"
L3Check(permu_list[0],permu_list[1],permu_list[2],OK012Listen)
print "Schritt 3/5 - Zeilen 4-6 checken"
L3Check(permu_list[3],permu_list[4],permu_list[5],OK345Listen)
print "Schritt 4/5 - Zeilen 7-9 checken"
L3Check(permu_list[6],permu_list[7],permu_list[8],OK678Listen)
BingoListe = []
# gefundene 3er-Linien werden gecheckt ob sie zusammenpassen
print "Schritt 5/5 - Zeilen 1-9 zusammensetzen"
for L1 in range(len(OK012Listen)):
l1 = []
for i in range(3): l1.append(OK012Listen[L1][i])
for L2 in range(len(OK345Listen)):
l2 = l1[:]
for i in range(3): l2.append(OK345Listen[L2][i])
for L3 in range(len(OK678Listen)):
l3 = l2[:]
for i in range(3): l3.append(OK678Listen[L3][i])
OK = 1
for x in range(9):
l = []
for i in range(9):
l.append(l3[i][x])
if not Reihe(l):
OK = 0
break
if OK:
BingoListe.append(l3)
# Ergebnis zeigen
for BL in range(len(BingoListe)):
print
print
print "Sudoku - Loesung", BL+1
for i in range(len(BingoListe[BL])):
print BingoListe[BL][i]
(=olliminieren)
. Ich denke du kannst das permut Modul ruhig posten.
und durch ein besseres ersetzen