The New Sudoku Players' Forum

[datprogrammer]

K, I've been Sudoking all day so for the last couple of hours, I decided I would give my brain a change of focus and start work on my own solver. Here's the first part of the story.

I chose C as it's quick and easy to knock up code in.

- Write a function to validate any partially filled grid (check rows 1-9 for multiple digits, check cols...check blocks)

- write a recursive function "solve()" that scans thruough the grid looking for a 0, then tries numbers 1-9 in that spot, if a valid digit is found, it calls solve again recursivly, if not and all 9 digits have been tried, it gives up on this iteration and returns.

The firsat run on a random "Hard" puzzle from Waynes program took about 260 seconds - I now the algorithm was AWFULLY inefficient but that time just sucked!

1st improvement - the checkgrid routine was rewritten to hold the checked digits in a single integer, using bit arithmetic to check each row, column and grid - that halved the time, but still no good.

2nd improvement - I realised that in the solve function, rather than checking the entire grid whenever I placed a number, I just needed to check the row/column and block that the cell was in. Whilst making this improvement, I also used a couple of arrays to get me the starting cell for any block, and the block number for any cell (assuming 9x9 grids) - eliminating a lot of calculations to work ouitwhihc block any cell was in and vice-versa.

That took me from 130 seconds down to a mere 0.2 seconds! (witjh 39,000 recursions into the solve function)

Interestingly, given a totally empty grid, it only takes 0.02 seconds and 392 recursions to find a solution (which is:

123 456 789
456 789 123
789 123 456

214 365 897
365 897 214
897 214 365

531 642 978
632 978 531
978 531 642


I can think of lots of improvements (obvious one being to do a simple candidate scan and only use valid candidates - which starts me on the road to a logic solver)

Not bad results though for such a simple minded (120 lines) C program and an hour or two tinkering!

[simes]

Did you also check that placing a digit in a cell didn't make any other cell unfillable? That could prune the tree a little bit more.

[datprogrammer]

Not yet Simes, I was just messing really, had an hour or so to kill.

There's lots I can do to improve the efficiency, such as maintaining a valid set of numbers for each cell.

I've got the time down to about 40 ms for my test puzzle, largely by chosing performce optimizer options on the compiler, and making one or two small optimisations - though one optimisation I made actuallly slowed it down - I replaced 3 function calls (checkRow, checkCol and checkBlock) with a single call that optimised out some common initialisations in the 3 functions - but this single call actually slowed it down by about 10% - compilers eh?! Mysterious beasts!

It's pretty mind blowing really that a modern processor can consider 40,000 grids in 40milliseconds, or 1 million grids a second - even with a very crude algorithmn.

I work with computers all day and I think it's easy to forget in this gui-oriented world just how mind-blowingly fast our little desktop pcs really are.

I'm going to think about a logical approach and see if I can't make something similar to yours (not to sell or anything, just as an intellectual excercise) that will solve using pure logic.

[bobkart]

Not bad results though for such a simple minded (120 lines) C program and an hour or two tinkering!

Someone posted a Sudoku puzzle at the Forums I administer (GT Times), and I was compelled to write a solving program, which I did in an hour or so, then someone else posted a link to this site, and I decided to see who else had written such programs, and found this Topic.

I was struck by the similarity of our results. I too chose C to program it in, since I have a C Compiler on my PC, and have used C for many years professionally. My program also came out to 120 (or so) lines, 124 actually with a 5-line block comment at the top. And my program takes but a fraction of a second to find the answer(s), as does yours.

Here's how it works, in case you're interested:

First I make a list of the vacancies. Then I call the recursive function to fill in the vacancies, which takes the index of the next vacancy to fill, this avoids searching for the next vacancy over and over. The code to fill in vacancies of course calls itself recursively on the next indexed vacancy, after first trying one of the possible value in its own vacancy. And the final efficiency comes from only trying possibilities that are not already taken on the row and column and 3x3 grid containing the vacancy, which a dozen or so line of code easily determines. That narrows the search greatly, resulting in considerably fewer recursions.

When it is finally asked to fill in a vacancy past the last one, it has solved the puzzle, and prints the solution. If there is more than one solution it finds them all. So I can't feed it an empty grid or it will print way too many solutions!

[Tom]

My algorithm is ~130 lines and only takes a few nodes to solve most puzzles. Here's one of the harder ones I've come across:

....1.78.5....9..........4..26.........6....3.74.8.........3..2.8..4..1.6..5.....

This one is solved in 36ms / 1403 nodes. (Athlon 64 3000+)

http://www.mottosearch.com/sudoku/

-Tom

[bobkart]

Very nice. Mine solves that one too, in under a second (I don't know how to measure the speed any better than that, coming from a Unix background and not knowing Windows that well), but I'm embarrassed to report how many recursions it had to do to get the answer (over a million). Maybe I need to sort the vacancies so I try the most constrained ones first. Also, I have no GUI on mine, it just reads from standard input and writes to standard output.

I see no mention of your algorithm (other than that it's clever) at your site. Are you keeping that to yourself?

[Tom]

Well, I suppose there is nothing to gain by keeping my algorithm a secret.

Without giving the entire thing away, I have an all-important (34 line) function that:
1) Generates the table of legal moves
2) Fills in any square that only has one move
3) Tests position legality, i.e., is there an empty square with no legal moves?
4) Detects solved positions

I call this function at the beginning of each node, which obviously simplifies the search tree enormously. Easy puzzles are solved by visiting 1 node.

-Tom

[bobkart]

Step 2 seems to be the one my algorithm would benefit from most. I could do a pre-pass through the list of vacancies, filling in any that only have one possibility, thus shortening the list. Of course repeated passes would be called for since filling one vacancy in might make others similarly fillable.

Thanks for the clues Tom. For now I doubt I'll change my program since "under a second" is plenty fast for me. It takes much longer to enter the puzzle in the first place.

I am slightly curious if there is some way I can get more accurate runtimes from my program. You mention 36ms, how were able to obtain that timing, are you making system calls from within your program, to get the clock and/or CPU time just before and just after finding the solution?

[Tom]

There's a Windows function called GetTickCount() which will return the number of milliseconds elapsed since IIRC your computer was turned on, but it's only accurate to 20ms or so.

Here's a function I wrote that returns the time (in seconds) using the high resolution 2MHz performance counter:

double get_time()
{
LARGE_INTEGER time;
double r;
static double freq = 0.0;
static LARGE_INTEGER first_time;

if (!freq) {
QueryPerformanceFrequency(&time);
freq = (double)time.QuadPart;
QueryPerformanceCounter(&first_time);
}
QueryPerformanceCounter(&time);
r = (double)(time.QuadPart - first_time.QuadPart);
r /= freq;
return r;
}

[bobkart]

I see. So you are measuring your real time from start of solution to end, in resolution of half a microsecond. I guess you get somewhat different answers depending on what else might be running, but taking the smallest time you ever get for a given problem is probably good enough for your purposes. Thanks again for the information.

I'll have to check to see if my C Compiler has that system call, I have lcc-win32 (freeware) as opposed to a "standard" Windows C Compiler. The downside is that much of what Windows C programmers (and I'm not one of those, I come from a Unix background as I mentioned) take for granted in the way of system calls is absent.

[Tom]

You may be able to do this:

#include <sys/timeb.h>
BOOL ftime_ok = FALSE; /* does ftime return milliseconds? */
int get_ms()
{
struct timeb timebuffer;
ftime(&timebuffer);
if (timebuffer.millitm != 0)
ftime_ok = TRUE;
return (timebuffer.time * 1000) + timebuffer.millitm;
}

But ftime isn't supported by all compilers and I think under Windows most ports of GCC will just call GetTickCount(), so you'll actually be getting ~20ms resolution instead of 1ms.

-Tom

[bobkart]

I guess I could test that by calling it in a loop until I got a different answer, and seeing how much it changed by.

Thanks again Tom.

[datprogrammer]

my braindead algorithm is pure brute force, when it finds an empty cell, it just starts counting from 1 to 9 until it finds a valid number, then moves on to the next empty cell, obviously it backtracks where necessary.

Very crude, very simple but very very fast. On a linux based 2.4ghz athlon, and code compiled with gcc -O3 it can solve any puzzle within 50ms, which is plenty fast enough for me!

I'm planning on making it smart, purely for my own programming interest.

[Tom]

datprogrammer, how long does your program take to solve the position that I posted earlier?
-Tom

[datprogrammer]

Tom,

My very crude algorithm struggles a bit on your grid, it takes 2.2 seconds and 939,410 iterations