Talk:Sudoku solving algorithms

The sample perl code does not produce any output?

The sample perl code does not produce any output? Jim Hardy 21:20, 26 February 2007 (UTC)[reply]

It took a little work (i.e. correctly removing embedded HTML, and changing & escapes to their correct values--i.e. I did not change the code itself at all), but I got the second program to work. The first handles a large case and might take a long time to finish?--SportWagon 22:21, 26 February 2007 (UTC)[reply]

Hello all, the first program takes quite some time as it does not sort vertices by the number of colors assigned in their zone. If you want a fast version of the first one, migrate the zones to the second one. The problem with the second one not producing any output is fixed. It failed to detect lines in the input that consist entirely of spaces and tabs, and should be skipped. As for the source code, copy and paste from the editor window to avoid HTML tags. -Zahlentheorie 22:46, 26 February 2007 (UTC)[reply]

constraint propagation

http://norvig.com/sudoku.html —The preceding unsigned comment was added by 125.99.216.13 (talk) 01:16, 26 April 2007 (UTC).[reply]

Dancing links

AFAICT, the dancing links algorithm is frequently used to solve sudoku problems. Yet there is not a link?

Cleanup / computer code

There is a heading on this article that says it needs cleanup and I agree with that. I also agree with problem of original research which should not be in the article.

First I see some people discussing how to solve things that are not sudoku puzzles, but variations (Like jigsaw, 10x10 grids, and grids much larger than the 9x9 normal sudoko grid). I think there is no point to explain those programs until after there is first a clear discussion on programs to solve just plain normal sudoku puzzles (whether easy or hard).

Also, I don't believe that any actual computer code belongs in this article. Explaining how a program works is OK, and perhaps a flowchart or diagram is OK. But actual code is too detailed and appears to present original research which is inconsistent with the principle of a good encyclopedia article.

Does anyone else agree? Would anyone object to large scale cleanup or revisions to adhere to what I suggest?

I entered the topic about brute force solvers, and I tried to adhere to what I just expressed (shows no actual computer code, and talks about solving an actual sudoko puzzle, not other types of puzzles. I hope others agree it is helpful to overall article. Thanks, Lithiumflash 00:29, 14 May 2007 (UTC)[reply]

Comparison of near worst-case for brute-force with the graph-coloring method

As of 2007, with CPU speeds of at least 1GHz the norm, the backtracking algorithm (graph coloring) on a Pentium 200 MHz will produce a solution of the Sudoku discussed in the article in 13 seconds:

host> cat difficult.sdk 

# a difficult sudoku

. . . . . . . . .
. . . . . 3 . 8 5
. . 1 . 2 . . . .
. . . 5 . 7 . . .
. . 4 . . . 1 . .
. 9 . . . . . . .
5 . . . . . . 7 3
. . 2 . 1 . . . .
. . . . 4 . . . 9


host> time ./sudoku.pl 9 difficult.sdk 
9 8 7 6 5 4 3 2 1
2 4 6 1 7 3 9 8 5
3 5 1 9 2 8 7 4 6
1 2 8 5 3 7 6 9 4
6 3 4 8 9 2 1 5 7
7 9 5 4 6 1 8 3 2
5 1 9 2 8 6 4 7 3
4 7 2 3 1 9 5 6 8
8 6 3 7 4 5 2 1 9
-----------------

real    0m13.875s
user    0m13.340s
sys     0m0.030s

-Zahlentheorie 18:44, 15 May 2007 (UTC)[reply]

Code

I removed the code, which I agree does not belong here. -Zahlentheorie 21:42, 16 May 2007 (UTC)[reply]

Solving a sudoku

I wrote myself a little program which actually solves simple sudoku puzzles, so thought I would put here the route by which I achieved it. Other people planning to write their own might want to consider the same method :-)

I did this in Visual Basic, so you will probably notice the VB command replace()...change as required

The first thing I did was work out which numbers were allowed in each box. I did this by scanning the 3x3 grid it was in and the row and column. I started with "123456789" and basically did a replace() of the values in each box in the grid/row/column against this string. So if the row had 1,3,5,8 and column had 2,7,9 and the grid had 6 then that leaves 4, meaning that the box *has* to be 4. I didn't actually put 4 in the box yet, I only ran the tests at this point (although it'd be possible to add the 4 if you want and it might speed up calculation)

Then I checked all boxes to see if there were any singular numbers (boxes with only one possibility)

Then I did the same but checked for any *unique* numbers in any row/column/grid (unique as in only appearing once in all possibilities on that row). If there's 9 boxes and one has the number 4 as a possible but no other box has it then that box *has* to be number 4

Then I did the same but checked for any double pairs (where there's 2 boxes with the same 2 numbers as the *only* possibilities...if I found a double pair, I removed those 2 numbers from the rest of that row/column/grid

Then I repeated this again and again. A simple sudoku grid took less than a second to solve.

Writing your own sudoku solver is an excellent challenge of programming skills...and it can be fun too :-) SmUX 22:29, 17 May 2007 (UTC)[reply]

Worst case scenario improvement?

Reading the sub-article on the worst case scenario, I was thinking about how one could re-arrange the numbers to produce faster computation times using the brute-force method. For example, by flipping the puzzle horizontally, one could improve computation time by about 9. Limiting the transformations to 90 degree rotation, flipping, and reordering of blocks (e.g. switch columns 123 with those of 456). Using these reversible transformations, what is the minimal ratio of time taken with the modified puzzle to that of the unmodified puzzle? A further thought is whether or not it would be possible to incorporate this 'reordering' into more efficient algorithms to improve the likelyhood of faster computation. Ghos two 20:30, 10 December 2007 (UTC)[reply]