Making reasonable progress with a Sudoku solver

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

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Mon Mar 12, 2018 9:53 pm

Here is a quick mock up for Mode 7 (in Apple Numbers, I'm back at work now so I have less time to write code).
Mode 7 Mockup.png
I've split "Menu" into "Commands" and "Options" instead. I think that's less confusing. There will be at least one new command added later (shhh, spoilers). Probably.

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

User avatar
kieranhj
Posts: 757
Joined: Sat Sep 19, 2015 10:11 pm
Location: Farnham, Surrey, UK
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by kieranhj » Wed Mar 14, 2018 10:03 am

BigEd wrote: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.)
I should have qualified that my rant was entirely about machine code programs, I don't have enough knowledge of how BASIC manages file handles to know whether it's safe to lower PAGE on a regular / permanent basis! My definition of "simple load/save operations" was effectively *LOAD/*SAVE.
Bitshifters Collective | Retro Code & Demos for BBC Micro & Acorn computers | https://bitshifters.github.io/

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

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Wed Mar 14, 2018 10:44 am

[Sorry, this is all a bit off topic now... if need be, we can ask the mods to split the thread.]

It's a curiosity of the architecture, that a machine code program needs to be built to run at a particular address, and yet by the time it's loaded it's too late to discover if the necessary memory is available. Basic is a help here, as a Basic program is always loaded to PAGE, and can determine how much memory is available, and fail gracefully if there's not enough, or pass control to machine code if it's OK.

Just a thought: if ROMs allocated their memory from HIMEM downwards, dropping HIMEM, then PAGE could be constant. But this interferes with the video system, which changes HIMEM when the MODE changes... something which could be fixed at some expense in the video ULA perhaps, allowing screen memory to be allocated below ROM allocations. But then we'd need all ROM allocations to be done before the screen is allocated!

In the absence of Basic - something which surely almost never happens - all I can think of is for machine code to be built to load quite high in RAM, just under a mode 7 screen, and to include a stub which runs at that address, checking PAGE, and relocating the main part of the program down. And yet this too fails, potentially, if we're not in mode 7 or if we're on an Electron which lacks mode 7.

The simple solution is to run in a second processor! The next most simple involves shadow RAM. Or, deliver software in ROM form, where it always sits at &8000. Or, pick a number and load at that address, and hope that it's higher than the value of PAGE, even given the possible presence of ROMs which haven't even been invented at the time of choosing.

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

Re: Making reasonable progress with a Sudoku solver

Post by crj » Wed Mar 14, 2018 8:07 pm

In hindsight, having later seen what other machines did, I'm a bit surprised there wasn't a standard for relocatable executable images on the Beeb.

If you're supplanting the current language, the clean solution would be to have a load-relocate-run utility which loaded into the language workspace from &400-&7FF. Given that the relocation offset would always be an exact number of pages, the relocation routine could be pretty simple and would only ever have to operate on a single byte at a time.

I'm actually quite tempted to write that, if nobody knows of something similar that already exists?

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

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Thu Mar 15, 2018 9:46 am

André Fachat has a relocatable loader as part of his OS development(s):
http://www.6502.org/users/andre/osa/
http://www.6502.org/users/andre/o65/index.html

And IIRC one of the later BASIC ROMs has a relocator built in so it can function as a BASIC or a HiBASIC. That doesn't make it a standard format, but might be worth a look.

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

Re: Making reasonable progress with a Sudoku solver

Post by crj » Thu Mar 15, 2018 5:07 pm

Oooh. That guy's relocator can also relocate zero-page usage. That's a nifty idea. (-8

SteveF
Posts: 510
Joined: Fri Aug 28, 2015 8:34 pm
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by SteveF » Thu Mar 15, 2018 11:40 pm

It's nothing particularly fancy, but my Acorn port of PLASMA has something like this in - the executable loads at &2000 (I was trying to keep it clear of screen RAM, which is why it doesn't load higher) and then relocates itself down to OSHWM/PAGE. You can see the code here: https://github.com/ZornsLemma/PLASMA/tree/merge8

The basic idea is that the assembly is done twice at different addresses, then a Python program compares the two and generates a list of the addresses which need to be patched up which is appended to the binary, as shown in this slightly simplified example:

Code: Select all

acme '-DSTART=$2000' -o rel/acorn/PLASMA vmsrc/acorn/32cmd.a
acme '-DSTART=$3000' -o rel/acorn/PLASMA.3000 vmsrc/acorn/32cmd.a
python vmsrc/acorn/add-relocations.py rel/acorn/PLASMA rel/acorn/PLASMA.3000
The relocation code is at VMINIT (line 214-ish) in vmsrc/acorn/plvm-post.s.

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

Re: Making reasonable progress with a Sudoku solver

Post by crj » Fri Mar 16, 2018 4:13 am

SteveF wrote:The basic idea is that the assembly is done twice at different addresses, then a Python program compares the two and generates a list of the addresses which need to be patched up
That's quite neat, actually. (-8

I'd been thinking in terms of tricks in the BASIC assembler like "JSR FNr2(some_address)" where FNr2 would add the current value of P%+2 to some list. Your technique is much simpler.

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

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Sat Mar 17, 2018 9:20 am

I like it!

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

Re: Making reasonable progress with a Sudoku solver

Post by flaxcottage » Sat Mar 17, 2018 11:57 pm

Using the T.Hardest example my wife completed the puzzle today! =D>

She began on the first day this thread was started and, taking into account the approximate time she spent on the puzzle her processor speed works out at 83Hz. :lol:
- John
Image

User avatar
leenew
Posts: 3796
Joined: Wed Jul 04, 2012 3:27 pm
Location: Doncaster, Yorkshire
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by leenew » Sun Mar 18, 2018 12:00 am

Excellent work Mrs. Flaxcottage =D>
Lee.

User avatar
daveejhitchins
Posts: 4655
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 » Sun Mar 18, 2018 7:17 am

flaxcottage wrote:She began on the first day this thread was started and, taking into account the approximate time she spent on the puzzle her processor speed works out at 83Hz. :lol:
=D> About twice my current speed . . .

Dave H :D
Parts: UM6502CE, GAL22V10D, GAL16V8D, AS6C62256A, TC514400AZ, WD1772, R6522, TMS27C512, AT28C256
Products: ARA II, ARA III, 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: 54
Joined: Thu Aug 10, 2017 8:07 pm
Location: Northamptonshire
Contact:

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Sun Mar 18, 2018 11:08 am

flaxcottage wrote:Using the T.Hardest example my wife completed the puzzle today! =D>

She began on the first day this thread was started and, taking into account the approximate time she spent on the puzzle her processor speed works out at 83Hz. :lol:
Golly. That shows a lot of determination. If my arithmetic is right (and I kind of hope I've made a mistake here), that works out at ~140 hours, assuming the program takes 21 seconds.

Code: Select all

21s * 2,000,000 / (83 * 60 * 60) ~= 140
Or, if you like, 7 hours per day, 5 days per week for 4 weeks. Basically a full time job.

I take my hat off to you Mrs. Flaxcottage.

Hopefully my program came up with the same solution.

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

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

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Sun Apr 01, 2018 2:11 pm

It's been a while, but I'm still working on this. It is still a work in progress, but here are today's development builds.

Electron (Mode 4, code at $1900)
BBC B (Mode 4 or 7, code at $1900)
BBC B with 2nd processor (Mode 1, 4 or 7, code at $0E00)
Master 128 with or without 2nd processor (Mode 129, 132 or 135, code at $0E00)

Model B builds start up in mode 7, the Master 128 build in mode 129 via !BOOT

Jeremy
Attachments
sudoku-modelb2p.ssd.zip
(6.43 KiB) Downloaded 17 times
sudoku-modelb.ssd.zip
(6.32 KiB) Downloaded 13 times
sudoku-master.ssd.zip
(6.29 KiB) Downloaded 19 times
sudoku-electron.ssd.zip
(5.72 KiB) Downloaded 11 times
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

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

Re: Making reasonable progress with a Sudoku solver

Post by crj » Mon Apr 02, 2018 1:09 am

Note the code can go at &800 on a second processor; most of the OS is missing. (-8

(Actually, if you're running pure machine code without using BASIC or similar, you can start at &400 and use contiguous RAM all the way up to &F800!)

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

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Mon Apr 02, 2018 2:06 pm

Here are today's development builds. There are some slight changes to the way (and when) results are displayed. The Master 128 build is now about ~4.4s faster at solving T.HARDEST than yesterday's build.

I suspect I'm close to running out of ideas for performance improvements.

Pro tem, the BBC B with 2nd processor build now loads at $1900, so that it can run on a vanilla Model B in mode 7 as well.

Jeremy
Attachments
sudoku-modelb2p.ssd.zip
(6.35 KiB) Downloaded 14 times
sudoku-modelb.ssd.zip
(6.23 KiB) Downloaded 12 times
sudoku-master.ssd.zip
(6.26 KiB) Downloaded 14 times
sudoku-electron.ssd.zip
(5.66 KiB) Downloaded 14 times
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

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

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Tue Jan 01, 2019 2:32 pm

It's been a while...

Basically I left this alone for some time while I had a bit of a ponder about how to progress things. In the end I decided I was making things too complicated for myself by trying to maintain all the BBC and Atari versions using the same code base. That got really messy. Also I switched assembler from MADS (back) to CA65, so I ended up reworking quite a bit of code.

Attached is the latest version which is MODE 7 only (sorry Electron users) for now and there is just one version for Model Bs & Masters.

There have been some modest speed improvements, but the main change has been to the recursive part of the solver. Er, basically it now works properly! What I had before didn't really work correctly and while it was able to solve a number of puzzles, this was more luck than judgement.

On the SSD there are some additional hard puzzle examples along with the original test cases / examples from earlier in the thread.

This is still very much an unfinished work in progress.

Hardest1.jpg
Hardest2.jpg

Jeremy
Attachments
Sudoku.ssd
(13.25 KiB) Downloaded 3 times
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

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

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Tue Jan 01, 2019 3:24 pm

Looks very nice indeed!

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

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Tue Jan 01, 2019 3:51 pm

To assist with entering puzzles, the attached will allow the following:

If you have input from elsewhere in this form...

Code: Select all

..3....8..5.1....66....74....8.9..4.7....5....1.6..8.....9...2.....2...8..2...3.4
...that is, a single line with either dots or spaces representing blank cells, then it can be pasted in via BeebEm. Choose "New" to edit a new puzzle, make sure you are in the top left hand cell, then paste.

Alternatively, loading from a text file is now supported. So the above string could be saved as a text file on the SSD and loaded from there. See T.TEXT01 on the attached SSD. There is some basic validation & translation of the input into the internal format. Anything after the first 81 bytes is ignored. In the picture below, these two files represent the same puzzle.

Dump.png

Jeremy
Attachments
Sudoku.ssd
(13.75 KiB) Downloaded 1 time
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

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

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Mon Feb 04, 2019 3:21 pm

Hopefully I'm getting close to a version of this I consider fit for general release.

After discovering that the recursive part of the solver didn't work very well, I decided to give it a bit more testing. To this end I found a collection of 26,370 "hard" puzzles online (I think from the same place BigEd found earlier examples) and spent several evenings running this through a version of the program.

AllResults.png
I also experimented with changing the order in which cells are guessed, to see if that helps. For any given puzzle that requires guesswork to solve, there isn't any obvious best strategy that I can see from just looking at the puzzle. Some search orders work better than others. Looking at the results above, I think that all the test cases have been generated by a program simply because searching forwards is so much faster than all the other strategies. This is not true for some other cases. The orders are:

Code: Select all

Fwd = Search from the top left cell forwards.
Rev = Search from the bottom right cell backwards.
Row = Order the rows by the number of blank cells at the time guesswork is first needed (ascending) and search the cells in that order.
Col = Same idea as Row, but using columns.
Box = Same idea as Row, but using 3x3 boxes.
This can be selected using the new "Order" option. I'm undecided as to whether this adds anything to the program or not. I may remove the option.

There are now three versions of the solver on the image (Model B, Master and Electron) and there is a crude loader program which tries to detect the machine it is running on and load the appropriate version. This loads into the cassette/RS423 buffer at $A00, hopefully that's a reasonable thing to do. Other than the title the Model B and Master versions are essentially the same, although my flow control macros may have generated the odd BRA instruction in the Master build.

The Electron version is basically the same except that it runs in MODE 6. It has the same layout as MODE 7, except that all the colour change codes are replaced with spaces. It looks a little plain, but at least managing the different versions is easier. I'm still unclear what best practice is for PAGE/ORG for an Electron, so pro tem it is set to $1900. If an Electron expert wants to tell me what to use, please do. Note that even if I assume a cassette based Electron and load the program at $E00, it will still run out of memory in edge cases although it seems not for realistic puzzles.

Model B/ Master

Mode7.jpg
Electron

Mode6.jpg
The information panel (Info option) is something I added for my own diagnostic purposes.

Also on the image is a file of test cases (TESTPAK). This consists of all the test cases I ran through the original Atari version, plus the first 10 "hard" puzzles from the 26,370 above. The program RUNTEST will run these test cases and output the results to the screen.

Dir.jpg
This is designed to generate a CSV file of statistics, so something like:

Code: Select all

*SPOOL RESULTS
*RUNTEST 0 0
*SPOOL
would generate a usable file. The first argument is the order (0-4, default 0) and the second is verbosity (0-2, default 2). Verbosity values are:

Code: Select all

0 - Just print statistics
1 - Include solution
2 - Include puzzle and solution
Example of verbose output.

RunTest.jpg
Enjoy!

Jeremy
Attachments
Sudoku-v0.9.ssd
(57.5 KiB) Downloaded 5 times
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

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

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Mon Feb 04, 2019 3:26 pm

Is there any sense in choosing a cell which has fewest valid possible values for the recursion?

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

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Mon Feb 04, 2019 4:03 pm

That's how the original version tried to work. I did implement this as an option earlier, but discarded it for some reason. I've got the code so it's easy enough to add back in to test. Now that I've got a set of test cases to run through I'll be able to compare timings.

Please stand by...

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

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

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Mon Feb 04, 2019 5:02 pm

Based on a small sample (HARDEST, BIGED, HARD1, HARD2 & EL0001), it isn't the fastest for any of them and in three cases it is actually the slowest. That combined with the fact that it is the slowest algorithm to generate the sequence is probably why I dropped it.

It sounds plausible that this should be a good choice and it might be if the sequence was recalculated (and by implication stored for each depth) so that it was always looking for the path of least effort, for want of a better term. It isn't, the sequence is calculated once based on the state of the puzzle when the first recursion happens. That's a significant change to the program, so I might not bother trying that.

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

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

Re: Making reasonable progress with a Sudoku solver

Post by BigEd » Mon Feb 04, 2019 5:24 pm

Ah right, indeed that's not quite what I was thinking of. Or indeed what I do, when solving manually - rows columns or squares with 5 or more numbers are where I concentrate. But if it doesn't fit naturally in the program, so be it!

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

Re: Making reasonable progress with a Sudoku solver

Post by EdwardianDuck » Mon Feb 04, 2019 9:21 pm

That's sort of what it's doing. If you choose Order=Box it orders the boxes by the least number of blank cells first, then generates the sequence from that. So it will try to fill out the most complete box first. Same for Row and Col.

So it's trying to make the best of the strategy it's told to use, but it's down to the user to pick the strategy.

Generally one of Box,Row and Col will be noticeably better than the other two, but there's no easy way of predicting which sequence will work best that I can see. For example, if there is one box with 4 blank cells but the smallest number of blank cells in a row or column is 5, then pick Order=Box. That seems sensible to me, but it's a lottery as to whether that's the best choice or not. Based on a few tests, it gets it wrong more often than not.

I've programmed this as a default "let the system decide" option, but again, I'm undecided as to whether it's of any benefit.

I'm coming to the conclusion that I'm over-thinking the problem and should just focus on getting it finished and released!

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

Post Reply