Making reasonable progress with a Sudoku solver

Got a programming project in mind? Tell everyone about it!
User avatar
EdwardianDuck
Posts: 47
Joined: Thu Aug 10, 2017 8:07 pm
Location: Northamptonshire
Contact:

Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Sun Feb 18, 2018 4:03 pm

In order to learn a little about BBC programming, I thought I'd port my Sudoku solver program from the Atari 8bit series to the Model B/Master 128. That will be a quick getting started exercise, or so I thought before going down the rabbit holes of experimenting with different assemblers and reworking the solver part to be more efficient. Now, several months later, it is just about robust enough to show.

The original Atari version is here.

Attached are two (zipped) SSD files, one for the Model B and one for the Master 128. The main difference is that the Model B version needs to run in MODE 4 (unless running on a 2nd processor, in which case you can use MODE 1). The Master 128 version can run in either MODE 129 or MODE 132. The Model B version uses only legal/documented NMOS 6502 instructions, the Master 128 version uses some CMOS 65c02 instructions as well.

The pictures below show what the Daily Telegraph claimed to be the world's hardest Sudoku which can be solved in ~21 seconds, if you want to watch it trying. The picture shows ~20 seconds (BeebEm) compared to ~21 seconds on a real Master 128, so perhaps there is a timing issue here. Solving this one in "Fast" mode (in which there is no progress shown until the end) gives more consistent timing. This isn't an area I've really looked into yet.
pic1.png
pic1.png (1.8 KiB) Viewed 1492 times
pic2.png
pic2.png (2.58 KiB) Viewed 1492 times
Typical newspaper puzzles should be solved in ~1 second.

Both versions should run on their respective 2nd (6502/65c02) processors. Running the example above on a PI Zero reduces the run time to ~0.2 seconds.

There are two test cases on the disk images, T.HARDEST and T.17CELLS, which can be loaded using the "L" option. To enter a puzzle, use the "N" option, digits 1-9 to enter known values, arrow keys to navigate around, delete to erase (backwards) and space to overwrite (forwards). Press escape to exit edit mode. Escape will also exit the program. For more information, please refer to the link above.

Known issues.

1) The time display is missing a zero when <0.1 seconds.
2) If the puzzle cannot be solved (initial state is inconsistent), the last solution is displayed.

But as these are just cosmetic I didn't want to hold back from an initial release.

Note that the program has not been tested on a real Model B.

Jeremy
Attachments
sudoku-master.ssd-20180218.zip
(4.98 KiB) Downloaded 19 times
sudoku-b.ssd-20180218.zip
(5.16 KiB) Downloaded 13 times
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

User avatar
flaxcottage
Posts: 3066
Joined: Thu Dec 13, 2012 8:46 pm
Location: Derbyshire
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by flaxcottage » Sun Feb 18, 2018 6:02 pm

This is a great piece of software. =D> =D>

Now I can beat my wife at solving Sudoku puzzles though she does regard it as cheating. :lol:
- John

Why do I keep collecting Acorn gear? I'm going to need a considerably bigger man-cave. :?

User avatar
tricky
Posts: 2441
Joined: Tue Jun 21, 2011 8:25 am
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by tricky » Sun Feb 18, 2018 6:24 pm

Very nice, and twice as fast as my C++ one running on a laptop! :oops:

User avatar
EdwardianDuck
Posts: 47
Joined: Thu Aug 10, 2017 8:07 pm
Location: Northamptonshire
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Sun Feb 18, 2018 8:19 pm

The attached updated SSD images fix the two cosmetic problems I mentioned in the original post.

Jeremy
Attachments
sudoku-b.ssd-20180218-2015.zip
(5.18 KiB) Downloaded 12 times
sudoku-master.ssd-20180218-2015.zip
(5 KiB) Downloaded 13 times
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

User avatar
jms2
Posts: 1965
Joined: Mon Jan 08, 2007 6:38 am
Location: Derby, UK
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by jms2 » Sun Feb 18, 2018 9:07 pm

Very nice, and I'm reassured to see that a Beeb can do it a lot faster than an Atari (I'm guessing this is a 2MHz vs 1MHz effect). Does the extra memory on a Master help? And also, do you plan to implement the memory use and other stats from the Atari version?

User avatar
EdwardianDuck
Posts: 47
Joined: Thu Aug 10, 2017 8:07 pm
Location: Northamptonshire
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Mon Feb 19, 2018 8:48 am

Well the Atari is ~1.73Mhz not 1Mhz but ANTIC DMA steals ~30% of the cycles. So given that v0.6 on the Atari takes ~69 seconds with the display active, if all things are equal, the BBC should take 69*1.73*(1-0.3)/2.0 or ~41.8 seconds. I don't have the exact figure to hand, but ~41.8 seconds sounds about right for the time when I did the initial quick port of the v0.6 algorithm to the BBC. It was certainly over 40 seconds. This calculation will be distorted by the fact that one can write to a GRAPHICS 0 (text) screen on the Atari much faster than using the BBC MOS.

The rest of the performance improvements are mostly down to improved implementations of the algorithms in the solver routine, plus a little from general improvements to loop efficiency, loop unrolling and so on.

v0.7 is somewhat faster for puzzles which can be solved without recursion. The 17Cells example takes ~2.4 seconds on the Atari running v0.6 compared with ~0.4 seconds on the BBC (which would be ~1.4 seconds in v0.6 using the calculation above).

The shadow RAM on the Master allows the program to run in MODE 129 (1) rather than MODE 4 on the Model B. While this allows for some colour, it actually slows the program down as it takes more effort for the MOS to write the screen in MODE 129.

I guess I could implement the other three statistics, they were slightly useful during development, although "Inserted" is a rather meaningless number now given the changes in the solver.

The next step is to port the improvements back to the Atari version and to some extent build both versions off the same code base. That should keep me amused for a while.

Jeremy
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

User avatar
BigEd
Posts: 1819
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Mon Feb 19, 2018 10:39 am

This looks very nice to me! Could a clever person please cook up a link to jsbeeb which directly loads and boots the SSD?

User avatar
lurkio
Posts: 1561
Joined: Tue Apr 09, 2013 11:30 pm
Location: Doomawangara
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by lurkio » Mon Feb 19, 2018 11:50 am

BigEd wrote:Could a clever person please cook up a link to jsbeeb which directly loads and boots the SSD?
It'll have to be me instead:
:idea:

User avatar
BigEd
Posts: 1819
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Mon Feb 19, 2018 12:07 pm

many thanks!

("L" to load T.HARDEST or T.17CELLS)

User avatar
tricky
Posts: 2441
Joined: Tue Jun 21, 2011 8:25 am
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by tricky » Mon Feb 19, 2018 12:19 pm

Jeremy, have you considered MODE 7 (teletext, one byte per character), you could have lines or colour or a much larger grid for both.

User avatar
EdwardianDuck
Posts: 47
Joined: Thu Aug 10, 2017 8:07 pm
Location: Northamptonshire
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Mon Feb 19, 2018 12:30 pm

I did briefly ponder MODE 7, but I couldn't see that I could get some sort of line draw characters (block graphics) and numbers at the same time. Having said that I am a complete BBC neophyte (this is my first BBC program) so I could easily be mistaken.

If anyone wants to mock up a MODE 7 screen for me and show me how it's done, please feel free.

Jeremy
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST


User avatar
EdwardianDuck
Posts: 47
Joined: Thu Aug 10, 2017 8:07 pm
Location: Northamptonshire
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Mon Feb 19, 2018 2:10 pm

Thank you, I can see where you're coming from now. Leverage the fact that I'd have to use a space for the colour change to space out the grid. I was over-thinking the problem of how to represent the grid, where the simplest answer is not to bother.

Jeremy
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

User avatar
BigEd
Posts: 1819
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Mon Feb 19, 2018 3:52 pm

There are a few difficult sudoko challenges here, and this one took 108.65s on jsbeeb:

Code: Select all

 . . . | . . . | . . 8
 . . 3 | . . . | 4 . .
 . 9 . | . 2 . | . 6 .
-------+-------+-------
 . . . | . 7 9 | . . .
 . . . | . 6 1 | 2 . .
 . 6 . | 5 . 2 | . 7 . 
-------+-------+-------
 . . 8 | . . . | 5 . .
 . 1 . | . . . | . 2 .
 4 . 5 | . . . | . . 3 
whereas this one took 71.26s:

Code: Select all

 . . . | . . . | . 3 9  
 . . . | . . 1 | . . 5  
 . . 3 | . 5 . | 8 . .  
-------+-------+-------
 . . 8 | . 9 . | . . 6  
 . 7 . | . . 2 | . . .  
 1 . . | 4 . . | . . .  
-------+-------+-------
 . . 9 | . 8 . | . 5 .  
 . 2 . | . . . | 6 . .  
 4 . . | 7 . . | . . .  
(But neither are symmetrical layouts)

User avatar
EdwardianDuck
Posts: 47
Joined: Thu Aug 10, 2017 8:07 pm
Location: Northamptonshire
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Mon Feb 19, 2018 4:31 pm

Interesting, both are a lot harder than "the World's Hardest Sudoku", at least for some value of "hard". I did notice that the first one at least causes the pass counter to wrap round, I'll have to change the switch in the source to turn that back into a word and rebuild.

Nice to have some really tough test cases though.

Jeremy
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

User avatar
BigEd
Posts: 1819
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Mon Feb 19, 2018 4:40 pm

It's an interesting area! My own approach to tackling a sudoku problem sometimes leaves me stuck, even when there is a solution - so "hard" is certainly relative to tactics employed.

Edit: oops, meant to link here.

User avatar
BigEd
Posts: 1819
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Mon Feb 19, 2018 4:58 pm

Here's something interesting - the solver gives up on this one:

Code: Select all

 . . . | . . . | . . 9
 . . . | . . 1 | . 3 5
 . . 3 | . 9 . | . 6 .
-------+-------+-------
 . . 5 | . 3 . | . . 6
 . 7 . | . . 2 | . . .
 1 . . | 4 . . | . . .
-------+-------+-------
 . . 9 | . 8 . | . 5 .
 . 2 . | 7 . . | . . .
 4 . . | . . . | 8 . . 
(It can solve it if you fill in the middle digit, as a six)

User avatar
EdwardianDuck
Posts: 47
Joined: Thu Aug 10, 2017 8:07 pm
Location: Northamptonshire
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Mon Feb 19, 2018 7:17 pm

True, and I can replicate the problem in BeebEm 3. However given that this comes from a thread where it appears they are discussing puzzles designed to break Sudoku solvers on fast modern hardware, I'm not too worried about that. :D

Still, as you say, interesting.

Jeremy
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

User avatar
EdwardianDuck
Posts: 47
Joined: Thu Aug 10, 2017 8:07 pm
Location: Northamptonshire
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Mon Feb 19, 2018 7:35 pm

Attached are updated versions with PASS set to be a word so that the count doesn't wrap for the hard puzzles above (but no other improvements).

Jeremy
Attachments
sudoku-master.ssd-20180219.zip
(5.03 KiB) Downloaded 11 times
sudoku-b.ssd-20180219.zip
(5.2 KiB) Downloaded 15 times
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

User avatar
IanS
Posts: 588
Joined: Mon Aug 31, 2009 6:02 pm
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by IanS » Mon Feb 19, 2018 10:06 pm

EdwardianDuck wrote:Attached are updated versions with PASS set to be a word so that the count doesn't wrap for the hard puzzles above (but no other improvements).

Jeremy
Would that affect its ability to solve a puzzle, or just a display issue?
If I fill in 1-9 in the top left 9 squares, it solves quite quickly.
Put in 123, 789, 456 in the same squares, runs for hours (still hasn't finished)
sodoku.PNG

User avatar
EdwardianDuck
Posts: 47
Joined: Thu Aug 10, 2017 8:07 pm
Location: Northamptonshire
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Tue Feb 20, 2018 8:49 am

IanS wrote:Would that affect its ability to solve a puzzle, or just a display issue?
Pass is just scenery (or at least I'm 99% sure it is, you've got me thinking now), it's just a counter that gets incremented and displayed.
IanS wrote:If I fill in 1-9 in the top left 9 squares, it solves quite quickly.Put in 123, 789, 456 in the same squares, runs for hours (still hasn't finished)
I can see that the recursive part of the solver is looping. I think I can see that it isn't trying 9 as an option when it should and this appears to be causing the looping. This

Code: Select all

123
456
789
works because it arrives at a solution without needing to use 9 as a trial value (or so I infer). Also solving a blank grid works.

Now the good news, it works fine on v0.6 on an (emulated, Altirra) A8, so basically I've introduced a bug while improving the solver performance. That's something I can fix, although probably not before the weekend.
BigEd wrote:Here's something interesting - the solver gives up on this one:

Code: Select all

  . . . | . . . | . . 9
  . . . | . . 1 | . 3 5
  . . 3 | . 9 . | . 6 .
 -------+-------+-------
  . . 5 | . 3 . | . . 6 
  . 7 . | . . 2 | . . . 
  1 . . | 4 . . | . . .
 -------+-------+------- 
  . . 9 | . 8 . | . 5 . 
  . 2 . | 7 . . | . . . 
  4 . . | . . . | 8 . . 
I think this is suffering from the same bug as above, v0.6 handles it without issue, albeit slowly.

Jeremy
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

User avatar
BigEd
Posts: 1819
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Tue Feb 20, 2018 9:39 am

Ah, this makes more sense now!

User avatar
EdwardianDuck
Posts: 47
Joined: Thu Aug 10, 2017 8:07 pm
Location: Northamptonshire
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Tue Feb 20, 2018 9:51 pm

Some slight progress...

Eliminating one of the deterministic algorithms from the solver allows both problem cases to complete successfully, if somewhat more slowly (+70% for T.HARDEST for comparison). This is one of the routines which was rewritten for v0.7, although I haven't been able to determine what the problem is this evening.

Jeremy
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

crj
Posts: 834
Joined: Thu May 02, 2013 4:58 pm
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by crj » Wed Feb 21, 2018 6:30 pm

If you want to run in teletext mode, an alternative to using extra spacing to delimit the 3x3 sub-squares is to use the | # = characters. In MODE 7, those come out looking like this:
Image

User avatar
tricky
Posts: 2441
Joined: Tue Jun 21, 2011 8:25 am
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by tricky » Wed Feb 21, 2018 7:42 pm

Those spaces are colour codes to keep the colour coding of the numbers feature ;)

User avatar
EdwardianDuck
Posts: 47
Joined: Thu Aug 10, 2017 8:07 pm
Location: Northamptonshire
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Wed Feb 21, 2018 9:33 pm

crj wrote:If you want to run in teletext mode, an alternative to using extra spacing to delimit the 3x3 sub-squares is to use the | # = characters. In MODE 7, those come out looking like this:
Image
That's a great tip, thank you. One reason for having the grid is that I find it helpful when typing in test cases.

Jeremy
Last edited by EdwardianDuck on Wed Feb 21, 2018 9:41 pm, edited 1 time in total.
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

User avatar
EdwardianDuck
Posts: 47
Joined: Thu Aug 10, 2017 8:07 pm
Location: Northamptonshire
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Wed Feb 21, 2018 9:41 pm

After a couple of evening's staring at the offending algorithm, I've finally managed to spot the error, one CLC missing! I did feel a bit of a twit when I found that. #-o

Attached are updated disk images which fix the two problem cases mentioned earlier. (The non-trivial example is T.BIGED on the image to save typing).

What is slightly interesting is that T.HARDEST now takes an additional two passes to solve. This is due to the earlier error causing the solver to accidentally find the correct value for one cell earlier in the process. Now that it works properly, it takes a little longer. :(

I'm relieved that's fixed, I'll have time to experiment with MODE 7 at the weekend.

Jeremy
Attachments
sudoku-master-20180221.ssd.zip
(5.08 KiB) Downloaded 15 times
sudoku-b-20180221.ssd.zip
(5.24 KiB) Downloaded 11 times
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

User avatar
tricky
Posts: 2441
Joined: Tue Jun 21, 2011 8:25 am
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by tricky » Thu Feb 22, 2018 6:59 am

The link that I posted to edit.tf is a website that is a Teletext editor, the page is the URL, so to save a page, just bookmark it.
There are also several editors that run on the beeb (or emulator) including one by JGH.

User avatar
vanekp
Posts: 539
Joined: Thu Nov 30, 2000 7:09 am
Location: The Netherlands
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by vanekp » Thu Feb 22, 2018 9:42 am

I noticed the latest version does not show the solved part in green anymore.

User avatar
EdwardianDuck
Posts: 47
Joined: Thu Aug 10, 2017 8:07 pm
Location: Northamptonshire
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Thu Feb 22, 2018 10:11 am

vanekp wrote:I noticed the latest version does not show the solved part in green anymore.
Is there any chance you are running the instance from sudoku-b-*.ssd rather than sudoku-master-*.ssd?

If so, that will use MODE4 and be limited to monochrome.

If not, I can't check this until I get home this evening. The latest update was prepared in a bit of a rush late yesterday evening, so it is quite likely that I've made a mistake somewhere.

Jeremy
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

Post Reply