1K Sudoku Solver

General games-related topics
Bukster
Posts: 46
Joined: Wed Sep 12, 2018 9:44 am

1K Sudoku Solver

Post by Bukster » Sat Jul 13, 2019 6:20 am

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 318 times
Here's the emulator file
1K Sudoku 130719.p
(835 Bytes) Downloaded 10 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.

Moggy
Posts: 1799
Joined: Wed Jun 18, 2008 2:00 pm

Re: 1K Sudoku Solver

Post by Moggy » Sat Jul 13, 2019 2:09 pm

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.

Moggy
Posts: 1799
Joined: Wed Jun 18, 2008 2:00 pm

Re: 1K Sudoku Solver

Post by Moggy » 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
Attachments
soduku.JPG

dr beep
Posts: 1188
Joined: Thu Jun 16, 2011 8:35 am
Location: Boxmeer

Re: 1K Sudoku Solver

Post by dr beep » Sat Jul 13, 2019 9:06 pm

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?

Bukster
Posts: 46
Joined: Wed Sep 12, 2018 9:44 am

Re: 1K Sudoku Solver

Post by Bukster » Sat Jul 13, 2019 10:23 pm

dr beep wrote:
Sat Jul 13, 2019 9:06 pm

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

Bukster
Posts: 46
Joined: Wed Sep 12, 2018 9:44 am

Re: 1K Sudoku Solver

Post by Bukster » Sat Jul 13, 2019 10:29 pm

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

Moggy
Posts: 1799
Joined: Wed Jun 18, 2008 2:00 pm

Re: 1K Sudoku Solver

Post by Moggy » Sat Jul 13, 2019 11:20 pm

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:

Bukster
Posts: 46
Joined: Wed Sep 12, 2018 9:44 am

Re: 1K Sudoku Solver

Post by Bukster » Sun Jul 14, 2019 12:44 am

@ 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 12 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.

Bukster
Posts: 46
Joined: Wed Sep 12, 2018 9:44 am

Re: 1K Sudoku Solver

Post by Bukster » Sun Jul 14, 2019 5:34 am

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.

dr beep
Posts: 1188
Joined: Thu Jun 16, 2011 8:35 am
Location: Boxmeer

Re: 1K Sudoku Solver

Post by dr beep » Sun Jul 14, 2019 11:17 am

You can save more bytes with a better compressed screen.
viewtopic.php?f=6&t=3275

Post Reply