I've posted my Sudoku solver written entirely in AutoHotkey (featuring both automatic and manual solving modes) at the following URL:
https://ahknet.autoh...imon/Sudoku.exe
The program will associate itself with .sku files (not used by any standard app as far as I can tell). Use the Help menu item (or pres [F1]) for usage instructions, and the About... dialog for contact info.
The AHK code (and related files, including Clip2Bmp and QQWingW source) are found here:
https://ahknet.autoh.../SudokuCode.zip
Here's a screenshot of the program (in manual solving mode):
Update: Version 1.7 featured:
** Grid navigation via arrow keys
** Other keyboard hotkeys (e.g. Ctrl+Digit to highlight candidates)
** Highlighting buttons change appearance when no matching candidates remain.
Update: Version 1.8 is now posted, featuring:
** New puzzle generation with selectable difficulty level (courtesy of Stephen Ostermiller's QQwing, ported to Windows).
Note: Expanded comments are still not yet added to the code (this will happen with v1.9, which will add sequential snapshooting of puzzle window to document a solution).
Jacques.
Sudoku Sensei - v1.8 Update
Started by
JBensimon
, Nov 08 2006 03:15 AM
30 replies to this topic
#1
-
Posted 08 November 2006 - 03:15 AM
I'm far too lazy to actually look at the code myself, so mind telling me which algorithm you used?
#2
-
Posted 08 November 2006 - 03:30 AM
You mean for the automatic solving? That's actually a tiny piece of the overall code (even taking into account the solution progress display). It's basically a "brute force" approach implemented as a recursive function: function takes a puzzle, plugs a candidate into the first empty cell, and calls itself with the updated puzzle. It either gets back a solved puzzle, or no solution (in which case it plugs in the next available candidate and calls itself again, etc. -- until a solution is obtained or it runs out of candidates for that cell, i.e. no solution exists).which algorithm[?]
Jacques.
#3
-
Posted 08 November 2006 - 03:42 AM
Ah, I see... I'm downloading it just to see how fast it runs. 8)
#4
-
Posted 08 November 2006 - 03:57 AM
Here are a couple of typical sample puzzles (the first pretty quick to solve, the second taking a little longer). Note that the solving time using the brute force approach is not related to the difficulty of solving the puzzle manually using logic alone.
Sudoku.exe ".....7.....9.812...7.36...58.4....9..5.....6..3....4.72...78.5...315.8.....4....."
Sudoku.exe "5..2...1...19..73.......8...5..2...8.62.39........43............8.4679....73....."
Jacques.
Sudoku.exe ".....7.....9.812...7.36...58.4....9..5.....6..3....4.72...78.5...315.8.....4....."
Sudoku.exe "5..2...1...19..73.......8...5..2...8.62.39........43............8.4679....73....."
Jacques.
#5
-
Posted 08 November 2006 - 04:21 AM
But it's probably related to the number of initial clues given. (Which, indeed, has absolutely no connection with human difficulty)
#6
-
Posted 08 November 2006 - 04:32 AM
I recall that an "optimum" algorithm had been posted on the internet. I guess it should be faster then brute force. But I can't remember where I saw it. You may search this forum for sodoku to find references if you are interested.
#7
-
Posted 08 November 2006 - 08:08 AM
Ciao
toralf
I use the latest AHK version (1.1.15+)
Please ask questions in forum on ahkscript.org. Why?
For online reference please use these Docs.
toralf
I use the latest AHK version (1.1.15+)
Please ask questions in forum on ahkscript.org. Why?
For online reference please use these Docs.
I just saw, that you have used that topic i mentioned above. Have you tested the "Least Candidate Hybrid II" solver (<!-- m -->http://sudoku.sourceforge.net/<!-- m --> )?
Would it be hard to extend the script to other matrix formats?
Would it be hard to extend the script to other matrix formats?
#8
-
Posted 08 November 2006 - 08:19 AM
Ciao
toralf
I use the latest AHK version (1.1.15+)
Please ask questions in forum on ahkscript.org. Why?
For online reference please use these Docs.
toralf
I use the latest AHK version (1.1.15+)
Please ask questions in forum on ahkscript.org. Why?
For online reference please use these Docs.
Didn't tried it, but the screenshot, thus the GUI is impressive. Complex yet clean.
Note there are Sudoku solvers in Java (eg. the link given by toralf) and other languages, even in JavaScript!
Note there are Sudoku solvers in Java (eg. the link given by toralf) and other languages, even in JavaScript!
#9
-
Posted 08 November 2006 - 09:39 AM
vPhiLho := RegExReplace("Philippe Lhoste", "^(\w{3})\w*\s+\b(\w{3})\w*$", "$1$2")
Regarding other algorithms, I wasn't really looking for speed because of my desire to provide an animated "show" of the solution in progress -- more fun than the solution simply appearing immediately in the grid. The brute force algorithm, if implemented without any progress display, is itself fast enough to provide an instantaneous solution (I originally created the solution algorithm as literally a 2-line APL program). The only reason to change it would be to turn the program into a "tutorial" for humans, going from easy to harder logical steps for candidate elimination -- which I'm not planning to do. If anything, I'd put further effort into attempting to generate new puzzles, which is a completely different challenge.
As far as other matrix formats, adapting the program would be feasible but a little tough because of the complexity of the GUI (e.g. sizing and lining up the groupbox, image and text controls that make up the manual solution pad). Would have been a lot easier if it were possible to set and change the background color of text controls (for the candidate highlighting feature).
I'm still amazed at what can be achieved with what was supposed to be a "scripting language". Chris can be very proud of his achievement.
Jacques.
As far as other matrix formats, adapting the program would be feasible but a little tough because of the complexity of the GUI (e.g. sizing and lining up the groupbox, image and text controls that make up the manual solution pad). Would have been a lot easier if it were possible to set and change the background color of text controls (for the candidate highlighting feature).
I'm still amazed at what can be achieved with what was supposed to be a "scripting language". Chris can be very proud of his achievement.
Jacques.
#10
-
Posted 08 November 2006 - 02:12 PM
Regarding the existence of Sudoku programs in other languages, they were the reason I decided (on a challenge from colleagues who've heard me sing the praises of AutoHotkey) that the honor of AutoHotkey had to be defended and an AHK version created. :-)
#11
-
Posted 08 November 2006 - 02:20 PM
I just tested the script. It is very nice.
I found one problem though. When the gui is empty and i select highlight for 1 all ones have a yellow background, except the 1 in the field marked with a 1
Edit: Never mind, I just played with your code and suddenly couldn't reproduce it anymore. :| But I calculated how many gui commands you used for the gui and it is roughly 1165 commands. :) Very impressive.
I found one problem though. When the gui is empty and i select highlight for 1 all ones have a yellow background, except the 1 in the field marked with a 1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 1| | | | | | | | | | | |It has some funny icon as background. This also applies to the rest of the numbers in that same field.
Edit: Never mind, I just played with your code and suddenly couldn't reproduce it anymore. :| But I calculated how many gui commands you used for the gui and it is roughly 1165 commands. :) Very impressive.
#12
-
Posted 08 November 2006 - 02:53 PM
Ciao
toralf
I use the latest AHK version (1.1.15+)
Please ask questions in forum on ahkscript.org. Why?
For online reference please use these Docs.
toralf
I use the latest AHK version (1.1.15+)
Please ask questions in forum on ahkscript.org. Why?
For online reference please use these Docs.
When the gui is empty and i select highlight for 1 all ones have a yellow background, except the 1 in the field marked with a 1
I just posted a screenshot of the steps you describe at https://ahknet.autoh...Screenshot2.png and it looks OK.
I think I've seen the sort of screen corruption you describe once in a different AHK GUI, but it disappeared when I closed and reopened the program -- would you mind sending me a screenshot (you can use the e-mail link in the About... dialog)?
Jacques.
#13
-
Posted 08 November 2006 - 03:13 PM
On the subject of screenshots, you may notice in the Help that the Print function currently requires a .NET Framework. This is because it uses a little utility (Clip2Bmp) created by a colleague to convert a bitmap on the clipboard to a .png file (which I then print using Windows' own shimgvw.dll). Does anybody know of a "native" way to save a clipboard bitmap to a valid image file (bmp, png, ...)?
Jacques.
Jacques.
#14
-
Posted 08 November 2006 - 03:23 PM
Just a small idea: couldn't the number keys 1-9 used as shortcuts to toggle the highlight candidates?
#15
-
Posted 08 November 2006 - 03:23 PM
Ciao
toralf
I use the latest AHK version (1.1.15+)
Please ask questions in forum on ahkscript.org. Why?
For online reference please use these Docs.
toralf
I use the latest AHK version (1.1.15+)
Please ask questions in forum on ahkscript.org. Why?
For online reference please use these Docs.