Algorithms

pirussas · Posted: Mon Oct 19, 2009 6:14 pm Post subject: Algorithms

Where can I find a good page with the advantages and disadvantages of the algorithms for solving sudoku?

Pete · Posted: Tue Oct 20, 2009 12:57 am Post subject:

If you're looking for solving techniques, you might start with http://sudopedia.org/wiki/Solving_Technique

You can also google "sudoku solving techniques" or something similar.

pirussas · Posted: Tue Oct 20, 2009 1:14 pm Post subject:

I have seen this site but I want a site where I can see the advantages and disadvantages of the algorithms

Pete · Posted: Tue Oct 20, 2009 9:01 pm Post subject:

I don't know of any such page on the Web. I'd like to help, but I'm not even sure what you're looking for.

What would you consider an "advantage" here? If an advantage is the ability to solve every possible sudoku, then you'd want a brute-force approach: either a straight depth-first search or maybe a slightly smarter search like dancing links. If advantage means that a technique can be easily used by human solvers, then those would be at the bottom of the list.

pirussas · Posted: Wed Oct 21, 2009 7:51 pm Post subject:

I seek advantages in solving sudoku nxn in the shortest time possible

Adak · Posted: Thu Oct 22, 2009 3:44 am Post subject:

ChPicard · Posted: Thu Oct 22, 2009 8:29 pm Post subject: BB_Solver and DLX

Adak · Posted: Thu Oct 22, 2009 11:31 pm Post subject:

No. BB_Solver uses it's own bit fields and arrays.

The DLX algorithm is a more general one, and the programs I've seen that use it, are substantially longer than Brit's programl.

briturner · Posted: Fri Oct 23, 2009 1:26 am Post subject:

Greetings,

Here are some notes on the algorithms I used:

First, as far as a guide, I used the guide at http://www.sudocue.net/guide.php. I found it extremely helpful, but that is just me. It will not help if you go with the DLX method.

I did timings using various methods. If the goal is strictly a fast solver, I recommend implementing Naked and Hidden Singles, as well as Locked Candidates.

pirussas · Posted: Tue Oct 27, 2009 9:44 am Post subject:

1) based on bit fields: Brit's bb solver is the fastest we've seen so far. The program is short, but working with bit fields is challenging. Human logic or solving techniques, are not their goal.

How does the technique Brit's bb? Where can I get information about it?

briturner · Posted: Wed Oct 28, 2009 1:13 am Post subject:

Greetings,

It really depends on your motivation:

If you want to learn about programming a sudoku solver, I recommend using a guide on human solvable techniques so you can understand the ideas behind the solvers and try a few yourself. Try implementing naked and hidden singles, along with a backtracker first. After you have a solver or two written yourself based on the guides, then start looking at how others did it. But by waiting until you tried a few things yourself, you avoid tunnel vision of just repeating other peoples work.

If you want to work on a generator, then grab the bb_sudoku files (there is a post in the programming sudoku forum with a link to the source code and executable), and link it in as a tester to run your puzzles through.

If you want to learn solving techniques only applicable for computers, study the DLX algorithm (Knuth has a good paper on it, though not specifically about sudoku).

If you want to do a vhdl based solver, or one for a gpu, then there is not alot of data to start from. These techniques are based on serial algorithms, vhdl is really more about doing things in parallel. You can use vhdl to verify a solution in a single clock (based really only on gate propagation delays).

So, it really depends on what you are after. Remember, the joy in writing a program is in the creation of something new. So, try some things out yourself before looking at what others have done.

Brit