Jump to content

Photo

Sudoku Solver


24 replies to this topic

#1 EdwardianDuck OFFLINE  

EdwardianDuck

    Space Invader

  • 30 posts
  • Location:DARC, DuckSpace (near UK)

Posted Mon May 4, 2015 2:17 PM

Here is a link to a little program I wrote recently for the Atari 8 bit line.

 

http://duckology.co....e/01/index.html

 

An ATR containing the program and a few test cases is available for download, as is the 6502 source code (MADS syntax). I've also (hopefully) managed to attach them to this post.

 

For documentation, please use the link above.

 

One word of warning / apology; I neither own nor have access to real hardware, so it has only been tested under emulation.

 

Jeremy

Attached Files



#2 EdwardianDuck OFFLINE  

EdwardianDuck

    Space Invader

  • Topic Starter
  • 30 posts
  • Location:DARC, DuckSpace (near UK)

Posted Mon May 4, 2015 2:19 PM

Also, thanks to Rob from the excellent Player/Missle podcast for featuring this as a listener written program in the latest episode (#12).

 

Jeremy



#3 EdwardianDuck OFFLINE  

EdwardianDuck

    Space Invader

  • Topic Starter
  • 30 posts
  • Location:DARC, DuckSpace (near UK)

Posted Sun Aug 30, 2015 8:20 AM

I've updated this program to version 0.4, adding an additional check to improve the chance of the program generating the same solution as a human solver. I noticed that one test case (PROBLEM.SUD) on the distribution ATR version 0.3 gave a different solution to the one I'd arrived at by hand. Version 0.3 did not allow for the case when despite not being able to place a value N within a 3x3 square precisely it was clear that N had to be placed in either a row or column of 3 cells within the 3x3 square. Given this knowledge a human solver is able to eliminate N from other cells in the grid and perhaps find a value to insert somewhere. Version 0.4 now includes this additional test and is able to proceed further before starting to make guesses.

 

As a result of this change, runtime is slightly increased in most test cases (TC*.SUD on the distribution ATR). However, the time to solve what the Telegraph describes as "the world's hardest Sudoku" (HARDEST.SUD on the distribution ATR) is reduced from 107.5 seconds to 69.2 seconds (Altirra v2.60, PAL).

 

The distribution ATR now auto-runs the program (AUTORUN.SYS is a copy of SUDOKU.XEX) and, for comparison, version 0.3 (SUDOKU03.XEX) is also present.

 

As before, this has been tested under emulation only.

 

Jeremy

Attached File  Sudoku-0.4-Distribution.atr.zip   36.79KB   101 downloadsAttached File  Sudoku-0.4-Source.zip   27.1KB   102 downloads



#4 jacobus OFFLINE  

jacobus

    Dragonstomper

  • 661 posts
  • Location:Canada

Posted Sun Aug 30, 2015 2:23 PM

Thanks for this Jeremy!

 

From the very first time I played Sudoku, I had a definite itch to write a solver - thank you for saving me the trouble!



#5 _The Doctor__ OFFLINE  

_The Doctor__

    River Patroller

  • 2,272 posts
  • Location:10-0-11-00:02

Posted Sat Sep 19, 2015 8:08 PM

You just made me happy! My son plays sudoku, this might make him happy too! Thank you so much!


Edited by _The Doctor__, Sat Sep 19, 2015 8:11 PM.


#6 vitoco OFFLINE  

vitoco

    Chopper Commander

  • 186 posts

Posted Sun Sep 20, 2015 9:23 AM

Wow! Nice program. It was interesting to see how it solves a blank grid in 64 passes :-D

 

I miss an option for directory listing. I had to quit to DOS, list the contents to search for available examples and load the solver again... In the meanwhile, I almost forgot the name!



#7 EdwardianDuck OFFLINE  

EdwardianDuck

    Space Invader

  • Topic Starter
  • 30 posts
  • Location:DARC, DuckSpace (near UK)

Posted Sun Sep 20, 2015 9:51 AM

Thank you all for your kind and encouraging comments.

 

I'm currently working on another slight revision which will add an "analysis" mode (basically solve the puzzle without showing you the solution). The idea is that you can look at the status panel to get a rough idea about how complex the puzzle is without seeing the solution (number of passes, recursion depth etc) and more importantly whether the inputs represent a valid puzzle (consistent = "Yes"). It might be useful for "manual" puzzle solvers. The other new feature will be an option to disable Antic DMA (SMDCTL= 0) during the solve just to speed things up.

 

In terms of the lack of a directory listing, that's a fair point and is something I'll add to the wish list (no promises though). Originally I wasn't going to bother with loading and saving options at all, but added them when it became clear that I'd need to put quite a lot of test cases through the solver in order to test it properly.

 

Jeremy



#8 cliffh OFFLINE  

cliffh

    Space Invader

  • 42 posts
  • Location:UK

Posted Sun Sep 20, 2015 1:10 PM

Wonderful!
 
It’s a pleasure to watch the program solving, and very instructive to see the MADS source code.  Thank you very much for sharing it.
 
The performance you have managed to get from the 8 bit Atari is amazing.
 
I got interested in Sudoku earlier this year when a friend told me about his solver and described how to encode the rules of the game in a table of indices (identical to your table “CellIntersect”).  I wrote my own solver in C using a brute force recursive search, and was surprised how well it worked.  It solves most published puzzles in a fraction of a second, but it depends on a modern machine that can search millions of values per second of course - and is not smart enough to be useful on the Atari.
 
My program always searches the entire tree of consistent values, so as the number of clues in the start position is reduced the solution time rises exponentially.  If I understand correctly, the situation is slightly different for human players (and I guess for your program too) and the main challenge is posed by the length of the sequences requiring speculative placement of values.  I tried running this extreme 17 Clue Puzzle on your program, and it made very light work of it, solving in only 2.4 seconds.  In contrast mine took 5 minutes and searched 1.9 billion moves – definitely a case of using a sledgehammer to crack a nut!
 
Cliff



#9 EdwardianDuck OFFLINE  

EdwardianDuck

    Space Invader

  • Topic Starter
  • 30 posts
  • Location:DARC, DuckSpace (near UK)

Posted Sun Sep 20, 2015 2:01 PM

Essentially my program simulates how a human would solve a puzzle, as far as possible. The basic idea is to avoid making guesses for as long as possible, then make one guess for the cell with the least number of candidate values. Then given that guess the program reverts back to avoiding guesses until no further cells can be inserted. For typical newspaper puzzles, at most 1 or 2 guesses are required for the harder puzzles. However, I've only implemented a couple of deterministic (I think that's the right word) algorithms, so v0.4 will still resort to recursion before a human solver in some cases (but less often than v0.3).

 

So running the 17 Clue Puzzle, as you point out, only takes 2.4 seconds, primarily because it doesn't need to make any guesses at all (Depth = 0). In fact this puzzle should be straightforward for a human to solve even through it looks hard. Compare and contrast HARDEST.SUD on the ATR, which was designed to be really hard to solve (apparently).

 

I must confess that I have spent a ridiculous amount of time improving the performance of this program, just for my own amusement really.

 

Jeremy



#10 pirx OFFLINE  

pirx

    Moonsweeper

  • 338 posts
  • Location:Poland

Posted Sun Sep 20, 2015 5:59 PM

Hi EdwardianDuck,

 

Just thought this nice app lacks the distinct sudoku grid view, so added some PM background to show the 3x3 boxes.

 

This is very quick and dirty stuff, kind of proof of concept only. I would not even try to replicate your elegant source code style  :).

 

If you'd like to use this concept, please remember about cleaning PM at exit. A better memory location for PMG would not hurt, too (e.g. below the screen).

 

Best,

 

pirx

Attached Files


Edited by pirx, Sun Sep 20, 2015 6:02 PM.


#11 EdwardianDuck OFFLINE  

EdwardianDuck

    Space Invader

  • Topic Starter
  • 30 posts
  • Location:DARC, DuckSpace (near UK)

Posted Mon Sep 21, 2015 1:36 AM

Hello pirx,

 

Thank you for producing this patch/example/proof of concept, that's really helpful. Such a neat idea to use PM graphics as a static background colour. I'm at the early stages of playing with PM graphics for another (potential) program and I don't think I'd have come up with this idea myself. What you have done solves the problem I was having with making the 3x3 squares more distinctive to help with alignment when entering the puzzle. I had originally done this by redefining the character set to make some of the lines thinner, but discarded it as it just looked ugly.

 

I look forward to reading your code this evening and cross referencing with De Re Atari & Mapping the Atari to understand it.

 

Sample image below.

 

Jeremy

Attached Thumbnails

  • Sudoku-PM.png

Edited by EdwardianDuck, Mon Sep 21, 2015 1:37 AM.


#12 idavis OFFLINE  

idavis

    Chopper Commander

  • 146 posts
  • Location:Keeping North of Austin Weird.

Posted Wed Sep 23, 2015 9:58 AM

Hey EdwardianDuck,

So I am really interested in this as I have my own Sudoku program for the 800. Where I ran into a problem was after my valid grid is generated and I go in to start blanking out the squares. Leeping it a valid sudoku puzzle is my problem (ensuring there is only one single solution). The only way I can see this happening is to do basically what you are doing, and solve the puzzle along the way as each new spot is blanked out. Do you mind if I take a look at your code? My atr and source is posted here on the board, but I am sure is buried under a couple years worth of dust. Maybe with both of our sets of code, we could get a complete working Sudoku game going.



#13 EdwardianDuck OFFLINE  

EdwardianDuck

    Space Invader

  • Topic Starter
  • 30 posts
  • Location:DARC, DuckSpace (near UK)

Posted Wed Sep 23, 2015 1:55 PM

Hello Issac,

 

Your post made me realise that I had said nothing about who can do what with my Sudoku program. Basically I wrote this purely for my own amusement and to share with the community. So, basically anyone can use the program or its source code for any purpose whatsoever. If you or anyone else wants to recycle any of the code, please feel free to do so. The only slight caveat to this is that I made use of the following code which may impose some restrictions.

 

1) The cursor handling code was taken from the cc65 runtime library.

2) The RLE unpack routine came from CodeBase64.

 

Both were tweaked very slightly.

 

But if you're only interested in the solving algorithms, neither of these are required.

 

In theory you could repurpose the solver to check that your generated puzzles (I looked up your original thread and read your paper) are solvable once cells are blanked out. However, there are some traps along the way...

 

I've been using the term "deterministic solution" to mean a solution that can be found by logic only, no guessing and recursion.

 

1) The aim of my program is to find a valid solution to the entered puzzle, not necessarily the only valid solution. It will halt as soon as it finds the first valid solution. In this respect only a deterministic solution is sure to be unique (depth = 0 in the status panel).

2) The solver is less sophisticated than a competent human solver. From time to time it will come up with a different solution. This arises when the solver gets stuck BEFORE the human solver and starts recursing. Where there are mulitple solutions from that point, the solver might not pick the same solution as the human. This is most noticable when a human solver can arrive at a deterministic solution but the solver cannot. This behaviour is less noticable in v0.4 where I added an extra algorithm, but I have seen one case in the last couple of weeks where I was able to solve it deterministically but the solver required one guess. However in this case (which I should really have made a note of) we arrived at the same solution. This extra algorithm is still only looking one step ahead, whereas a human may manage more steps.

3) Mitigating this by only accepting deterministic solutions in your program does mean that more complex puzzles will be rejected as unsolveable. You can implement this by removing the recursive section from procedure SolvePuzzle in Core.asm, which is the code from label guess: onwards.

4) I'm trading memory for speed. The program makes heavy use of lookup tables (over 2K just for the solver), which might be an issue if you are still targeting a cartridge solution.

5) The recursive solver can use a lot of memory and it does not check if it is running out. If you compare the memory used by test cases TC1.SUD and HARDEST.SUD (or get it to solve a blank grid) you'll get an idea of memory used by recursion.

 

You could perhaps make use of the status values to rank puzzles in order of complexity. Some combination of pass count and the number of cells inserted in each pass (fewer = harder) might be a useful metric.

 

Hopefully this is clear and of some help.

 

Jeremy


Edited by EdwardianDuck, Wed Sep 23, 2015 1:59 PM.


#14 idavis OFFLINE  

idavis

    Chopper Commander

  • 146 posts
  • Location:Keeping North of Austin Weird.

Posted Wed Sep 23, 2015 2:53 PM

Jeremy,

Awesome, and thanks. I was originally setting that as my goal (8k cart), and over the years have pretty much resigned myself that it isn't going to happen unless I take a sort of a canned approach and bundle in some pre-made puzzles and then shuffle them, but I haven't investigated whether or not the shuffling would affect a ready made set. I know it's easy enough to shuffle a complete grid before you have removed the tiles for play, but once they are removed I am not sure if that process would introduce extra solutions. I have also studied ways to solve the puzzle and haven't been able to devote enough time to working it out so imagine my surprise when I saw your post. :) I am wondering how feasible it will be at this point still though as sometimes the wait for a legitimate grid to be produced on the 8bit can be a real bummer, and if you see my program work, it can run into a situation where it just tries and tries and cannot randomly get a combination that's valid and has to start back over. Without firing everything up, I was just curious how long it takes your code to come up with a solution? My reason for asking is like I mentioned, I was maybe working on a way to just start blanking out squares and then testing to see if there was more than one solution. If there is, put it back and try another. My fear is that this could potentially take longer than my initial grid generation, which would really put people off. It would almost just be as a novelty at that point since the time before you could play might be a real problem. Hopefully I can take a look at this soon. I am not sure if I released my source code at the time as my intention was to turn this into a cartridge (kind of one of those dreams some of us have). At this point I am not against having some help and sharing any credit where credit is due. I will get everything back out and dusted off and see what we have.

Thanks,

Isaac


Edited by idavis, Wed Sep 23, 2015 2:55 PM.


#15 EdwardianDuck OFFLINE  

EdwardianDuck

    Space Invader

  • Topic Starter
  • 30 posts
  • Location:DARC, DuckSpace (near UK)

Posted Wed Sep 23, 2015 3:20 PM

Issac,

Solution times range from 0.4s to 69.2s between the simplest cases and what the Daily Telegraph claims is the world's hardest Sudoku.

I'll hopefully be able to look at what you've produced this weekend.

Jeremy

#16 idavis OFFLINE  

idavis

    Chopper Commander

  • 146 posts
  • Location:Keeping North of Austin Weird.

Posted Wed Sep 23, 2015 3:32 PM

Jeremy,

I just loaded up your code and put in a few puzzles from a magazine I had laying here, and bingo, one solved in 7 passes and the other in 11. Pretty awesome. One more comment on mine, you mentioned seeing if mine would be solvable. Since I generate a valid grid from the start they should always have a solution. Where I ran into my mistake was not knowing that to be a true sudoku puzzle there could only be the one solution. I was so worked up about getting the Atari to come up with a valid grid in as small a space as I could that I completely missed out on one of the major rules of the game. Dumb move on my part, and unfortunately is a show stopper at this point. You will see that I tried to add a little gaming aspect to it where points would be awarded and a countdown timer was put in. The quicker you finish the more bonus points you get. Nothing happens if the timer runs out other than you lose any bonus it might have awarded you. You can also take a hint and it will go through and remove any entries you have that are incorrect, but again as a game you lose some points. I also would have to look at my code and make sure, but I think it's joystick only, other than the keys to get it started. I am not sure I coded in the arrow keys. Keep in mind the majority of this was coded on my 800 with a joystick attached so I really hadn't done much emulating. I am sure all these features can be added in, but since I ran into the issue of possibly having multiple solutions I have come to a standstill as that has to be corrected before I can put in any bells or whistles. A pretty car with no engine isn't very useful. Good job on yours, it was able to solve these two puzzles I entered in, in a relatively short amount of time. So maybe there is still some hope here.


Edited by idavis, Wed Sep 23, 2015 3:36 PM.


#17 EdwardianDuck OFFLINE  

EdwardianDuck

    Space Invader

  • Topic Starter
  • 30 posts
  • Location:DARC, DuckSpace (near UK)

Posted Sun Oct 4, 2015 9:58 AM

Here is the latest version, v0.5. This includes the following features.

 

  • I added the "checkerboard" background based (very heavily) on the sample code generously provided by @pirx. I used a darker shade as this seemed to give more contrast between the text and background. Currently, the background is suspended when the "Run" and "Analyse" menu items are used. This is because (I guess) the extra DMA accesses for the players are slowing the solver down.
  • There is a new option "B" (not actually shown on the menu) to toggle the background if you prefer not to have it.
  • An "Analyse" option which runs the solver but doesn't show either the results or the workings. It does however show the statistics. The idea is that this can be used to determine how complex a puzzle is without showing you the solution. It can also be used to validate that the inputs represent a valid solvable puzzle (Consistent = Yes).
  • A "Fast" option (toggle, shown with "*" if on). This just disables DMA (so no display) when solving. There isn't a lot of point to this IMHO, but I added it just so that "the World's hardest Sudoku" can be solved in under 1 minute.
  • Added the "Trace" option to the menu. The code existed in v0.4. All this does is pause for a key press after displaying each inserted cell. I added this so I could single step through an edge case. Again, not really all that useful, especially given the way the solver works, except possibly as a hint mode. If you get stuck solving a puzzle manually, you could enter the "stuck" position, use the "Analyse" option to check if it can be solved without recursion (Depth = 0), then use the "Trace" option to see the next cell in the solution. "Trace" starts to make less sense if the solution requires recursion.

ATR, source code and sample image attached.

 

Jeremy

 

Attached File  Sudoku-0.5-Distribution.atr   90.02KB   75 downloads

Attached File  Sudoku-0.5-Source.zip   29.76KB   68 downloads

19Cells.png



#18 EdwardianDuck OFFLINE  

EdwardianDuck

    Space Invader

  • Topic Starter
  • 30 posts
  • Location:DARC, DuckSpace (near UK)

Posted Sun Oct 4, 2015 10:10 AM

Oops.

 

I just noticed that there is a slight inconsistency between the "Fast" and "Background" options. That is, if "Fast" is ON and "Background" is ON then DMA doesn't get disabled when the solver runs. Should be easy enough to fix, but possibly not today.

 

Jeremy



#19 bfollett ONLINE  

bfollett

    Dragonstomper

  • 507 posts

Posted Sun Oct 4, 2015 10:27 AM

Maybe I'm blind, but where's the "Backround" option to begin with.  I don't see it in your screen shot or when running the program.  Also you have some spare lines on the display.  Maybe put a status type bar so when you are toggling things like Fast or Edit, the status will display what is currently active.   The edit is easy enough to tell because the cursor disappears, but you can't tell if Fast is on or off.  Also if possible in some way could you gray out menu items that can't be pressed because you're in the wrong mode.  I was in Edit and tried to do a run when I was finished without realizing I had to leave edit mode first.

 

Bob


Edited by bfollett, Sun Oct 4, 2015 10:30 AM.


#20 EdwardianDuck OFFLINE  

EdwardianDuck

    Space Invader

  • Topic Starter
  • 30 posts
  • Location:DARC, DuckSpace (near UK)

Posted Sun Oct 4, 2015 10:43 AM

Bob,

 

Thank you for the feedback, all valid points. In the short term...

 

  • The background option isn't shown in the menu, but if you press the "B" key the player/missile background toggles on and off.
  • When "Fast" mode is on, there is a "*" character appended to the menu item.
  • In the original unreleased cc65 prototype, I swapped out the main menu for one which was relevant to the edit mode, but as it only had one option, I dropped it. On the other hand, the main menu is now getting crowded (which is why the "Background" option isn't visible) so a rethink of this bit is certainly overdue.

Jeremy



#21 bfollett ONLINE  

bfollett

    Dragonstomper

  • 507 posts

Posted Sun Oct 4, 2015 11:44 AM

Ah, didn't even notice the asterisk character toggling on Fast mode.  Sorry about that.  Hey if you changed "Quit Program" to just "Quit" or "Close"  you could probably move it to the second column of menu items and have room for "Background" where Quit Program used to be.

 

Bob



#22 EdwardianDuck OFFLINE  

EdwardianDuck

    Space Invader

  • Topic Starter
  • 30 posts
  • Location:DARC, DuckSpace (near UK)

Posted Sun Oct 4, 2015 12:44 PM

Here is an experimental version, v0.5x. I'm not uploading the source code this time because the changes where hurried and the code is messy. Source code will of course be made available once I'm happy with it. Also, it hasn't had much testing.

 

Changes as follows:

 

  • Fix for the Fast/Background problem (see "oops" post above).
  • Addition of a status bar as suggested. This is just to get some feedback, I'm not convinced that it is much improvement over a redesigned menu section and I may drop it later. Mind you, I'm not claiming to have any expertise in the UI/UX field. The status bar shares the same line as the I/O error message, so after an error is shown, it remains there instead if the error until a menu action is invoked.

Jeremy

 

Attached File  Sudoku-0.5-Experimental.atr   90.02KB   64 downloads

 

Experimental.png


Edited by EdwardianDuck, Sun Oct 4, 2015 12:45 PM.


#23 EdwardianDuck OFFLINE  

EdwardianDuck

    Space Invader

  • Topic Starter
  • 30 posts
  • Location:DARC, DuckSpace (near UK)

Posted Sun Oct 11, 2015 8:09 AM

Here is the latest version, v0.6. This has the following changes from v0.5 and v0.5x.

 

  • I have dropped the status bar idea, IMHO it added little real value and didn't work that well.
  • The menu has been reorganised to (hopefully) make it clearer.
  • "Fast" mode is more clearly indicated with "(On)" and "(Off)" being appended as appropriate.
  • Menu items which are not relevant are "greyed out" ("blued out"?) by removing the inverse video bit on the command character.
  • When in "Edit" mode the word "Edit" is changed to "Exit" to make this a bit clearer.
  • The fix for the "Fast/Background" problem in v0.5 and provisionally fixed in v0.5x is now formally working. There was no real change from v0.5x, but I've now had time to test it.
  • Some of the UI code has been tidied up / tweaked a bit just to make things a little easier for me going forwards (on the assumption that there will be further enhancements).

As ever, comments are always welcome.

 

Jeremy

 

Attachments

 

Distribution (bootable DOS 2.5 image)

 

Attached File  Sudoku-0.6-Distribution.atr   90.02KB   41 downloads

 

Source (ZIP)

 

Attached File  Sudoku-0.6-Source.zip   31.58KB   50 downloads

 

Initial screen

 

v0.6-Main.png

 

Edit mode showing disabled menu items

 

v0.6-Edit.png



#24 devwebcl OFFLINE  

devwebcl

    Stargunner

  • 1,074 posts
  • Location:Chile

Posted Sat Dec 3, 2016 7:25 AM

just wondering, whether your algorithm is based in any popular one ?

(as we know thare several algorithms/books about sudoku)



#25 EdwardianDuck OFFLINE  

EdwardianDuck

    Space Invader

  • Topic Starter
  • 30 posts
  • Location:DARC, DuckSpace (near UK)

Posted Sat Dec 3, 2016 9:26 AM

I suspect what I have used are known algorithms (the chance of me having invented something new is very, very small), but I didn't start from a book or other existing resource. That is to say, I worked out my simplistic strategy for solving the puzzles from first principles. Essentially the program tries to solve the puzzles as an inexperienced human solver would, looking for cells with single candidate values and values that can only be placed in one position. The program repeats these steps until it gets stuck, then it makes a guess and implements the same basic processes in a recursive manner. With the exception of the one additional check introduced in v0.4, this is all it does. I'm aware from solving puzzles manually that there are other algorithms that could be added, but so far I have only used what is (relatively) easy for me to program in 6502.

 

Hopefully this helps.

 

Jeremy






0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users