Sudoku-Lösungs-Skript (String-basierend)

oetzn

Beiträge

293
8. Juli 2010 um 18:11
- #1
Hi Leute,
Ich weis, dass es bereits ein µit daraüber gab, aber das hab ich erst gesehen, als ich schon fast fertig war
Derzeit unterstüzte Lösungsmethoden:
Jede Zahl darf in jeder Reihe nur einmal vorkommen.

Jede Zahl darf in jeder Spalte nur einmal vorkommen.

Jede Zahl darf in jedem Quadrat nur einmal vorkommen.

Sourcecode:

Spoiler anzeigen

[autoit]

#NoAutoIt3Execute
[/autoit] [autoit][/autoit] [autoit]
#include <EditConstants.au3>
#include <GUIConstantsEx.au3>
#include <Misc.au3>
[/autoit] [autoit][/autoit] [autoit]
Opt("GuiCloseOnEsc", 0)
Opt("GuiOnEventMode", 1)
Opt("MouseCoordMode", 2)
[/autoit] [autoit][/autoit] [autoit]
;~ If $CmdLine[0] > 1 And StringLen($CmdLine[1]) == 81 Then _Solve($CmdLine[1])
[/autoit] [autoit][/autoit] [autoit]
Global $aGuiInputs[81]
Global $aPossible[81]
Global Const $iGUISize = 500
Global Const $sEmptyChar = '0' ; nicht verändern!
Global Const $aPossibleChars[9] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Global Const $sPossibleChars = '123456789'
Global Const $sTitle = "SUDOKU-SOLVE-ENGINE by oetzn"
[/autoit] [autoit][/autoit] [autoit]
Global Const $bDebug = True
Global Const $bTime = True
[/autoit] [autoit][/autoit] [autoit]
$hGui = GUICreate($sTitle, $iGUISize, $iGUISize)
[/autoit] [autoit][/autoit] [autoit]
$Menu1 = GUICtrlCreateMenu("Sudoku")
GUICtrlCreateMenuItem("Einfügen", $Menu1)
GUICtrlSetOnEvent(-1, "_Insert")
GUICtrlCreateMenuItem("Lösen", $Menu1)
GUICtrlSetOnEvent(-1, "_Solve")
GUICtrlCreateMenuItem("Datei laden", $Menu1)
GUICtrlSetOnEvent(-1, "_LoadFile")
GUICtrlSetState(-1, $GUI_DISABLE)
GUICtrlCreateMenuItem("", $Menu1)
GUICtrlCreateMenuItem("Beenden", $Menu1)
GUICtrlSetOnEvent(-1, "_Exit")
$Menu2 = GUICtrlCreateMenu("Hilfe")
GUICtrlCreateMenuItem("Über", $Menu2)
[/autoit] [autoit][/autoit] [autoit]
_CreateInputs($iGUISize / 13)
[/autoit] [autoit][/autoit] [autoit]
GUISetState(@SW_SHOW, $hGui)
GUISetOnEvent(-3, "_Exit", $hGui)
[/autoit] [autoit][/autoit] [autoit]
HotKeySet("^v", "_SudokuFromClipboard")
[/autoit] [autoit][/autoit] [autoit]
While 1
Sleep(10)
WEnd
[/autoit] [autoit][/autoit] [autoit]
Func _CreateInputs($iSize)
Local $x, $y
Local $iXExtra, $iYExtra
Local $iCounter = 0
[/autoit] [autoit][/autoit] [autoit]
For $x = 1 To 9
For $y = 1 To 9
$aGuiInputs[$iCounter] = GUICtrlCreateInput("", $y * $iSize + $iYExtra, $x * $iSize + $iXExtra, $iSize, $iSize, BitAND($ES_CENTER, $ES_NUMBER))
$iCounter += 1
GUICtrlSetFont(-1, $iSize / 2)
If Mod($y, 3) = 0 Then $iYExtra += $iSize
Next
$iYExtra = 0
If Mod($x, 3) = 0 Then $iXExtra += $iSize
Next
EndFunc ;==>_CreateInputs
[/autoit] [autoit][/autoit] [autoit]
Func _GetContent()
If Not IsArray($aGuiInputs) Then Return
Local $sSudoku
[/autoit] [autoit][/autoit] [autoit]
For $x = 0 To 80
If GUICtrlRead($aGuiInputs[$x]) = '' Then
$sSudoku &= $sEmptyChar
Else
$sSudoku &= GUICtrlRead($aGuiInputs[$x])
EndIf
Next
Return $sSudoku
EndFunc ;==>_GetContent
[/autoit] [autoit][/autoit] [autoit]
Func _Insert()
$sRet = InputBox("Sudoku einfügen!", "Bitte geben Sie hier einen String aus 81 Zahlen ein." & @LF & "Der String wird von links nach rechts eingetragen!")
If @error Then Return
If Not _ValidateSudoku($sRet) Then
MsgBox(16, "ERROR", "Ein Fehler ist aufgetreten!" & @CRLF & "Das Sudoku ist nicht gültig!", 5)
Return
EndIf
[/autoit] [autoit][/autoit] [autoit]
For $x = 0 To 80
$sTempChar = StringLeft($sRet, 1)
$sRet = StringTrimLeft($sRet, 1)
If $sTempChar = $sEmptyChar Then
$aPossible[$x] = $sPossibleChars
ContinueLoop
EndIf
GUICtrlSetData($aGuiInputs[$x], '')
GUICtrlSetData($aGuiInputs[$x], $sTempChar)
$aPossible[$x] = $sTempChar
Next
[/autoit] [autoit][/autoit] [autoit]
If $bDebug Then AdlibRegister("_Debug", 10)
[/autoit] [autoit][/autoit] [autoit]
EndFunc ;==>_Insert
[/autoit] [autoit][/autoit] [autoit]
Func _Solve()
Local $sSudoku = _GetContent()
[/autoit] [autoit][/autoit] [autoit]
If Not _ValidateSudoku($sSudoku) Then
MsgBox(16, "ERROR", "Ein Fehler ist aufgetreten!" & @CRLF & "Das Sudoku ist nicht gültig!")
Return
EndIf
[/autoit] [autoit][/autoit] [autoit]
Do
[/autoit] [autoit][/autoit] [autoit]
$iEmptyFields = __Solve_Method_CheckChange()
[/autoit] [autoit][/autoit] [autoit]
__Solve_Method_EliminatePossibilitesInRow($sSudoku)
__Solve_Method_EliminatePossibilitesInColumn($sSudoku)
__Solve_Method_EliminatePossibilitesInSquare($sSudoku)
[/autoit] [autoit][/autoit] [autoit]
__Solve_Method_OnlyOneOccurenceInRow()
__Solve_Method_OnlyOneOccurenceInColumn()
__Solve_Method_OnlyOneOccurenceInSquare()
[/autoit] [autoit][/autoit] [autoit]
__Solve_Method_CheckForSinglePoss()
[/autoit] [autoit][/autoit] [autoit]
Until $iEmptyFields == __Solve_Method_CheckChange()
[/autoit] [autoit][/autoit] [autoit]
EndFunc ;==>_Solve
[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]
Func __Solve_Method_EliminatePossibilitesInRow($sInput)
; by oetzn (autoit.de)
[/autoit] [autoit][/autoit] [autoit]
If Not _ValidateSudoku($sInput) Then Return
Local $iCount
Local $iPos
Local $sTempRow
[/autoit] [autoit][/autoit] [autoit]
If $bTime Then $TempTimer = TimerInit()
[/autoit] [autoit][/autoit] [autoit]
For $i = 1 To 81 Step 9
$sTempRow = StringMid($sInput, $i, 9)
For $j = 1 To 9
$iCount = 0
$iPos = ''
For $k = 1 To 9
If StringMid($sTempRow, $k, 1) == $j Then
$iCount += 1
$iPos = $k
EndIf
Next
If $iCount == 1 Then
For $m = 1 To 9
If $m == $iPos Then ContinueLoop
$aPossible[$i + $m - 2] = StringReplace($aPossible[$i + $m - 2], String($j), '')
Next
EndIf
Next
Next
[/autoit] [autoit][/autoit] [autoit]
If $bTime Then ConsoleWrite("__Solve_Method_EliminatePossibilitesInRow: " & TimerDiff($TempTimer) & " ms " & @CRLF)
[/autoit] [autoit][/autoit] [autoit]
EndFunc ;==>__Solve_Method_EliminatePossibilitesInRow
[/autoit] [autoit][/autoit] [autoit]
Func __Solve_Method_EliminatePossibilitesInColumn($sInput)
; by oetzn (autoit.de)
[/autoit] [autoit][/autoit] [autoit]
If Not _ValidateSudoku($sInput) Then Return
[/autoit] [autoit][/autoit] [autoit]
Local $iPosInStr = 1
Local $sTempColumn
[/autoit] [autoit][/autoit] [autoit]
If $bTime Then $TempTimer = TimerInit()
[/autoit] [autoit][/autoit] [autoit]
For $iOffset = 0 To 8
$sTempColumn = ''
[/autoit] [autoit][/autoit] [autoit]
For $i = 1 To 81 Step 9
$sTempColumn &= StringMid($sInput, $i + $iOffset, 1)
Next
[/autoit] [autoit][/autoit] [autoit]
For $j = 1 To 9
$iCount = 0
$iPos = ''
For $k = 1 To 9
If StringMid($sTempColumn, $k, 1) == $j Then
$iCount += 1
$iPos = $k
EndIf
Next
If $iCount == 1 Then
For $m = 1 To 9
If $m == $iPos Then ContinueLoop
$aPossible[$iPosInStr + ($m - 1) * 9 - 1] = StringReplace($aPossible[$iPosInStr + ($m - 1) * 9 - 1], String($j), '')
Next
EndIf
Next
$iPosInStr += 1
Next
[/autoit] [autoit][/autoit] [autoit]
If $bTime Then ConsoleWrite("__Solve_Method_EliminatePossibilitesInColumn: " & TimerDiff($TempTimer) & " ms " & @CRLF)
[/autoit] [autoit][/autoit] [autoit]
EndFunc ;==>__Solve_Method_EliminatePossibilitesInColumn
[/autoit] [autoit][/autoit] [autoit]
Func __Solve_Method_EliminatePossibilitesInSquare($sInput)
; by oetzn (autoit.de)
[/autoit] [autoit][/autoit] [autoit]
If Not _ValidateSudoku($sInput) Then Return
[/autoit] [autoit][/autoit] [autoit]
Local $aParts[27]
Local $iCounter = 0
Local $sTempSquare
Local $iOffsetExt
[/autoit] [autoit][/autoit] [autoit]
If $bTime Then $TempTimer = TimerInit()
[/autoit] [autoit][/autoit] [autoit]
For $i = 1 To 81 Step 3
$aParts[$iCounter] = StringMid($sInput, $i, 3)
$iCounter += 1
Next
[/autoit] [autoit][/autoit] [autoit]
For $iOffsetBig = 0 To 26 Step 9
For $iOffsetSmall = 0 To 2
$sTempSquare = ''
For $i = 0 To 8 Step 3
$sTempSquare &= $aParts[$i + $iOffsetSmall + $iOffsetBig]
Next
[/autoit] [autoit][/autoit] [autoit]
For $j = 1 To 9
$iCount = 0
$iPos = ''
For $k = 1 To 9
If StringMid($sTempSquare, $k, 1) == $j Then
$iCount += 1
$iPos = $k
EndIf
Next
If $iCount == 1 Then
For $m = 1 To 9
If $m == $iPos Then ContinueLoop
$iOffsetExt = 0
Select
Case $m <= 3
$iOffsetExt = 0
Case $m > 3 And $m <= 6
$iOffsetExt = 5 + $m
Case $m >= 7
$iOffsetExt = 11 + $m
EndSelect
$aPossible[$iOffsetBig * 3 + $iOffsetSmall * 3 + $iOffsetExt] = StringReplace($aPossible[$iOffsetBig * 3 + $iOffsetSmall * 3 + $iOffsetExt], String($j), '')
Next
EndIf
Next
[/autoit] [autoit][/autoit] [autoit]
Next
Next
[/autoit] [autoit][/autoit] [autoit]
If $bTime Then ConsoleWrite("__Solve_Method_EliminatePossibilitesInSquare: " & TimerDiff($TempTimer) & " ms " & @CRLF)
[/autoit] [autoit][/autoit] [autoit]
EndFunc ;==>__Solve_Method_EliminatePossibilitesInSquare
[/autoit] [autoit][/autoit] [autoit]
Func __Solve_Method_OnlyOneOccurenceInRow()
; by oetzn (autoit.de)
[/autoit] [autoit][/autoit] [autoit]
Local $iCount
Local $iPos
[/autoit] [autoit][/autoit] [autoit]
If $bTime Then $TempTimer = TimerInit()
[/autoit] [autoit][/autoit] [autoit]
For $i = 0 To 80 Step 9
For $j = 1 To 9
$iCount = 0
$iPos = ''
For $k = $i To $i + 8
If StringInStr($aPossible[$k], String($j)) Then
$iCount += 1
$iPos = $k
EndIf
Next
If $iCount == 1 Then $aPossible[$iPos] = String($j)
Next
Next
[/autoit] [autoit][/autoit] [autoit]
If $bTime Then ConsoleWrite("__Solve_Method_OnlyOneOccurenceInRow: " & TimerDiff($TempTimer) & " ms " & @CRLF)
[/autoit] [autoit][/autoit] [autoit]
EndFunc ;==>__Solve_Method_OnlyOneOccurenceInRow
[/autoit] [autoit][/autoit] [autoit]
Func __Solve_Method_OnlyOneOccurenceInColumn()
; by oetzn (autoit.de)
[/autoit] [autoit][/autoit] [autoit]
Local $iCount
Local $iPos
[/autoit] [autoit][/autoit] [autoit]
If $bTime Then $TempTimer = TimerInit()
[/autoit] [autoit][/autoit] [autoit]
For $iOffset = 0 To 8
For $j = 1 To 9
$iCount = 0
$iPos = ''
For $i = 0 To 80 Step 9
If StringInStr($aPossible[$i + $iOffset], String($j)) Then
$iCount += 1
$iPos = $i + $iOffset
EndIf
Next
If $iCount == 1 Then $aPossible[$iPos] = String($j)
Next
Next
[/autoit] [autoit][/autoit] [autoit]
If $bTime Then ConsoleWrite("__Solve_Method_OnlyOneOccurenceInColumn: " & TimerDiff($TempTimer) & " ms " & @CRLF)
[/autoit] [autoit][/autoit] [autoit]
EndFunc ;==>__Solve_Method_OnlyOneOccurenceInColumn
[/autoit] [autoit][/autoit] [autoit]
Func __Solve_Method_OnlyOneOccurenceInSquare()
; by oetzn (autoit.de)
[/autoit] [autoit][/autoit] [autoit]
Local $iCount
Local $iPos
[/autoit] [autoit][/autoit] [autoit]
If $bTime Then $TempTimer = TimerInit()
[/autoit] [autoit][/autoit] [autoit]
For $iOffset1 = 0 To 54 Step 27
For $iOffset2 = 0 To 6 Step 3
For $j = 1 To 9
$iCount = 0
$iPos = ''
For $iOffset3 = 0 To 18 Step 9
For $iOffset4 = 0 To 2
If StringInStr($aPossible[$iOffset1 + $iOffset2 + $iOffset3 + $iOffset4], $j) Then
$iCount += 1
$iPos = $iOffset1 + $iOffset2 + $iOffset3 + $iOffset4
EndIf
Next
Next
If $iCount == 1 Then $aPossible[$iPos] = String($j)
Next
Next
Next
[/autoit] [autoit][/autoit] [autoit]
If $bTime Then ConsoleWrite("__Solve_Method_OnlyOneOccurenceInColumn: " & TimerDiff($TempTimer) & " ms " & @CRLF)
[/autoit] [autoit][/autoit] [autoit]
EndFunc ;==>__Solve_Method_OnlyOneOccurenceInSquare
[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]
Func __Solve_Method_CheckForSinglePoss()
[/autoit] [autoit][/autoit] [autoit]
If $bTime Then $TempTimer = TimerInit()
[/autoit] [autoit][/autoit] [autoit]
For $i = 0 To 80
If StringLen($aPossible[$i]) == 1 Then GUICtrlSetData($aGuiInputs[$i], $aPossible[$i])
Next
[/autoit] [autoit][/autoit] [autoit]
If $bTime Then ConsoleWrite("__Solve_Method_CheckForSinglePoss: " & TimerDiff($TempTimer) & " ms " & @CRLF)
[/autoit] [autoit][/autoit] [autoit]
EndFunc ;==>__Solve_Method_CheckForSinglePoss
[/autoit] [autoit][/autoit] [autoit]
Func __Solve_Method_CheckChange()
Local $iEmptyCounter = 0
For $i = 0 To 80
If StringLen($aPossible[$i]) > 1 Then $iEmptyCounter += 1
Next
[/autoit] [autoit][/autoit] [autoit]
Return $iEmptyCounter
EndFunc ;==>__Solve_Method_CheckChange
[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]
Func _ValidateSudoku($sInput)
; by oetzn (autoit.de)
Local $bValid = True
[/autoit] [autoit][/autoit] [autoit]
If StringRegExp($sInput, '[^0-9]', 0) = 1 Then $bValid = False
If StringLen($sInput) <> 81 Then $bValid = False
If Not IsString($sInput) Then $bValid = False
[/autoit] [autoit][/autoit] [autoit]
Return $bValid
EndFunc ;==>_ValidateSudoku
[/autoit] [autoit][/autoit] [autoit]
Func _Debug()
$aInfo = GUIGetCursorInfo($hGui)
If $aInfo[4] > 0 Then
For $i = 0 To UBound($aGuiInputs, 1) - 1
If $aGuiInputs[$i] == $aInfo[4] Then ExitLoop
Next
ToolTip("Possbile Chars: " & $aPossible[$i])
Else
ToolTip("")
EndIf
EndFunc ;==>_Debug
[/autoit] [autoit][/autoit] [autoit]
Func _SudokuFromClipboard()
Local $sClipboard = ClipGet()
If WinGetTitle("[ACTIVE]", "") == $sTitle Then
If _ValidateSudoku($sClipboard) Then
For $x = 0 To 80
$sTempChar = StringLeft($sClipboard, 1)
$sClipboard = StringTrimLeft($sClipboard, 1)
If $sTempChar = $sEmptyChar Then
$aPossible[$x] = $sPossibleChars
ContinueLoop
EndIf
GUICtrlSetData($aGuiInputs[$x], '')
GUICtrlSetData($aGuiInputs[$x], $sTempChar)
$aPossible[$x] = $sTempChar
Next
Else
MsgBox(16, "ERROR", "Ein Fehler ist aufgetreten!" & @CRLF & "Das Sudoku ist nicht gültig!", 2)
Return
EndIf
[/autoit] [autoit][/autoit] [autoit]
If $bDebug Then AdlibRegister("_Debug", 10)
[/autoit] [autoit][/autoit] [autoit]
Else
HotKeySet("^v")
Send("^v")
HotKeySet("^v", "_SudokuFromClipboard")
EndIf
EndFunc ;==>_SudokuFromClipboard
[/autoit] [autoit][/autoit] [autoit]
Func _LoadFile()
Sleep(10)
EndFunc ;==>_LoadFile
[/autoit] [autoit][/autoit] [autoit]
Func _Exit()
Exit
EndFunc ;==>_Exit
[/autoit]

Aufgrund der noch spärlich Ausstattung mit Lösungswegen, kann das Skript natürlich nicht alle Sudokus lösen, aber mit einfach kommt es schon zurecht
Bedienung:
Möglichkeit 1:
Ihr tippt die Zahlen direkt in die Inputfelder ein. (Mit Tab usw)
Möglichkeit 2:
Ihr klickt auf den Menübutton 'Sudoku' und wählt 'Einfügen'.
Hier müsst ihr dann das Sudoku eingeben in folgender Form:
Von links nach rechts gelesen. Links oben beginnend. Jeder Leerstelle ist eine '0'.
Möglichkeit 3:
Ihr kopiert einen solchen Sudokustring in die Zwischenablage, setzt das Fenster in den Vordergrund und drückt 'STRG + V'
Neuerungen die noch kommen:
Mehr Lösungswege

Abspeichern von Sudokus ermöglichen

Abarbeiten von einer Datei, die mehere Sudoku-Strings enthält

Viel Spaß damit
Konstruktive Kritik, Lob & Verbesserungsvorschläge sind gerne gesehen
Dateien

Sudoku.au3 10,95 kB – 418 Downloads

UDFs:
VLC MEDIA PLAYER - OBJEKT
Skripte:
TCP MULTICHAT
PROGRAMMDATENBANK
GDI+ Snake
Sudoku-Lösungs-Skript
oetzn

Beiträge

293
10. Juli 2010 um 11:31
- #2
50 Zugriffe & 7 Downloads und keine Rückmeldung ? =(
UDFs:
VLC MEDIA PLAYER - OBJEKT
Skripte:
TCP MULTICHAT
PROGRAMMDATENBANK
GDI+ Snake
Sudoku-Lösungs-Skript

In deinem Webbrowser ist JavaScript deaktiviert. Um alle Funktionen dieser Website nutzen zu können, muss JavaScript aktiviert sein.