Making reasonable progress with a Sudoku solver

Got a programming project in mind? Tell everyone about it!
User avatar
daveejhitchins
Posts: 4148
Joined: Wed Jun 13, 2012 5:23 pm
Location: Newton Aycliffe, County Durham
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by daveejhitchins » Thu Feb 22, 2018 10:15 am

I noticed the latest version does not show the solved part in green anymore. Booo - Hisss . . . . . Ooooops :oops: - got carried away (I know, I should be :lol: )

I aim to try both versions on the Electron - maybe today, however, Mrs H's back from Antigua early this afternoon . . . So may not have time :?

Dave H :D
Parts: UM6502CE, GAL22V10D, GAL16V8D, AS6C62256A, TC514400AZ, WD1772, R6522, TMS27C512, AT28C256
Products: ARA II, ABR, ATI, AP6, MGC, AP5 . . .
For a price list, contact me at: Retro Hardware AT dave ej hitchins DOT plus DOT com

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:45 am

daveejhitchins wrote:I aim to try both versions on the Electron
I'm not that familiar with the Electron, but just to mention that the Master version does use some 65c02 instructions, in case that's a problem.

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 » Thu Feb 22, 2018 1:31 pm

From my (very) limited reading at lunchtime (and assuming Wikipedia isn't completely inaccurate), I think the Model B version should work on an Electron, subject to PAGE=$1900 being suitable. Alternatively if someone can advise a suitable value for PAGE, I can easily build a separate Electron version for testing.

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

User avatar
daveejhitchins
Posts: 4148
Joined: Wed Jun 13, 2012 5:23 pm
Location: Newton Aycliffe, County Durham
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by daveejhitchins » Thu Feb 22, 2018 3:10 pm

Mrs H jet lagged and asleep :D

Testing results - System: Electron with Acorn Plus 3 and GOSDC with E00 DFS - Page at 1D00.

Master version doesn't work, as expected!

Beeb version works just fine :D =D> another game for the MGC if that would be OK ? [-o<

Dave H :D
Parts: UM6502CE, GAL22V10D, GAL16V8D, AS6C62256A, TC514400AZ, WD1772, R6522, TMS27C512, AT28C256
Products: ARA II, ABR, ATI, AP6, MGC, AP5 . . .
For a price list, contact me at: Retro Hardware AT dave ej hitchins DOT plus DOT com

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 3:30 pm

PAGE/run address is $1900 in the Model B version, would a build with it set to $1D00 be better?

I'm sorry, I'm new here, I don't know what an "MGC" is?

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

User avatar
daveejhitchins
Posts: 4148
Joined: Wed Jun 13, 2012 5:23 pm
Location: Newton Aycliffe, County Durham
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by daveejhitchins » Thu Feb 22, 2018 3:38 pm

PAGE/run address is $1900 in the Model B version, would a build with it set to $1D00 be better?
I'm not sure it matters? Perhaps others may have an opinion. My view is: you're not using ADFS so would it matter?

I'm sorry, I'm new here, I don't know what an "MGC" is?
Mega Games Cartridge original here and MK II here.

Dave H :D
Parts: UM6502CE, GAL22V10D, GAL16V8D, AS6C62256A, TC514400AZ, WD1772, R6522, TMS27C512, AT28C256
Products: ARA II, ABR, ATI, AP6, MGC, AP5 . . .
For a price list, contact me at: Retro Hardware AT dave ej hitchins DOT plus DOT com

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 » Sat Mar 03, 2018 12:24 pm

daveejhitchins wrote:Another game for the MGC if that would be OK ? [-o<
Firstly, my apologies for taking so long to reply, I wasn't anticipating this question and wanted to think about it. Then work and snow took over.

Yes, I'm happy for this program to be distributed via the MGC and elsewhere, but please, not until it is finished.

Once I'm happy that the program is finished, I'll host it on my own website and make some sort of announcement here.

What I have posted here is very much a beta test version at best and as we have seen, bugs have been found. I haven't really made that clear with the versions I've been posting here, but I'll put something on the screen to make that clear in future postings here. The revised solver algorithm has not had sufficient testing in my opinion and I need to write something which can run a significant number of test cases through the solver in one batch and log the results. The other thing I'm working on is back porting the solver improvements to the A8 version and making as much of the code as possible/practical common between the two platforms. This will require changes to the way the UI & IO have been written for the BBC and A8 to bring them in to line, at least in terms of how they are called & used. Internally of course, they will be very different.

I'm off work for a week, so I should be able to make some progress.

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

User avatar
daveejhitchins
Posts: 4148
Joined: Wed Jun 13, 2012 5:23 pm
Location: Newton Aycliffe, County Durham
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by daveejhitchins » Sat Mar 03, 2018 4:18 pm

EdwardianDuck wrote:Yes, I'm happy for this program to be distributed via the MGC and elsewhere, but please, not until it is finished.
Excellent . . . Thanks - more that I could have hoped for :D

Dave H :D
Parts: UM6502CE, GAL22V10D, GAL16V8D, AS6C62256A, TC514400AZ, WD1772, R6522, TMS27C512, AT28C256
Products: ARA II, ABR, ATI, AP6, MGC, AP5 . . .
For a price list, contact me at: Retro Hardware AT dave ej hitchins DOT plus DOT com

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 » Sat Mar 03, 2018 4:52 pm

A slight spanner in the works, I added a few lines of code and my assembler of choice (MADS) went from 9 passes to 20 passes with an unhelpful warning about an infinite loop and wrote garbage to the object file.

Unhelpful in the sense that it claims the infinite loop is in some data!

Grrr.

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 » Sat Mar 03, 2018 5:12 pm

Glancing at the MADS source code, it seems that if it hits 20 passes, the author infers that there must be an infinite loop somewhere.

Turning off optimisation of built in macros (MVA, MWA etc, opt r-) resolves the problem at the expense of code size.

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 » Sun Mar 04, 2018 9:24 pm

Apropos nothing in particular, timings for the BBC and A8 versions, which now use the same solving algorithm are as follows:

Solving T.HARDEST

A8 ~26.34s or ~18.46s in "fast" mode (1.73Mhz)
BBC ~20.36s or ~13.91s in "fast" mode (2Mhz)

Compared with ~69s / ~51s on the A8 using the v0.6 solver, so about 2.6x faster.

Solving T.17CELLS

A8 ~0.68s compared to ~2.4s before, so about 3.5x faster.

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

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 » Sun Mar 04, 2018 9:52 pm

wow that's some serious improvements =D> =D> =D>

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 Mar 05, 2018 8:46 am

Some more timings, all from the A8 solving T.HARDEST. I was curious about just how slow the first version was, memory having faded.

v0.1 ~9m3s. I wrote this in CC65 because this was my first non-trivial foray into 8 bit programming since the mid 1980s and I thought it would be easier than going straight to 6502. It wasn't. Frankly it was a struggle to make it work at all. Watching it solve the puzzle so slowly this morning was painful/tedious/disappointing.
v0.2 ~108.7s
v0.3 ~107.5s
v0.4 & v0.5 ~69.3s (an additional cell elimination routine was introduced in v0.4)

So currently at ~4.1x faster than the first 6502 version and ~20.6x faster than the CC65 version.

All timings in "not fast" mode (option R) because earlier versions didn't have the "fast" mode.

That's probably enough timings for now. :D

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

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

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Mon Mar 05, 2018 1:48 pm

I was just thinking... there are two extreme cases of solver design. One is purely a recursive backtracking thing (may be rather slow), and the other is purely using inference rules and has no backtracking (may fail to solve.)

As this program is a bit of both, would it be interesting for the program to indicate whether it's currently filling in using rules, or is currently doing some backtracking searches? (Or maybe it already does? Or the alternation is so fine-grained that it wouldn't be informative?)

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 Mar 05, 2018 2:13 pm

The original CC65 prototype did this, briefly flashing up the word "Recursing" when doing so. Because the program was so glacially slow, one could just about read it.

The way the program works is that when recursing, it makes one guess, then returns to rule based solving until it either can't insert anything, in which case it increases depth and makes one more guess. Alternatively if it hits an inconsistent state, it backtracks up one level.

So, as you suggest, the alternation is fine grained and I don't think showing the state would be useful. Even in edge cases like solving a blank grid, while it appears to be recursing all the time, it is actually alternating between the two states rapidly.

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

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

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Mon Mar 05, 2018 2:17 pm

Ah right... is there merit in showing at the end how many cells were found by recursing vs inference? Or is that already there?

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 Mar 05, 2018 2:23 pm

"Depth" shows the number of successful guesses, I think.

I briefly tried showing "D" for rules and "R" for recursion in the top left corner. All one sees is "D" which briefly appears to flicker slightly.

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

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

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Mon Mar 05, 2018 2:29 pm

All good then! I just tried and failed to solve the 17clue problem myself... but I will not resort to guesswork!

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 » Fri Mar 09, 2018 8:11 pm

A brief status update.

Most of this week has been spent back porting code to the A8 and reworking the project so that the bulk of the code is common between the two platforms. That has taken rather longer than I anticipated. This has required some changes to the way the UI has been implemented and has increased the size of the program somewhat. I practical terms this means that the Model B build is now rather tight on memory, at least in extreme edge cases, such as solving a blank grid. To alleviate this a little, the Model B version is built without optimisations that trade memory for performance, such as loop unrolling.

Changes since the last builds are as follows:
  • "Q" is now available to quit the program (escape still works).
    "Undo" just removes the solution from the grid, reverting back to the inputs.
    "Fast" is now a toggle rather an a command (to be consistent with the published A8 version).
    "Analyse" is a new toggle. If selected, the results are not printed. Again this was from the A8 version and was added to allow the user to gauge how complex the puzzle was without seeing the solution.
    Additional outputs "Max Depth", "Inserted" and "Memory" have been added. Memory is the sum of the program size and workspace. Workspace follows immediately from the end of the program.
I have not added the stack display from the published A8 version, the number displayed being somewhat unrealistic. In extreme cases the stack pointer seems to get down to between $70 and $80, which should be safe enough. It was originally added as a debugging aid but it doesn't really add much now that the recursive part of the solver seems to be reliable.

Some further tidying up and testing is still required, but I'm slowly getting towards a final version.

Jeremy
Attachments
sudoku-master.ssd-20180309-1950.zip
(5.58 KiB) Downloaded 14 times
sudoku-b.ssd-20180309-1950.zip
(5.65 KiB) Downloaded 14 times
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

User avatar
SimonSideburns
Posts: 275
Joined: Mon Aug 26, 2013 8:09 pm
Location: Purbrook, Hampshire
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by SimonSideburns » Sat Mar 10, 2018 9:32 pm

I have a suggestion:

The Sudoku grid doesn't make it clear where the borders of the 3x3 grid are, thus making it harder to see the divisions.

One way to solve this is to use a solid line for the border of each 3x3 region and a dotted line within to separate each single cell.

Another way is to thicken the lines around the whole grid and at the borders of each 3x3 region, leaving the other lines a single pixel wide.

It's purely a cosmetic change, and won't impact on performance, but I feel it would improve the visuals.
I'm writing a game where you can change your character from a Wizard to a monkey to a cat.

Well, Imogen that!

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 Mar 11, 2018 12:05 pm

SimonSideburns wrote:I have a suggestion:

The Sudoku grid doesn't make it clear where the borders of the 3x3 grid are, thus making it harder to see the divisions.

One way to solve this is to use a solid line for the border of each 3x3 region and a dotted line within to separate each single cell.

Another way is to thicken the lines around the whole grid and at the borders of each 3x3 region, leaving the other lines a single pixel wide.

It's purely a cosmetic change, and won't impact on performance, but I feel it would improve the visuals.
I agree, it needs something to help align cells more clearly when editing. On a A8 I used players (sprites) as a background at the suggestion of AtariAge member PIRX which worked well. Obviously that's not an option on the BBC, but dotted lines would help.
main-screen.png
main-screen.png (3.12 KiB) Viewed 629 times
In the meantime, attached is an example running in Mode 7 as suggested earlier for consideration (I'm slowly catching up). This is a Model B build but will work on a Master 128 as well. It is a bit crufted together at this stage.
Sudoku-Mode7.png
Thoughts?

Jeremy
Attachments
sudoku-mode-7.ssd.zip
(5.57 KiB) Downloaded 12 times
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

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

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Sun Mar 11, 2018 12:08 pm

Looks good to me! And Mode 7 is especially clear and readable. (But note that the Electron doesn't have a Mode 7)

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 Mar 11, 2018 4:00 pm

Here is a picture of the Mode 1 build with the grid changed to use dots and narrower lines for the internal dividers.

I've also thickened the horizontal outer box draw characters to 2px so that they match the default verticals (and also match the A8).
Sudoku-Dots.png
This does mean I now have multiple crufted together builds which need tidying up.

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

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

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Sun Mar 11, 2018 4:11 pm

And that looks very good too! If RAM isn't much of a constraint then this might be best. How about using inverse video for the clue numbers? Ideally they'd be somehow different.

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 Mar 11, 2018 4:26 pm

RAM is, unfortunately, a constraint on a Model B and Electron.

Masters and Model B's with 2nd processors can run in Mode 1, so we can use red/green for the clue and result cells.
Masters and Model B's can run in Mode 7, so we can use the same colour approach there as well.
Electrons and Model B's without 2nd processors are stuck in Mode 4, so as you suggest, inverse video is the only option. In this case we're tight on memory, but so far this is only a problem for silly edge cases like solving a blank grid. It's not a problem for real life cases.

It's also unclear to me where PAGE should be on an Electron as I'm unclear what filing system is typically used. OK, for tape it's $0E00, which would help, but I really don't want to go down the tape route myself.

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

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

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Sun Mar 11, 2018 4:46 pm

I'm pretty sure you'd find Page can be lowered a bit if you're not doing explicit file i/o - load and save are cheap, I think, needing no buffer space. There's probably a recipe for lowering Page but I don't know it offhand.

Loading to &1900 is pretty safe, I think.

With some cleverness, if you don't need the full vertical height of the screen, I think you could arrange to use less RAM that way. Again, I don't have a recipe to hand.

User avatar
SimonSideburns
Posts: 275
Joined: Mon Aug 26, 2013 8:09 pm
Location: Purbrook, Hampshire
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by SimonSideburns » Sun Mar 11, 2018 7:38 pm

Those changes are superb.

The fact that the MODE 7 version is suitable for a standard Model B is great, and for those with extra RAM the Mode 1 version is so much clearer to see.

Great stuff.
I'm writing a game where you can change your character from a Wizard to a monkey to a cat.

Well, Imogen that!

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

Re: Making reasonable progress with a Sudoku solver

Post by tricky » Sun Mar 11, 2018 10:14 pm

There are various boards that give a version of Shadow ram on the model B and there is sideways ram, but now you have mode 7, they may not be with the effort. Nice job.

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

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Mon Mar 12, 2018 2:08 pm

Found a thread to help with PAGE:
kieranhj wrote:On the topic of memory I'm going to have a small rant. It's boggling that Acorn chose to set PAGE=&1900 by default for DFS when the vast majority of simple file load/save operations can be undertaken quite safely / happily with PAGE=&1100
If you start as a Basic program, you'll aways be loaded at PAGE and would need to relocate and restart (somehow) but if you're machine code, presumably you just set your load address to 1100... or perhaps it's not so easy. (There could be other ROMs installed which have allocated some memory.)

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

Re: Making reasonable progress with a Sudoku solver

Post by crj » Mon Mar 12, 2018 2:55 pm

EdwardianDuck wrote:In the meantime, attached is an example running in Mode 7 as suggested earlier for consideration (I'm slowly catching up). Thoughts?
Needless to say, I approve of the use of = # ‖ to delimit the grid. (-8

It bears mentioning that, for reasons that are easy to anticipate, writing to a MODE 7 screen is way faster than writing to other modes. You'll likely find that you get a worthwhile amount of CPU back by using it or, equivalently, can update more frequently.

As minor stylistic points, I'd be tempted to make the grid lines blue instead of white so the numbers stand out better against them. It also looks as though if you took "New" and "Edit" out from beside "Analyse" and "Fast", shunting them down alongside "Load"/"Save"/"Run" you would save quite a bit of screen real estate and could afford a much wider gap between the grid and the Menu/Status panels. I think that would help clarity a lot.

I'd also try setting "Menu" and "Status" into a bar of background colour (blue?) which spans the panel, for a nicer look and greater clarity.

As final icing on the cake, you've got the spare lines to make your "BBC Model B Sudoku Solver" line double-height.

Post Reply