My own SuDoku solver, opinions please

JacKnife

Hi all, I just discovered the Sudoku puzzle about two weeks ago. Being a bit of a theoretical programmer by hobby, I decided to create my own version of a solver.

Here is the source: http://www.smackedassintosh.net/progs/source/sudoku/sudoku-smacked-1.0.tar.gz

It is written in C, should be ANSII compatible, and i know it to compile on AIX, Sun, and Linux. Let me know if someone wants binaries, and I can probably get some out there.

Some of the things that I do not do are:

1. Uniqueness testing
2. Use coloring (???)
3. Solve every puzzle

Although it does not solve every puzzle, the only ones it does not solve are the ones i've found on this forum. Which is why i'm posting here.

If it can solve a puzzle, it takes less then 0.5 seconds to do so on a 700 Mhz AMD processor, which I would consider very fast, please let me know if this is relativly not fast.

Other questions:

- Where can i find information on coloring for solving boards?
- What else am I missing?
- Is my 0.5 second max time to solve fast?

Thanks for reading.

gaby · Posted: Tue Oct 18, 2005 5:33 pm Post subject:

Information about colouring can be found on this forum, in particular here:

http://www.setbb.com/phpbb/viewtopic.php?t=311&mforum=sudoku

And other topics. This one is the one that explained it most clearly for me. Alongside with this one:

http://www.setbb.com/phpbb/viewtopic.php?t=321&mforum=sudoku

You should be able to wrap your head around it all.

We can't really tell you what you're missing until you've told us what method of analysis your solver does implement. 0.5 seconds to solve a board using simple brute force sounds about right, but my solver is written in PHP, and is therefore not that fast. It does solve puzzles in the most human like manner that I could manage. I'm more interested in getting accurate ratings for a puzzle than speed, so perhaps I'm not the best person to comment on speed Smile

_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

JacKnife · Posted: Tue Oct 18, 2005 7:04 pm Post subject:

gaby,

Hey, thanks for the links, I tried searching but most of the threads started way over my head.

With this solver I employ three methods attempting general elimination by brute force methods:

1. Scanning - determine what cells have only one possible solution

2. Section guessing - solve every solution for one section (a 3x3 box within the board), then solve for the cross sections. The goal is to determine if, in all the solutions possible, one cell could only have one value.

3. Filling the board - fill the entire board with one number and determine if, in all the solutions possible, any one cell had that number for every solution.

The fourth means I use to solve the board, if all these fail, is to start guessing for each empty cell, and then scan the board. If the scan completes the board, then the board is solved.

At the moment I only guess one number deep. I could go more, but the big O ends up very large, so perhaps adding color would help me solve these very hard boards within my 0.5 seconds.

At any rate, there it is, if anyone has any thoughts or suggestions that would be wonderful.

I hope to get my sudoku site up and running sometime this week, but we shall see. Thanks again.

Lummox JR · Posted: Tue Oct 18, 2005 7:40 pm Post subject:

It sounds like you're missing quite a few methods. #1 is for naked singles, but #2 sounds like you're trying to find a hidden single in a box. That's great, but you're not looking for hidden singles in a column or row, either.

#3 I don't get, but it sounds like Nishio. You should be going through a range of other techniques before you hit that. Among the more common techniques in roughly increasing difficulty:

Pointing pair/triple: In a given box, a certain digit can only fit into cells that all line up in the same column or row. That digit can be eliminated elsewhere in that column/row.

Box-line intersection: In a given column/row, a certain digit can only fit into cells that are all in the same box. That digit can be eliminated elsewhere in that box.

Naked subsets: A group of N cells in a box/column/row have at most the same N candidates, but no others. Those candidates can be eliminated from other cells in the box/column/row.

Hidden subsets: A group of N cells in a box/column/row are the only places where a set of N candidates can go. All other candidates in those cells can be removed.

X-wing/swordfish: For a given digit, in N columns it can only appear in the same N rows. The digit can be eliminated elsewhere in each of those rows. (You can switch columns and rows in those two sentences as well.) N=2 is an X-wing.

There is actually a large set of techniques. Other good ones include remote pairs, XY-wing, of course uniqueness and coloring, and then there's forcing chains (popular with some), supercoloring, tabling....

JacKnife · Posted: Tue Oct 18, 2005 8:32 pm Post subject:

Thanks for the breakdown of alternative techniques. It looks like more research is at hand.

Although, I dont know that I'm "missing" anything specific. My goal was to create the fastest solver I could. Using recursion with these methods has sofar proven very fast. If the combination of others yields a faster general purpose solver I would love to hear some results.

#3 is basically this, if I have the following board:

Ruud · Site Admin

Solving a Sudoku is basically a process of elimination. There are 81 digits that need to be placed in 81 cells, abiding the rule of 1 digit per row, column and box.

Most solving techniques require either a list of digits that can go into a particular cell (the candidates), or a list of cells that allow a particular digit within a row, column or box.

These are the lists that you need to keep track of:

a. for each cell (81): the candidate digits
b. for each row+digit (81) the available cells
c. for each column+digit (81) the available cells
d. for each box+digit (81) the available cells

Solving techniques are used to reduce all these lists to 1. Each time a technique eliminates a cell-digit combination, you update the 4 lists. If any of them reaches 1, you have bound a digit to a cell.

Keeping track of this data allows you to implement as many solving techniques as you like, as long as they interact with this basic data set.

xyzzy · Posted: Wed Oct 19, 2005 2:33 am Post subject:

You can find a comparison of solving speeds in this thread here.

To be honest with you, solving a single sudoku in .5 seconds isn't fast, in fact it's very slow for a solver written in C. To give you a comparison, my solver, in less than half the time (.2 seconds), on a computer about half as fast (400MHz P2), can solve over 1000 sudokus. If you want to be competitive you need to make your solver something like 1000 to 5000 times faster.

Convoluted logic techniques like coloring, forcing chains, your #2 and #3, etc. are't fast. A depth first search, called backtracking or trial and error here, is really quite fast. Most of the fancy 'logic' techniques involve a multi-level search of their own, and are really no more than trial-and-error themselves, except with different rules for how to make the trials and find the errors.

JacKnife · Posted: Wed Oct 19, 2005 3:22 am Post subject:

wow, I daresay all this information is way more then I was looking for, and has certainly sparked my interest.

Its funny but i've been searching google over the past week or so and in 1 day i've found everything i'd ever want to know about solving sudoku on this forum alone!

Thanks for all the info and knowlege.

I think I will revisit my methods and look to buid a faster scanner and go from there.

xyzzy: thanks for pointing me in the right direction.

others: thanks for the info on various solving techniques.

dukuso · Posted: Wed Oct 19, 2005 6:35 am Post subject:

what you describe (without knowing?) is already quite similar
to general constraint-programming-theory :

Ruud · Site Admin

Thanks for the translation.

I was already familiar with the publication by W.J. van Hoeve.

Being a database designer by profession I always tend to look at a problem from the data perspective. Smart data design often saves a lot of time in programming the code that handles the data.

Bombarding a beginning Sudoku programmer with constraint programming terminology just seemed a little unfair to me.

Lummox JR · Posted: Wed Oct 19, 2005 11:07 pm Post subject:

Oddly enough I was having very little luck writing a solver until I found an algorithm to implement DLX. Once I realized I could do the same stuff with DLX's columns and use rows to eliminate possibilities, I knew it would be a lot easier to build human-style solving techniques around that.