Jump to content

Sudoku Solution Calculator Gone MAD!

Decipher

By Decipher
in AutoIt General Help and Support

 Share

Recommended Posts

Decipher Universalist

Decipher

Posted
Posted (edited)

I've been working on this fun project for a few hours as it turns out its not so fun anymore. LOL but I'm determined. Does anyone got ideas why this isn't working? I know that there is a rule missing, I didn't get that far. Thanks for your help :)

#include <GUIConstantsEx.au3>
#include <WindowsConstants.au3>
#include <EditConstants.au3>
#include <Array.au3>

Opt("GUIOnEventMode", 1)

; My idea is that of a graph with x,y cordinates. One array points to the edit control handles the other their values while they wait to put inside the GUI.

Dim $aSudoku[9][9], $aSudoku_Value[9][9][2] ; The reason this array was created is for two very goods reason, one to prevent unnecessary processing and two I need a fool proof way to distinguish between fixed values.
Dim $iDemension = 0, $iIndex = 0 ;;;The first index numbers for the control array. ;$Sudoku_Solved = False
; $iDemension is just a variable name. The $aSudoku array is only 2D name value pairs
AdlibRegister("_Populate_Sudoku", 250) ; This function reads numbers from the $aSudoku_Value 3D array and puts them inside the edit controls

#region ### START Koda GUI section ### Form=
$Sudoku = GUICreate("Sudoku Solution Calculator", 335, 340) ; Create Sudoku GUI
Dim $iLeft = 10, $iTop = 10 ; Intial cordinates for the first edit control - box.
For $i = 1 To 81 Step 1 ; The games calls for a graph that consists of 81 squares = 9x9
$aSudoku[$iDemension][$iIndex] = GUICtrlCreateEdit("", $iLeft, $iTop, 35, 35, BitOR("", $ES_CENTER))
GUICtrlSetState(-1, @SW_LOCK)
GUICtrlSetFont(-1, 16, 700, "Arial Black")
GUICtrlSetBkColor(-1, 0xFFFFFF)
GUICtrlSetColor(-1, 000000)
$iLeft += 35 ; for each iteration step or move the new box 35 px to the right.
$iIndex += 1 ; $iIndex is only from 0 to 8 until $i reaches a multiple of 9
For $iAdjust = 1 To 9 Step 1
If $iAdjust * 9 = $i Then
$iIndex = 0 ; reset the index to 0 for enumerating another row through columns I think...lmao, it works
$iDemension += 1 ; changes to the next row
$iLeft = 10 ; reset the pos for another row.
$iTop += 35 ; bring the position on the new row down a notch as necessary.
EndIf
Next
Next

_Create_Fixed_Value(0, 2, 4) ; Param1 = x cord, Param2 = y cord, Param3 = fixed number who's value should not change during execution.
_Create_Fixed_Value(0, 3, 2)
_Create_Fixed_Value(0, 4, 6)
_Create_Fixed_Value(0, 6, 1)
_Create_Fixed_Value(1, 6, 2)
_Create_Fixed_Value(1, 7, 6)
_Create_Fixed_Value(2, 0, 5)
_Create_Fixed_Value(2, 3, 1)
_Create_Fixed_Value(2, 5, 3)
_Create_Fixed_Value(2, 6, 8)
_Create_Fixed_Value(2, 8, 9)
_Create_Fixed_Value(3, 1, 5)
_Create_Fixed_Value(3, 2, 6)
_Create_Fixed_Value(3, 3, 8)
_Create_Fixed_Value(3, 7, 2)
_Create_Fixed_Value(3, 8, 7)
_Create_Fixed_Value(4, 3, 7)
_Create_Fixed_Value(4, 5, 5)
_Create_Fixed_Value(5, 0, 9)
_Create_Fixed_Value(5, 1, 7)
_Create_Fixed_Value(5, 5, 4)
_Create_Fixed_Value(5, 6, 5)
_Create_Fixed_Value(5, 7, 3)
_Create_Fixed_Value(6, 0, 6)
_Create_Fixed_Value(6, 2, 5)
_Create_Fixed_Value(6, 3, 9)
_Create_Fixed_Value(6, 5, 2)
_Create_Fixed_Value(6, 8, 8)
_Create_Fixed_Value(7, 1, 2)
_Create_Fixed_Value(7, 2, 7)
_Create_Fixed_Value(8, 2, 1)
_Create_Fixed_Value(8, 4, 5)
_Create_Fixed_Value(8, 5, 6)
_Create_Fixed_Value(8, 6, 7)


GUISetState(@SW_SHOW) ; show the GUI
#endregion ### END Koda GUI section ###

GUISetOnEvent($GUI_EVENT_CLOSE, "_Exit_Sudoku") ; register the exit function



While 1
If Not IsComplete() Then _Random_Evalulation() ; randomly populate squares with numbers that do not conflict.
Sleep(50)
WEnd

Func _Exit_Sudoku()
Exit
EndFunc ;==>_Exit_Sudoku

; obviously there is a problem with randomizing instead of a programmatic educated quess.

Func _TryDigit($aSquare, $iDigit) ; Generate random digit and check for duplication - as to follow the instructions on solving the puzzle.
If $aSudoku_Value[$aSquare[0]][$aSquare[1]][1] = False Then ; this line checks to see if the index contains a fixed number if not than set the value to the random digit.
$aSudoku_Value[$aSquare[0]][$aSquare[1]][0] = $iDigit
EndIf
Local $iHorizontal = _Horizontal_Valid($aSquare, $iDigit) ; this function will return the one of the indexes to the array contain a handle to a duplicate upon failure.
Local $iVertical = _Vertical_Valid($aSquare, $iDigit)
If $iHorizontal = "" And $iVertical = "" Then
Return True
ElseIf $iHorizontal <> "" Then
$aSquare[1] = $iHorizontal
For $iDigit = 1 To 9
If _Horizontal_Valid($aSquare, $iDigit) = "" Then ExitLoop
If $iDigit = 9 Then $aSudoku_Value[$aSquare[0]][$aSquare[1]][0] = ""
Next
ElseIf $iVertical <> "" Then
$aSquare[0] = $iVertical
For $iDigit = 1 To 9
If _Vertical_Valid($aSquare, $iDigit) = "" Then ExitLoop
If $iDigit = 9 Then $aSudoku_Value[$aSquare[0]][$aSquare[1]][0] = ""
Next
EndIf
EndFunc ;==>_TryDigit

Func _Empty_Sudoku() ; empty the contents of the value array except for the fixed numbers.
For $iCtrl = 0 To 8 Step 1
For $iCtrl_Index = 0 To 8 Step 1
If $aSudoku_Value[$iCtrl][$iCtrl_Index][1] = False Then
$aSudoku_Value[$iCtrl][$iCtrl_Index][0] = ""
EndIf
Next
Next
EndFunc ;==>_Empty_Sudoku

Func IsComplete()
Local $aSquare[2]
For $aSquare[0] = 0 To 8 Step 1
For $aSquare[1] = 0 To 8 Step 1
If $aSudoku_Value[$aSquare[0]][$aSquare[1]][1] = False Then
If _Horizontal_Valid($aSquare, $aSudoku_Value[$aSquare[0]][$aSquare[1]][0]) <> "" Or _Vertical_Valid($aSquare, $aSudoku_Value[$aSquare[0]][$aSquare[1]][0]) <> "" Then Return False
EndIf
Next
Next
EndFunc ;==>IsComplete

Func _Horizontal_Valid($aSquare, $iDigit)
For $iSquare = 0 To 8
If $aSquare[1] <> $iSquare Then
If $aSudoku_Value[$aSquare[0]][$iSquare][0] = $iDigit Then
If $aSudoku_Value[$aSquare[0]][$iSquare][1] = False Then Return $iSquare
Return $aSquare[1]
EndIf
EndIf
Next
Return ""
EndFunc ;==>_Horizontal_Valid

Func _Vertical_Valid($aSquare, $iDigit)
For $iSquare = 0 To 8
If $aSquare[0] <> $iSquare Then
If $aSudoku_Value[$iSquare][$aSquare[1]][0] = $iDigit Then
If $aSudoku_Value[$iSquare][$aSquare[1]][1] = False Then Return $iSquare
Return $aSquare[0]
EndIf
EndIf
Next
Return ""
EndFunc ;==>_Vertical_Valid


Func _Random_Evalulation()
_Empty_Sudoku()
For $i = 1 To 100 Step 1
While 1
$aSquare = _Random_Square()
If Not IsPopulated($aSquare) Then ExitLoop
WEnd
For $iDigit = 1 To 9
If _TryDigit($aSquare, $iDigit) Then ExitLoop
If $iDigit = 9 Then $aSudoku_Value[$aSquare[0]][$aSquare[1]][0] = ""
Next
Next
EndFunc ;==>_Random_Evalulation

Func _Random_Square() ; take note of what this function is doing and is pretty straight forward as to whats being done.
Local $aCord[2] = [Int(Random(0, 9)), Int(Random(0, 9))]
Return $aCord
EndFunc ;==>_Random_Square

Func _Populate_Sudoku()
For $iCtrl = 0 To 8 Step 1
For $iCtrl_Index = 0 To 8 Step 1
If $aSudoku_Value[$iCtrl][$iCtrl_Index][0] <> "" And $aSudoku_Value[$iCtrl][$iCtrl_Index][1] = False Then
If $aSudoku_Value[$iCtrl][$iCtrl_Index][0] <> GUICtrlRead($aSudoku[$iCtrl][$iCtrl_Index]) Then
GUICtrlSetData($aSudoku[$iCtrl][$iCtrl_Index], $aSudoku_Value[$iCtrl][$iCtrl_Index][0])
EndIf
EndIf
Next
Next
EndFunc ;==>_Populate_Sudoku

Func _Create_Fixed_Value($X, $Y, $iValue)
$aSudoku_Value[$X][$Y][0] = $iValue ; the 0 index contains the number values
$aSudoku_Value[$X][$Y][1] = True ; is this last index is set to true then its a fixed value otherwise the value is automatically false.
GUICtrlSetData($aSudoku[$X][$Y], $aSudoku_Value[$X][$Y][0])
GUICtrlSetColor($aSudoku[$X][$Y], 0xFF0000) ; paint them red.
;$sFixed_Values += "{" & $X & "," & $Y & "}" ; this line is redundant; I should have removed this when I converted to a 3d array for distinguishing between them.
EndFunc ;==>_Create_Fixed_Value


Func IsPopulated($aSquare) ; I don't think this works but run this thing and see what happens. I have successfully generated a correct answering following the row and column rules only once but the harder I try the worst it runs.
;I think I need to change tactics. Thanks for reading and suggestion.
If $aSudoku_Value[$aSquare[0]][$aSquare[1]][0] <> "" Then Return True
EndFunc ;==>IsPopulated

Sorry, I couldn't get the tidied code inserted properly. But uh this isn't that complicated... ;)

Edited by Decipher
  Reveal hidden contents

 

MvGulik Universalist

MvGulik

Posted
Posted
  On 11/13/2012 at 8:50 PM, 'Decipher said:

why this isn't working?

General suggestion: Be a bit more specific in what it is doing wrong, and what it is your expecting it to do instead.

"Straight_and_Crooked_Thinking" : A "classic guide to ferreting out untruths, half-truths, and other distortions of facts in political and social discussions."
"The Secrets of Quantum Physics" : New and excellent 2 part documentary on Quantum Physics by Jim Al-Khalili. (Dec 2014)

"Believing what you know ain't so" ...

Knock Knock ...
 

Decipher Universalist

Decipher

Posted
  • Author
Posted

Sudoku rules

- Sudoku is played over a 9x9 grid, divided to 3x3 sub grids called "regions":

Posted Image

- Sudoku begins with some of the grid cells already filled with numbers:

- The object of Sudoku is to fill the other empty cells with numbers between 1 and 9 (1 number only in each cell) according the following guidelines:

1. Number can appear only once on each row

2. Number can appear only once on each column: Allowed

Not allowed

Posted Image Posted Image Posted Image Posted Image

3. Number can appear only once on each region: Allowed

Not allowed

Posted Image Posted Image Posted Image Posted Image

- A summary of these guidelines would be, that a number should appear only once on each row, column and a region.

I can edit the initial post with code comments if necessary.

I have attempted to populate a box with fixed numbers that followed the rules with exception to the 3x3 region rule.

It does not work. I question my methods. I'm hoping that someone can offer some helpful advice.

Thanks

  Reveal hidden contents

 

Decipher Universalist

Decipher

Posted
  • Author
Posted (edited)

Thanks, I was wondering why I couldn't hit the "X". Lol I should've caught that.

The problem is that my script is not coming close to solving the puzzle with just the first two rules in places.

Edited by Decipher
  Reveal hidden contents

 

JohnOne Universalist

JohnOne

Posted
Posted

If you leave it running for 1 billion years or 3 it might solve, because it is entirely random.

It's like the monkies writing a shakespear novel cliche.

For a starting point, look at what numbers are being tried in 1 row and colum

for example row 1 colum 1, do you see a number being tried that is already a fixed number

in both the row and the colum? because I do.

You might want to check for that.

AutoIt Absolute Beginners    Require a serial    Pause Script    Video Tutorials by Morthawt   ipify 

Monkey's are, like, natures humans.

czardas Universalist

czardas

Posted
Posted (edited)

I'll tell you what is wrong - your AI is totally random (that's the problem - which John identified as I was writing this). Start by identifying candidate values for each available square. Perhaps you could start with a 9x9x7 cube and fill the third dimension with candidate values, then take it from there.

Edited by czardas

operator64  ArrayWorkshop

JohnOne Universalist

JohnOne

Posted
Posted (edited)

Also, you might want to think about whether your fixed numbers are actually solvable.

For an exercise, first try to create a filled valid sudoku grid from scratch which is started with a random seed in one square.

EDIT: which I think is what czardas just said.

Edited by JohnOne

AutoIt Absolute Beginners    Require a serial    Pause Script    Video Tutorials by Morthawt   ipify 

Monkey's are, like, natures humans.

BrewManNH Universalist

BrewManNH

Posted
Posted

You might get a few ideas from that Mat posted a few years ago for a Sudoku solver script. Or even this batch file that supposedly solves the puzzles.

If I posted any code, assume that code was written using the latest release version unless stated otherwise. Also, if it doesn't work on XP I can't help with that because I don't have access to XP, and I'm not going to.
Give a programmer the correct code and he can do his work for a day. Teach a programmer to debug and he can do his work for a lifetime - by Chirag Gude
How to ask questions the smart way!

  Reveal hidden contents

I hereby grant any person the right to use any code I post, that I am the original author of, on the autoitscript.com forums, unless I've specifically stated otherwise in the code or the thread post. If you do use my code all I ask, as a courtesy, is to make note of where you got it from.

Back up and restore Windows user files _Array.au3 - Modified array functions that include support for 2D arrays.  -  ColorChooser - An add-on for SciTE that pops up a color dialog so you can select and paste a color code into a script.  -  Customizable Splashscreen GUI w/Progress Bar - Create a custom "splash screen" GUI with a progress bar and custom label.  -  _FileGetProperty - Retrieve the properties of a file  -  SciTE Toolbar - A toolbar demo for use with the SciTE editor  -  GUIRegisterMsg demo - Demo script to show how to use the Windows messages to interact with controls and your GUI.  -   Latin Square password generator

czardas Universalist

czardas

Posted
Posted (edited)

My idea may not be the best approach but it's interesting to consider. I now see that my 9x9x7 cube (based on the above puzzle) would have to be 9x9x10 (after looking at the variety of examples). The first grid would hold the puzzle and the remaining 9 grids would hold all possible missing values. Any field intersected by a completely empty row and (empty) column would have 9 possible candidate values (with entries through grids 1 to 9). Next I would look for an empty field with the least number of candidate solutions and start to build a tree of possible solutions. The branches that lead nowhere may need to be cleared from memory as you go. It could take a long time.

Edited by czardas

operator64  ArrayWorkshop

Decipher Universalist

Decipher

Posted
  • Author
Posted

Thanks for all the useful information m8s. This is absolutely an exercise in logic. While working an 12 hour grave-yard shift I've decided on a new system for generating the solutions. The code above is illogical as it is generates and attempts to validate digits at random this only adds to the number of possibilities and as JohnOne Stated it could take a tremendous amount of time and never once come close to solving the puzzle.

I'm now going to use a Fixed System:

Requiring two more 2D arrays - one horizontal and the other vertical where the structure is outlined below:

Global $Fixed_Horizontal[9][4]

Horizontal 9x4 should contain each rows information or if you will its probabillity - this is what the count is for.

-----------------------------------------------------------------------

|Rows 0 to 8|Fixed Digits|Possible Digits|Available Count|

-----------------------------------------------------------------------

For ex. lets say row 5 which would be in my array system index 4 because of the zero based arrays, contains the fixed digits

"456987" then the Possible digits in

Global $Fixed_Horizontal[4][2]

would contain "123" and the available count is 3.

Knowing the available count is in my logic is the same as the knowing probability of finding what I call a Fixed number.

Using min/max functions I can determine the row or column to be analyzed firstly. Then the digit to be checked against the other digits must be an available digit. I would then iterate through all of the available sectors counting the conflicts storing the last non conflict coordinate in a variable. If the (duplicate)conflict counter is one less than the available count then I know the number is a valid addiction to the Fixed number set and should be treated as such making is value permanent. Removing the digit from the Possible and Available indexes and adding it to the Digits in a Row. If the difference is not valid meaning more than one then it will not be placed and It will then continue to check the next available digit in the available set otherwise the probability check will run again selecting a new row or column to analyze, more likely it will be the same row or column selected because there is once less possibility and therefore greater chance of determining a Fixed number.

What should be done when a row or column that is select for analyzes based on probability does not have a valid addition to make to the Fixed Number set? Suggestions?

Then that would be the completion of the first check the second which will be executed when there are no possible valid additions to be made and should make educated guesses on probability. I have ideas for this but offer your own if you wish.

Concerning the first two rules I think this system will in most cases succeed if there are enough starting fixed numbers.

The third rule would work in the same way with a third array.

I will post code when its written. I note that Mat has allegedly already succeeded in making a similar script. This is for fun so I will not be viewing or asking anyone for code but suggestions and other helpful information is greatly appreciated. Thanks

  Reveal hidden contents

 

MvGulik Universalist

MvGulik

Posted
Posted (edited)

Mmm, looked around for some Sudoku strings (as solver input cases). But they seem not that common (probably using wrong search parameters).

Anyway, did found this one: http://forum.enjoysudoku.com/patterns-game-results-t6291.html

Might be of some use. (don't forget to browse that forum, as its a Sudoku forum ... like anyone might miss that. ;) )

Edited by MvGulik

"Straight_and_Crooked_Thinking" : A "classic guide to ferreting out untruths, half-truths, and other distortions of facts in political and social discussions."
"The Secrets of Quantum Physics" : New and excellent 2 part documentary on Quantum Physics by Jim Al-Khalili. (Dec 2014)

"Believing what you know ain't so" ...

Knock Knock ...
 

jdelaney Universalist

jdelaney

Posted
Posted (edited)

I created this, it can solve the easy puzzles...i'll add additional functions within the loop to recursivly guess (when out of known answers)...the file that is created on the fly includes an easy puzzle, that will be solved

UPDATE:: added logic to attempt guesses, but only one at a time, so if the guess (all possible single attempt guesses) fails, then script fails...real fun to watch it try though :)...(will add logic for a second guess later...need to make that dynamic to allow infinite, valid guesses)

The gauntlet was thrown, beat in fewer lines if you can :)

  Reveal hidden contents

Edited by jdelaney
IEbyXPATH-Grab IE DOM objects by XPATH IEscriptRecord-Makings of an IE script recorder ExcelFromXML-Create Excel docs without excel installed GetAllWindowControls-Output all control data on a given window.
Decipher Universalist

Decipher

Posted
  • Author
Posted

  On 11/15/2012 at 4:01 AM, 'jdelaney said:

I created this, it can solve the easy puzzles...i'll add additional functions within the loop to recursivly guess (when out of known answers)...the file that is created on the fly includes an easy puzzle, that will be solved

UPDATE:: added logic to attempt guesses, but only one at a time, so if the guess (all possible single attempt guesses) fails, then script fails...real fun to watch it try though :)...(will add logic for a second guess later...need to make that dynamic to allow infinite, valid guesses)

The gauntlet was thrown, beat in fewer lines if you can :)

As if I didn't have enough competition.. lol

  Reveal hidden contents

 

jdelaney Universalist

jdelaney

Posted
Posted

All done...this should solve any solveable puzzle:

  Reveal hidden contents

IEbyXPATH-Grab IE DOM objects by XPATH IEscriptRecord-Makings of an IE script recorder ExcelFromXML-Create Excel docs without excel installed GetAllWindowControls-Output all control data on a given window.
MvGulik Universalist

MvGulik

Posted
Posted (edited)

Erm,

If MsgBox(1, 1, "Solve on close of this msgbox") <> 1 Then Exit

(edit: 

MsgBox(1, 1, "Solve this puzzle?")
)

works a bit better than,

MsgBox(1, 1, "Solve on close of this msgbox")

(especially if SciTE decides to keeps restarting the script after breaking it off. :mellow: )

---

This seems like a hard test puzzle.

0,2,3,0,9,0,8,0,0
6,0,1,0,3,8,0,0,0
5,0,0,4,0,0,0,0,0
3,0,0,0,0,0,2,0,4
0,0,6,0,0,0,3,0,0
7,0,8,0,0,0,0,0,1
0,0,0,0,0,3,0,0,8
0,0,0,7,8,0,9,0,6
0,0,2,0,5,0,1,4,0
Edited by MvGulik

"Straight_and_Crooked_Thinking" : A "classic guide to ferreting out untruths, half-truths, and other distortions of facts in political and social discussions."
"The Secrets of Quantum Physics" : New and excellent 2 part documentary on Quantum Physics by Jim Al-Khalili. (Dec 2014)

"Believing what you know ain't so" ...

Knock Knock ...
 

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share
Go to topic listing

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...