Page 1 of 2

1K Sudoku Solver

Posted: Sat Jul 13, 2019 6:20 am
by Bukster
Sudoku driving you nuts and all you have to help is a 1K ZX81? Don't panic, here's a 1K program that will solve your sudoku for you.

Instructions are:

N and M = Move cursor around to enter clues
1 - 9 = Enter clue number (zero if you make a mistake to clear a clue number). Clues appear in inverse text.
C = clear entire grid
S = Solve in slow mode so you can see it going through the calculations
F = Solve in fast mode
Sudoku Solver.jpg
Sudoku Solver.jpg (4.42 KiB) Viewed 946 times
Here's the emulator file
1K Sudoku 130719.p
(835 Bytes) Downloaded 34 times
Thanks to Dr Beep for his help in learning to use the same efficient emulator he uses rather than Flat Assembler.

This means that even a 1K ZX81 can do sudoku so that doesn't bode well for us humans who can't do it.

Re: 1K Sudoku Solver

Posted: Sat Jul 13, 2019 2:09 pm
by Moggy
Superb work in 1k Bukster. :ugeek:

There is a 16k sudoku solver created by Simon Holdsworth that could accompany your version to show what can be achieved in both memory sizes and can be found here on his most excellent site...

http://www.zx81stuff.org.uk/zx81/supers ... oku81.html

Again great work in 1k.

Re: 1K Sudoku Solver

Posted: Sat Jul 13, 2019 7:47 pm
by Moggy
@Bukster.

Tried the following grid (see picture) on both emulator and real 81.
It never seems to get beyond the third line, going into an endless loop as it were. Have run it on emulator speeded up X100 and still no solution after 2hrs run. Just a heads up nothing more as I still think it's great for 1k. :D

Re: 1K Sudoku Solver

Posted: Sat Jul 13, 2019 9:06 pm
by dr beep
Bukster wrote:
Sat Jul 13, 2019 6:20 am
Thanks to Dr Beep for his help in learning to use the same efficient emulator he uses rather than Flat Assembler.
I think you mean COMPILER.

BTW: do you use the optimized base where the call to MC is fully placed over sysvar and so saving most bytes?

Re: 1K Sudoku Solver

Posted: Sat Jul 13, 2019 10:23 pm
by Bukster
dr beep wrote:
Sat Jul 13, 2019 9:06 pm

I think you mean COMPILER.
Whoops, brain slip. I did mean to say compiler

Re: 1K Sudoku Solver

Posted: Sat Jul 13, 2019 10:29 pm
by Bukster
Moggy wrote:
Sat Jul 13, 2019 7:47 pm
@Bukster.

Tried the following grid (see picture) on both emulator and real 81.
It never seems to get beyond the third line, going into an endless loop as it were. Have run it on emulator speeded up X100 and still no solution after 2hrs run. Just a heads up nothing more as I still think it's great for 1k. :D

Well done, you've spotted a bug there. The algorithm is a simple brute force counter that just goes through all the possibilities. If the first non-clue number (an 8 in your screen shot) becomes a nine and still doesn't solve then it should go back to the start, find a zero that indicates stop and exit without a solution, not just go around and around.

There are some sudoku puzzles that are designed to bamboozle this type of search. You've probably entered one of them. Thanks for finding the bug. I will investigate and upload an improved version

Re: 1K Sudoku Solver

Posted: Sat Jul 13, 2019 11:20 pm
by Moggy
If it's any consolation I tried it with the so called hardest grid in the world devised by a Finnish mathematician and it solved quite easily. :lol:

Re: 1K Sudoku Solver

Posted: Sun Jul 14, 2019 12:44 am
by Bukster
@ Moggy

I found the problem. The zero to indicate stop went missing in the change over to the new compiler from the other compiler I had written it on. If I input your clue numbers and hit solve, it goes around and around until it stops with no solution found.

I tried your clues with an on line solver and it rejected it as not solvable. It didn't take me five minutes to see the problem and fix it here is an updated version that will end if it can't find a solution.
1K Sudoku 140719.p
(828 Bytes) Downloaded 28 times
It may take a little longer than most sudoku solvers, but I think we've shown yet another task that can be done on only 1K if we put our minds to it.

One feature this solver also has is a real time checking system. Try entering a number twice in the same row, column or box and it will not accept it. So it has a validation system built in too.

Re: 1K Sudoku Solver

Posted: Sun Jul 14, 2019 5:34 am
by Bukster
dr beep wrote:
Sat Jul 13, 2019 9:06 pm
BTW: do you use the optimized base where the call to MC is fully placed over sysvar and so saving most bytes?
You bet I did. I just totally copied the code you'd put into the 1K Jewel game and used that. So this program does not ever use the Basic system.

Re: 1K Sudoku Solver

Posted: Sun Jul 14, 2019 11:17 am
by dr beep
You can save more bytes with a better compressed screen.
viewtopic.php?f=6&t=3275