Four line sudoku solver

rwaddilove · Posted: Fri Mar 17, 2006 12:02 pm Post subject: Four line sudoku solver

Sudoku puzzles can be solved with just 4 lines of code. Here's it is:

1 sp(cell(ptr))=(sp(cell(ptr)) + 1) mod 10
2 if sp(cell(ptr))=0 then ptr=ptr+1:goto 1
3 if countnum(cell(ptr))=3 then ptr=ptr-1
4 if ptr>-1 then goto 1

Of course, it needs a bit of explanation. This is a brute force method, but it is so short and simple that it is very fast. You need to create two arrays and a pointer like this:

sp(80) is the sudoku puzzle - 9 x 9 grid, 81 cells, numbered 0-80
cell(80) is a list of blank cells - when you read in the puzzle, store the blank cell numbers here
ptr=points to the last blank cell in the list

One other thing you need is a countnum() function. This counts how many times a number appears. It should appear once in a row, once in a column and once in a block, hence the if countnum()=3 then...

That's it. You want to see some real code? Here it is in Visual Basic - I dislike goto so the structured version is a little longer:

rwaddilove

I tracked down the hardest puzzle I could find on this board and ran it through the Visual Basic program above. It took about 40 seconds to solve. Removing the For...Next loops in the CountNum function and writing out the code in full reduced this to 9 seconds, which is quite a saving.

However, seeing other people talking of solving puzzles in milliseconds left me slightly disappinted to say the least.

I copied the code from VB and pasted it into Blitz Basic. Hardly any changes were required to get it working and when I ran the same puzzle, it was solved in around 700 milliseconds. It just shows what a difference the compiler makes.

I wonder if C would be even faster?

Can anyone write in assembly language these days? Presumably this would be the ultimate, but I've not done this since the days when everything was Z80 or 6502 powered.

tarek · Posted: Sun Mar 19, 2006 11:33 am Post subject:

I actually had one of those,

It was revolutinary in its time as it had a whole 1KB of memory....which then can be expanded to a " 16 KB " memory, I wouldn't have thought that it would withstand DLX or even brute force to be honest Very Happy

Tarek

rwaddilove · Posted: Sun Mar 19, 2006 1:30 pm Post subject: Down memory lane

You're thinking of the ZX-81, I think. I was just talking about the Z80 processor in general, which was used in several different computers. You could quite easily write a soduku solver for the ZX-81 because it requires very little memory and only about 20 or 30 lines of Basic. Mind you, it would take about 3 days to come up with a solution! Anyone want to try this with a ZX-81 emulator?

LangPol · Posted: Mon Mar 20, 2006 2:18 pm Post subject: Re: Four line sudoku solver

Never, ever, throw out something like that. It sounds like a challenge.

Here's a Perl version, not mine, andall you need is the array A:

use integer;@A=split//,<>;sub R{for$i(0..80){next if$A[$i];my%t=map{$_/9
==$i/9||$_%9==$i%9||$_/27==$i/27&&$_%9/3==$i%9/3?$A[$_]:0=>1}0..80;R($A[
$i]=$_)for grep{!$t{$_}}1..9;return$A[$i]=0}die@A}R

3 lines.

foxglove · Posted: Mon Mar 27, 2006 6:34 pm Post subject: Re: Four line sudoku solver

elroy · Posted: Sat Apr 01, 2006 7:19 pm Post subject:

rwaddilove fm elroy:
Even in VB, your cute algorithm can be speeded 60 times faster * - and be smaller - if done in the "quise" of machine-language & bit-manipulation as you inclined:
Your complete VB routine, for example, could evolve to following, requiring just initial setup of its arrays (for which, further below at bottom, an illustrative example/working macro [Excel] is also submitted)

elroy · Posted: Sat Apr 01, 2006 7:40 pm Post subject:

BTW here's a good valid test-puzzle - Vidarino's old "Monster #2:

Agent Allen · Posted: Sun Apr 02, 2006 9:00 pm Post subject: Re: Four line sudoku solver

docnzok · Posted: Mon Apr 10, 2006 8:34 pm Post subject: Testing your theory

Hey,

I am trying to test your code in VB, but am having trouble accessing the array member that is stored with the pointer.

Can you send me the code that you used to declare the pointer and then how you access that memory location.

I am in sync with everything else you are doing.

Thanks

I declare the pointer like this.
Dim ptr As Long

The set it like this
ptr = VarPtr(cell(x))

I get a memory address correctly using this technique but when I try to reference the ptr using your code:
sp(cell(ptr))
I get out of range because the memory address is way higher than the original cell(80) declaration.

Thanks

Germanboy · Posted: Wed May 10, 2006 11:29 am Post subject: complete source code

who can send me the complete source code (all parts zipped)? iI cannot understand the whole code from rwaddilove!

Thanks

Germanboy

Lunatic · Posted: Wed Mar 14, 2007 10:24 pm Post subject:

I've put a small VB6 program on my website to test any sudoku if it has one, more then one or no solution at all. The program is based on the code from rwaddilove.
Since this is my first posting in this forum, I'm not allowed to post any URL, so contact me if you want me to send the zipped source code.
Greetz,
Lunatic Wink

Pat · Posted: Fri Mar 16, 2007 9:48 am Post subject: re: Website

Lunatic · Posted: Thu Mar 22, 2007 11:28 pm Post subject:

Ok, I have rearranged my website so that the zipped file of the sudoku test can be downloaded easely.
I also added my website's url at my profile. Choose "English" and then "Sudoku". You'll find a screenshot of the little program and a link to download.
I've included some basic solving techniques in the sudoku uniqueness tester, to assist solving (pre-solve) before the brute force solving. There's an evil sudoku in .txt format in the zipped file (to be dragged 'n' dropped). There are some additional lines added at the brute force routines, so one can see the brute force at work on screen, but this will slow down the proces. You can even dowload my own sudoku programm 'MPQ Sudoku' from my website.

Have fun.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~