Making reasonable progress with a Sudoku solver

Got a programming project in mind? Tell everyone about it!
User avatar
EdwardianDuck
Posts: 48
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: 716
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: 2058
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: 834
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: 2058
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: 834
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: 834
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: 2058
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: 3184
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: 3630
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: 4342
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, 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: 48
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: 48
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 7 times
sudoku-modelb.ssd.zip
(6.32 KiB) Downloaded 7 times
sudoku-master.ssd.zip
(6.29 KiB) Downloaded 8 times
sudoku-electron.ssd.zip
(5.72 KiB) Downloaded 6 times
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 » 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: 48
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 7 times
sudoku-modelb.ssd.zip
(6.23 KiB) Downloaded 7 times
sudoku-master.ssd.zip
(6.26 KiB) Downloaded 8 times
sudoku-electron.ssd.zip
(5.66 KiB) Downloaded 6 times
Master 128 + RetroClinic DataCentre + Internal Pi Zero Coprocessor, MiST

Post Reply