Sudoku-Löser

@night@

Guten Abend.
Ich hab heute mal aus Langeweile nen Programm zum Lösen von Sudokus geschrieben... Der Alghorithmus ist nicht gerade perfekt, aber er funktioniert^^
Die Bedienung is nicht gerade schwer: einfach alle Ziffern in die GUI eingeben, auf Start klicken und sich freuen
mfg @night@

Bulli

moin
ich hab das mal kurz getestet mit 2 sudokus
hab den script 2 min laufen lassen tut sich aber nix

guck nochma drüber oder muss ich mehr gedult haben?
EDIT: ich meinte hab das sudoku eingetragen und auf start gedrückt dann 2 min laufen lassen

@night@

Komisch... Ich habe es mit ein paar Sodokus aus einem Rätselheft probiert und da löste er es in weniger als einer Sekunde (nicht nur die einfachen )
Das Problem ist, dass er sich im Falle eines unmöglichen Sodukus aufhängt. Das werde ich noch verbessern, aber im Moment ist das schlecht, weil ich gerade kein AutoIT aufem Pc habe^^
mfg @night@
€dit: Probiert es mal mit dem Sudoku. Bei mir klappt es gut. Man muss eben drauf achten, dass alle Ziffern genau angegeben werden.

Jakolo

Das Sudoku von dir lässt sich mit deinem Programm lösen ein anderes was ich gerade zur Hand hatte allerdings nicht (hab allerdings auch nicht geprüft ob sich das Sudoku lösen lässt). Ich würder außerdem vielleicht noch einstellen, dass man nur eine Zahl in ein Kästchen schreiben kann und das wenn man eine Zahl eingegeben hat sofort das nächste Kästchen aktiviert wird.
lg jakolo

**Andy**

...gib mal Sudoku in der Sufu ein, im µ-It März 2009 gab es sehr schöne Solver

Spoiler anzeigen

[autoit]

#include <Array.au3>
#include <GDIPlus.au3>
;=======================>
#region GUI

[/autoit] [autoit][/autoit] [autoit]

$start = "000670900360005028805002100020506004009407000700100583070054261000703000084090050" ;normaler start
$start1= "410670900360005028805002100020536004009407610700100583070054261000703000084090050" ;weitere zahlen der lösung eingesetzt
$loesung="412678935367915428895342176128536794539487612746129583973854261251763849684291357";lösung
$hGUI = GUIcreate("Sodoku", 300, 370)
Local $aInputs[9][9]
For $x = 0 To 8
For $y = 0 To 8
$left = ($x + 1) * 30
$top = ($y + 1) * 30
$nummer=stringmid($start1,$y*9+$x+1,1)
if $nummer="0" then $nummer=""
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $nummer = ' & $nummer & @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console
$aInputs[$x][$y] = GUICtrlCreateInput($nummer, $left, $top, 20, 20)
Next
Next
$idStartBut = GUIctrlcreatebutton("Start", 100, 320, 100)
;load_old_sodoku($aInputs)
GUIsetstate()
;====================>Mit GDI+ die Striche draufmalen
draw_lines()
;======>
While 1
$nMsg = GUIgetmsg()
Switch $nMsg
Case -3 ;GUI_EVENT_CLOSE
Exit
Case $idStartBut
$aSodoku = get_array_of_sodoku($aInputs)
save_Sodoku_Ini($aSodoku)
MakeSodoku($aSodoku, $aInputs)
EndSwitch
Sleep(20)
WEnd

[/autoit] [autoit][/autoit] [autoit]

Func load_old_sodoku($aInputs)
If NOT FileExists("last_sodoku.ini") Then return -1
For $x = 0 To 8
For $y = 0 To 8
GUICtrlSetData($aInputs[$x][$y], Iniread("last_sodoku.ini", "section", $x&"|"&$y, ""))
Next
Next
return 0
endfunc

[/autoit] [autoit][/autoit] [autoit]

Func save_Sodoku_Ini($aSodoku)
For $x = 0 To 8
For $y = 0 To 8
If $aSodoku[$x][$y] <> 0 Then
Iniwrite("last_sodoku.ini", "section", $x&"|"&$y, $aSodoku[$x][$y])
Else
Iniwrite("last_sodoku.ini", "section", $x&"|"&$y, "")
endif
Next
Next
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func get_array_of_sodoku($aInputs)
Local $aSodoku[10][10]
For $x = 0 To 8 ;die nicht-existierende Reihe mit 0en auffüllen
$aSodoku[$x][9] = 0
Next
For $x = 0 To 8
For $y = 0 To 8
$aSodoku[$x][$y] = GUIctrlread($aInputs[$x][$y])
If $aSodoku[$x][$y] = "" Then $aSodoku[$x][$y] = 0
Next
Next
return $aSodoku
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func draw_lines()
_GDIPlus_Startup()
$hGraphics = _GDIPlus_GraphicsCreateFromHWND($hGui)
$hPen = _GDIPlus_PenCreate(0xFF000000, 3)
_GDIPlus_GraphicsDrawLine($hGraphics, 115, 20, 115, 300, $hPen) ;senkrecht
_GDIPlus_GraphicsDrawLine($hGraphics, 205, 20, 205, 300, $hPen) ;senkrecht
_GDIPlus_GraphicsDrawLine($hGraphics, 20, 115, 295, 115, $hPen) ;waagrecht
_GDIPlus_GraphicsDrawLine($hGraphics, 20, 205, 295, 205, $hPen) ;waagrecht
_GDIPlus_Shutdown()
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func array_drehen2D($array)
$er = $array
For $i = 0 To Ubound($array) -1
For $i2 = 0 To Ubound($array, 2) -1
$er[$i][$i2] = $array[$i2][$i]
Next
Next
return $er
EndFunc ;==>by Zeitriss

[/autoit] [autoit][/autoit] [autoit]

#endregion GUI

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

Func MakeSodoku($aFeld, $aInputs)
Local $aMerk[9][9] ;zum merken, welche Zahlen dort hin passen
While 1
$Ziffervoll = true
For $x = 0 To 8 ;==>Alle Ziffern setzen
For $y = 0 To 8
If $aFeld[$x][$y] = 0 Then
$Ziffervoll = False
$aMerk[$x][$y] = getpossibleNrs($aFeld, $x, $y)
Else
$aMerk[$x][$y] = ""
EndIf
Next
Next
If $Ziffervoll Then exitloop
;===>Alle Ziffern setzen, die eindeutig sind
For $x = 0 To 8 ;==>Alle Ziffern setzen
For $y = 0 To 8
If Stringlen($aMerk[$x][$y]) = 1 Then
$aFeld[$x][$y] = $aMerk[$x][$y]
$aMerk[$x][$y] = ""
EndIf
Next
Next
Sleep(5)
WEnd
;===========================>Berechnung ist beendet
;=======>Jetzt werden die Kontrollfelder ausgefüllt
For $x = 0 To 8
For $y = 0 To 8
GUIctrlsetdata($aInputs[$x][$y], $aFeld[$x][$y])
Next
Next
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func getpossibleNrs($aFeld, $iX_coord, $iY_coord)
$sCase = "123456789"
;========>Senkrechte
For $y = 0 To 8
If $aFeld[$iX_coord][$y] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX_coord][$y], "")
Next
;=========>Waagrechte
For $x = 0 To 8
If $aFeld[$x][$iY_coord] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$x][$iY_coord], "")
Next
;==============>Daten des 9er-Feldes bestimmen
If $iX_coord < 3 Then ;die Yer
$iX = 1
elseif $iX_coord > 5 Then
$iX = 7
elseif $iX_coord < 6 and $iX_coord > 2 Then
$iX = 4
EndIf
;=>
If $iY_coord < 3 Then ;die Yer
$iY = 1
elseif $iY_coord > 5 Then
$iY = 7
elseif $iY_coord < 6 and $iY_coord > 2 Then
$iY = 4
EndIf
;=========>9er-Feld
If $iX > 0 Then
If $aFeld[$iX-1][$iY] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX-1][$iY], "")
EndIf
If $iX < 9 Then
If $aFeld[$iX+1][$iY] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX+1][$iY], "")
EndIf
If $iX > 0 and $iY > 0 Then
If $aFeld[$iX-1][$iY-1] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX-1][$iY-1], "")
EndIf
If $iX < 9 and $iY > 0 Then
If $aFeld[$iX+1][$iY-1] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX+1][$iY-1], "")
EndIf
If $iY > 0 Then
If $aFeld[$iX][$iY-1] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX][$iY-1], "")
EndIf
If $iX < 9 and $iY < 9 Then
If $aFeld[$iX+1][$iY+1] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX+1][$iY+1], "")
EndIf
If $iX > 0 and $iY < 9 Then
If $aFeld[$iX-1][$iY+1] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX-1][$iY+1], "")
EndIf
If $iY < 9 Then
If $aFeld[$iX][$iY+1] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX][$iY+1], "")
EndIf
;=============>
return $sCase
EndFunc

[/autoit]

Habe dein Script mal "vorbelegt" mit einem leichten Sudoku. Es wurde erst gelöst, nachdem ich weitere Zahlen eingesetzt hatte.
µit - März hier findest du z.B. einen Solver, bei dem Script muß man die Zeile 158 auskommentieren, um etwas zu "sehen". Das Script mit der Gui und dem farbig dargestellten Lösungsweg der Strategien hab ich irgendwo vergraben...

@night@

Ich werde das Skript noch weiter nach Fehlern prüfen. Könntest du bitte mal das Sodoku posten, was du benutzt hast??? Ansonsten hab ich keinen richtigen Ansatz^^

Zitat

...gib mal Sudoku in der Sufu ein, im µ-It März 2009 gab es sehr schöne Solver

Ihr habt darüber schon nen Wettbewerb gemacht und ich bemerks nicht Naja, wenigstens hab ich so selber nen Lösungsweg gefunden...

**Andy**

Wenn du ein Sudoku, dass nur aus leeren Feldern besteht, mit deinem Programm lösen kannst, dann sollte dieses Script alle anderen Sudokus auch lösen.
Nur ist die "Brute-Force"-Lösung nicht immer die schnellste. Daher die diversen Strategien...

Zitat

Könntest du bitte mal das Sodoku posten, was du benutzt hast?

In meinem vorherigen Post ist sowohl das Sudoku, als auch die Lösung. Weitere in dem Link s.o.

@night@

Zitat

Wenn du ein Sudoku, dass nur aus leeren Feldern besteht, mit deinem Programm lösen kannst, dann sollte dieses Script alle anderen Sudokus auch lösen.

Da hst du recht. Allerdings sollte das Programm im Vornerein nicht können^^ Ich hab mir folgendes Zitat als Grundstein für das Skript genommen.

Zitat

Die Mindestanzahl vorbelegter Felder zu bestimmen, für die es ein eindeutig lösbares Sudoku gibt, ist ein ungelöstes Problem. Für die Standardvariante ist die kleinste bisher gefundene Anzahl 17.

Allerdings verstehe ich jetzt was du meinst. Ich werde trotzdem noch mal versuchen das Skript zu verbessern...
Werde mir die Links von dir auch noch mal genauer angucken...

Zitat

In meinem vorherigen Post ist sowohl das Sudoku, als auch die Lösung. Weitere in dem Link s.o.

Ich glaube ich sollte mal zum Optiker gehen... An meiner Beobachtungsgabe kann's ja nicht liegen

**Andy**

Wenn du "Futter" brauchst, im schon angesprochenen Thread sollte auch eine Liste von ca 36.000 Sudokus enthalten sein, darunter auch sehr viele 17er. Ich hatte die mal spaßeshalber mit meinem Solver abgeackert, um "böse" Sudokus zu finden.
20xBöse: (jedenfalls bei "normalen" Strategien)

Spoiler anzeigen

160000000000300050040002000007000020000104000000060007002005000000080006000000001
000000120000803000000009000401060000000007003002000000000020040030000008095000000
000900130000540000000060000080001020005000004006000000030007000004000005000000009
500080200740000000000000000002050000000600007800000040060700000001000500000304000
602050000000003040000000000430008000010000200000000700500270000000000081000600000
602050000000004030000000000430008000010000200000000700500270000000000081000600000
602700000000800130000000090400000700030090000000010000500400600010000020000000000
700080000000000104000000200000102000200000030000400500051030000000006070040000000
000701600500080000000000000000600701208090000400000000000020050070300000000000080
002100400083000000000000000500400700600020000010000000000008063100700000000000080
000800001900000500000000000410050000003000080000000700000108040020300000500000600
051000000000300080000070000020501006800000040000700000000000201300040000000000500
000020007405000000001000000000401000003000008060002000000500210070030000000000040
000420050070000000000080000030006007002090080000000001000007006805000000000001000
010065000000100080000000032070004001000020000008000000000007004806000000003000000
500004090020001000000030000031000008000005000008000000600700050004080000000000001
030080000000002005000000001000705030040000700000001000502000000000040080001006000
....7.94..7..9...53....5.7..874..1..463.8.........7.8.8..7.....7......28.5.268...
38.6.......9.......2..3.51......5....3..1..6....4......17.5..8.......9.......7.32
6...4...3.1.....7...5...8.....5.2...3...9...2...1.3.....8...9...7.....5.2...3...4

das 8. sollte man mal "von Hand" probieren^^

@night@

Das klingt jetzt vielleicht extrem dumm, aber wie liest man deine Sudokus? Bis jetzt hab ich nur kapiert, das eine Reihe ein Sodoku ist^^

**Andy**

ein Sudoku besteht aus 9 Zeilen a 9 Ziffern. Wenn man alle Zeilen nacheinander schreibt, entsteht....ein String mit 81 Zeichen.
Anstatt der 0 kann man auch . oder _ oder * einsetzen. Die gängigen Löser (ich empfehle mal einen Blick auf http://www.sudokuwiki.org/sudoku.htm) fressen so ziemlich alles....

stayawayknight

Also bei mir löst der "Löser" kein einziges Sudoku

**Andy**

Welcher?
Im Script in Post #5 ist ein Sudoku eingetragen. Das wird auch gelöst....

@night@

Hey Andi,
ich hab mir jetzt erstmal ne Funktion geschrieben, die die Sudoku-Strings in die Felder eingibt. Nur leider kommen dabei unlösbare Sudokus raus, da schon in der ersten Linie die 1 zweimal vorkommt.
Denke mal, das meine Funktion das falsch umsetzt. Hab auch schon die For-Schleife ein bisschen variiert^^

Spoiler anzeigen

[autoit]

#include <Array.au3>
#include <GDIPlus.au3>
;=======================>
#region GUI
$hGUI = GUIcreate("Sodoku", 300, 370)
Local $aInputs[9][9]
For $x = 0 To 8
For $y = 0 To 8
$left = ($x + 1) * 30
$top = ($y + 1) * 30
$aInputs[$x][$y] = GUICtrlCreateInput("", $left, $top, 20, 20)
Next
Next
$idStartBut = GUIctrlcreatebutton("Start", 100, 320, 100)
load_old_sodoku($aInputs)
GUIsetstate()
;====================>Mit GDI+ die Striche draufmalen
draw_lines()
readSudokuLine("160000000000300050040002000007000020000104000000060007002005000000080006000000001", $aInputs)
;======>
While 1
$nMsg = GUIgetmsg()
Switch $nMsg
Case -3 ;GUI_EVENT_CLOSE
Exit
Case $idStartBut
$aSodoku = get_array_of_sodoku($aInputs)
save_Sodoku_Ini($aSodoku)
MakeSodoku($aSodoku, $aInputs)
EndSwitch
Sleep(20)
WEnd

[/autoit] [autoit][/autoit] [autoit]

Func load_old_sodoku($aInputs)
If NOT FileExists("last_sodoku.ini") Then return -1
For $x = 0 To 8
For $y = 0 To 8
GUICtrlSetData($aInputs[$x][$y], Iniread("last_sodoku.ini", "section", $x&"|"&$y, ""))
Next
Next
return 0
endfunc

[/autoit] [autoit][/autoit] [autoit]

Func save_Sodoku_Ini($aSodoku)
For $x = 0 To 8
For $y = 0 To 8
If $aSodoku[$x][$y] <> 0 Then
Iniwrite("last_sodoku.ini", "section", $x&"|"&$y, $aSodoku[$x][$y])
Else
Iniwrite("last_sodoku.ini", "section", $x&"|"&$y, "")
endif
Next
Next
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func get_array_of_sodoku($aInputs)
Local $aSodoku[10][10]
For $x = 0 To 8 ;die nicht-existierende Reihe mit 0en auffüllen
$aSodoku[$x][9] = 0
Next
For $x = 0 To 8
For $y = 0 To 8
$aSodoku[$x][$y] = GUIctrlread($aInputs[$x][$y])
If $aSodoku[$x][$y] = "" Then $aSodoku[$x][$y] = 0
Next
Next
return $aSodoku
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func draw_lines()
_GDIPlus_Startup()
$hGraphics = _GDIPlus_GraphicsCreateFromHWND($hGui)
$hPen = _GDIPlus_PenCreate(0xFF000000, 3)
_GDIPlus_GraphicsDrawLine($hGraphics, 115, 20, 115, 300, $hPen) ;senkrecht
_GDIPlus_GraphicsDrawLine($hGraphics, 205, 20, 205, 300, $hPen) ;senkrecht
_GDIPlus_GraphicsDrawLine($hGraphics, 20, 115, 295, 115, $hPen) ;waagrecht
_GDIPlus_GraphicsDrawLine($hGraphics, 20, 205, 295, 205, $hPen) ;waagrecht
_GDIPlus_Shutdown()
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func array_drehen2D($array)
$er = $array
For $i = 0 To Ubound($array) -1
For $i2 = 0 To Ubound($array, 2) -1
$er[$i][$i2] = $array[$i2][$i]
Next
Next
return $er
EndFunc ;==>by Zeitriss

[/autoit] [autoit][/autoit] [autoit]

#endregion GUI

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

Func MakeSodoku($aFeld, $aInputs)
Local $aMerk[9][9] ;zum merken, welche Zahlen dort hin passen
While 1
$Ziffervoll = true
For $x = 0 To 8 ;==>Alle Ziffern setzen
For $y = 0 To 8
If $aFeld[$x][$y] = 0 Then
$Ziffervoll = False
$aMerk[$x][$y] = getpossibleNrs($aFeld, $x, $y)
Else
$aMerk[$x][$y] = ""
EndIf
Next
Next
If $Ziffervoll Then exitloop
;===>Alle Ziffern setzen, die eindeutig sind
For $x = 0 To 8 ;==>Alle Ziffern setzen
For $y = 0 To 8
If Stringlen($aMerk[$x][$y]) = 1 Then
$aFeld[$x][$y] = $aMerk[$x][$y]
$aMerk[$x][$y] = ""
EndIf
Next
Next
;~_ArrayDisplay(array_drehen2D($aFeld), "aFeld")
Sleep(5)
WEnd
;===========================>Berechnung ist beendet
;=======>Jetzt werden die Kontrollfelder ausgefüllt
For $x = 0 To 8
For $y = 0 To 8
GUIctrlsetdata($aInputs[$x][$y], $aFeld[$x][$y])
Next
Next
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func getpossibleNrs($aFeld, $iX_coord, $iY_coord)
$sCase = "123456789"
;========>Senkrechte
For $y = 0 To 8
If $aFeld[$iX_coord][$y] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX_coord][$y], "")
Next
;=========>Waagrechte
For $x = 0 To 8
If $aFeld[$x][$iY_coord] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$x][$iY_coord], "")
Next
;==============>Daten des 9er-Feldes bestimmen
If $iX_coord < 3 Then ;die Yer
$iX = 1
elseif $iX_coord > 5 Then
$iX = 7
elseif $iX_coord < 6 and $iX_coord > 2 Then
$iX = 4
EndIf
;=>
If $iY_coord < 3 Then ;die Yer
$iY = 1
elseif $iY_coord > 5 Then
$iY = 7
elseif $iY_coord < 6 and $iY_coord > 2 Then
$iY = 4
EndIf
;=========>9er-Feld
If $iX > 0 Then
If $aFeld[$iX-1][$iY] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX-1][$iY], "")
EndIf
If $iX < 9 Then
If $aFeld[$iX+1][$iY] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX+1][$iY], "")
EndIf
If $iX > 0 and $iY > 0 Then
If $aFeld[$iX-1][$iY-1] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX-1][$iY-1], "")
EndIf
If $iX < 9 and $iY > 0 Then
If $aFeld[$iX+1][$iY-1] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX+1][$iY-1], "")
EndIf
If $iY > 0 Then
If $aFeld[$iX][$iY-1] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX][$iY-1], "")
EndIf
If $iX < 9 and $iY < 9 Then
If $aFeld[$iX+1][$iY+1] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX+1][$iY+1], "")
EndIf
If $iX > 0 and $iY < 9 Then
If $aFeld[$iX-1][$iY+1] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX-1][$iY+1], "")
EndIf
If $iY < 9 Then
If $aFeld[$iX][$iY+1] <> 0 Then $sCase = Stringreplace($sCase, $aFeld[$iX][$iY+1], "")
EndIf
;=============>
return $sCase
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func readSudokuLine($sLine, $aInputs)
$aChars = StringSplit($sLine, "")
Local $aSudoku[10][10]
For $x = 0 To 8 ;die nicht-existierende Reihe mit 0en auffüllen
$aSudoku[$x][9] = 0
Next
;===================================>
Local $zaehler = 1
For $x = 0 To 8 ;es bringt leider nichts $x und $y in der Reihenfolge zu ändern
For $y = 0 To 8
$aSudoku[$x][$y] = $aChars[$zaehler]
$zaehler += 1
Next
Next
;~$aHelp = array_drehen2D($aSudoku)
;=======>Jetzt werden die Kontrollfelder ausgefüllt
For $x = 0 To 8
For $y = 0 To 8
If $aSudoku[$x][$y] <> 0 Then GUIctrlsetdata($aInputs[$x][$y], $aSudoku[$x][$y])
Next
Next
EndFunc

[/autoit]

mfg @night@

SEuBo

So klappts:

(und ich hab mal das GDI+ Zeugs ausgebaut, das war ja echt relativ unnötig)

Spoiler anzeigen

[autoit]

#include <Array.au3>
;=======================>
#region GUI
$hGUI = GUICreate("Sodoku", 300, 370)
Local $aInputs[9][9]
For $x = 0 To 8
For $y = 0 To 8
$left = ($x + 1) * 30
$top = ($y + 1) * 30
$aInputs[$x][$y] = GUICtrlCreateInput("", $left, $top, 20, 20)
Next
Next
$idStartBut = GUICtrlCreateButton("Start", 100, 320, 100)
load_old_sodoku($aInputs)
GUISetState()
;====================>Mit GDI+ die Striche draufmalen
draw_lines()
readSudokuLine("160000000000300050040002000007000020000104000000060007002005000000080006000000001", $aInputs)
;======>
While 1
$nMsg = GUIGetMsg()
Switch $nMsg
Case -3 ;GUI_EVENT_CLOSE
Exit
Case $idStartBut
$aSodoku = get_array_of_sodoku($aInputs)
save_Sodoku_Ini($aSodoku)
MakeSodoku($aSodoku, $aInputs)
EndSwitch
Sleep(20)
WEnd

[/autoit] [autoit][/autoit] [autoit]

Func load_old_sodoku($aInputs)
If Not FileExists("last_sodoku.ini") Then Return -1
For $x = 0 To 8
For $y = 0 To 8
GUICtrlSetData($aInputs[$x][$y], IniRead("last_sodoku.ini", "section", $x & "|" & $y, ""))
Next
Next
Return 0
EndFunc ;==>load_old_sodoku

[/autoit] [autoit][/autoit] [autoit]

Func save_Sodoku_Ini($aSodoku)
For $x = 0 To 8
For $y = 0 To 8
If $aSodoku[$x][$y] <> 0 Then
IniWrite("last_sodoku.ini", "section", $x & "|" & $y, $aSodoku[$x][$y])
Else
IniWrite("last_sodoku.ini", "section", $x & "|" & $y, "")
EndIf
Next
Next
EndFunc ;==>save_Sodoku_Ini

[/autoit] [autoit][/autoit] [autoit]

Func get_array_of_sodoku($aInputs)
Local $aSodoku[10][10]
For $x = 0 To 8 ;die nicht-existierende Reihe mit 0en auffüllen
$aSodoku[$x][9] = 0
Next
For $x = 0 To 8
For $y = 0 To 8
$aSodoku[$x][$y] = GUICtrlRead($aInputs[$x][$y])
If $aSodoku[$x][$y] = "" Then $aSodoku[$x][$y] = 0
Next
Next
Return $aSodoku
EndFunc ;==>get_array_of_sodoku

[/autoit] [autoit][/autoit] [autoit]

Func draw_lines()
GUICtrlSetBkColor(GUICtrlCreateLabel("", 114, 20, 3, 280), 0)
GUICtrlSetBkColor(GUICtrlCreateLabel("", 204, 20, 3, 280), 0)
GUICtrlSetBkColor(GUICtrlCreateLabel("", 20, 114, 275, 3), 0)
GUICtrlSetBkColor(GUICtrlCreateLabel("", 20, 204, 275, 3), 0)
EndFunc ;==>draw_lines

[/autoit] [autoit][/autoit] [autoit]

Func array_drehen2D($array)
$er = $array
For $i = 0 To UBound($array) - 1
For $i2 = 0 To UBound($array, 2) - 1
$er[$i][$i2] = $array[$i2][$i]
Next
Next
Return $er
EndFunc ;==>array_drehen2D

[/autoit] [autoit][/autoit] [autoit]

#endregion GUI

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

Func MakeSodoku($aFeld, $aInputs)
Local $aMerk[9][9] ;zum merken, welche Zahlen dort hin passen
While 1
$Ziffervoll = True
For $x = 0 To 8 ;==>Alle Ziffern setzen
For $y = 0 To 8
If $aFeld[$x][$y] = 0 Then
$Ziffervoll = False
$aMerk[$x][$y] = getpossibleNrs($aFeld, $x, $y)
Else
$aMerk[$x][$y] = ""
EndIf
Next
Next
If $Ziffervoll Then ExitLoop
;===>Alle Ziffern setzen, die eindeutig sind
For $x = 0 To 8 ;==>Alle Ziffern setzen
For $y = 0 To 8
If StringLen($aMerk[$x][$y]) = 1 Then
$aFeld[$x][$y] = $aMerk[$x][$y]
$aMerk[$x][$y] = ""
EndIf
Next
Next
;~_ArrayDisplay(array_drehen2D($aFeld), "aFeld")
Sleep(5)
WEnd
;===========================>Berechnung ist beendet
;=======>Jetzt werden die Kontrollfelder ausgefüllt
For $x = 0 To 8
For $y = 0 To 8
GUICtrlSetData($aInputs[$x][$y], $aFeld[$x][$y])
Next
Next
EndFunc ;==>MakeSodoku

[/autoit] [autoit][/autoit] [autoit]

Func getpossibleNrs($aFeld, $iX_coord, $iY_coord)
$sCase = "123456789"
;========>Senkrechte
For $y = 0 To 8
If $aFeld[$iX_coord][$y] <> 0 Then $sCase = StringReplace($sCase, $aFeld[$iX_coord][$y], "")
Next
;=========>Waagrechte
For $x = 0 To 8
If $aFeld[$x][$iY_coord] <> 0 Then $sCase = StringReplace($sCase, $aFeld[$x][$iY_coord], "")
Next
;==============>Daten des 9er-Feldes bestimmen
If $iX_coord < 3 Then ;die Yer
$iX = 1
ElseIf $iX_coord > 5 Then
$iX = 7
ElseIf $iX_coord < 6 And $iX_coord > 2 Then
$iX = 4
EndIf
;=>
If $iY_coord < 3 Then ;die Yer
$iY = 1
ElseIf $iY_coord > 5 Then
$iY = 7
ElseIf $iY_coord < 6 And $iY_coord > 2 Then
$iY = 4
EndIf
;=========>9er-Feld
If $iX > 0 Then
If $aFeld[$iX - 1][$iY] <> 0 Then $sCase = StringReplace($sCase, $aFeld[$iX - 1][$iY], "")
EndIf
If $iX < 9 Then
If $aFeld[$iX + 1][$iY] <> 0 Then $sCase = StringReplace($sCase, $aFeld[$iX + 1][$iY], "")
EndIf
If $iX > 0 And $iY > 0 Then
If $aFeld[$iX - 1][$iY - 1] <> 0 Then $sCase = StringReplace($sCase, $aFeld[$iX - 1][$iY - 1], "")
EndIf
If $iX < 9 And $iY > 0 Then
If $aFeld[$iX + 1][$iY - 1] <> 0 Then $sCase = StringReplace($sCase, $aFeld[$iX + 1][$iY - 1], "")
EndIf
If $iY > 0 Then
If $aFeld[$iX][$iY - 1] <> 0 Then $sCase = StringReplace($sCase, $aFeld[$iX][$iY - 1], "")
EndIf
If $iX < 9 And $iY < 9 Then
If $aFeld[$iX + 1][$iY + 1] <> 0 Then $sCase = StringReplace($sCase, $aFeld[$iX + 1][$iY + 1], "")
EndIf
If $iX > 0 And $iY < 9 Then
If $aFeld[$iX - 1][$iY + 1] <> 0 Then $sCase = StringReplace($sCase, $aFeld[$iX - 1][$iY + 1], "")
EndIf
If $iY < 9 Then
If $aFeld[$iX][$iY + 1] <> 0 Then $sCase = StringReplace($sCase, $aFeld[$iX][$iY + 1], "")
EndIf
;=============>
Return $sCase
EndFunc ;==>getpossibleNrs

[/autoit] [autoit][/autoit] [autoit]

Func readSudokuLine($sLine, $aInputs)
$aChars = StringSplit($sLine, "")
Local $i = 1
For $y = 0 To 8
For $x = 0 To 8
GUICtrlSetData($aInputs[$x][$y], $aChars[$i])
$i += 1
Next
Next
EndFunc ;==>readSudokuLine

[/autoit]

@night@

thx SEubo. Mhmm, do wies ausieht wird bei diesem Sudoku mein Alghorithmus nicht mehr funktionieren, weil es keine eindeutige Lösung gibt. Heisst: mein Programm braucht mindestens nen paar ansätze. Mal gucken ob ich das ganze mal mit Backtracking probiere, aber nicht jetzt^^
€dit: Ich hab das ganze mal mit nen paar anderen Sudokus von Andy probiert.
500004090020001000000030000031000008000005000008000000600700050004080000000000001

Aber auch diese sind mit deinem Alghorithmus unmöglich...

**Andy**

Da du zzt. keinerlei Strategien anwendest, werden die allermeisten Sudokus natürlich nicht gelöst. Beim Backtracken viel Erfolg!
Du kannst ja mal berichten, in welcher Zeit die "bösen" (s.o.) Sudokus gelöst wurden...mein BT hat sich bei zweien "totgelaufen", bzw ich habe nach einer bestimmten Zeit abgebrochen.