Talk:Algorithmics of sudoku
From Wikipedia, the free encyclopedia
[edit] Qassim Hamaza is isomorphic to a previously posted puzzle
This is to highlight this matter. It was also discussed fully on the sudoku players' forums http://www.sudoku.com/boards/viewtopic.php?t=4212&postdays=0&postorder=asc&start=825 The puzzle was posted by Ocean on 2 Nov 2006 on the sudoku players' forums (It was known afterwards as the gold list #5) http://www.sudoku.com/boards/viewtopic.php?t=4212&postdays=0&postorder=asc&start=331 It was considered one the hardest at the time it was posted.
001002000030040050600700800006000007010000030900000600007001008040030020000500900
Oysterkite posted an isomorphic version on the forums on 24 May 2007 labelling it as Qassim Hamza http://sudoku.com/boards/viewtopic.php?p=44330#44330 It then appeared on this wiki page added by AMcDermot on 12 August 2007 http://en.wikipedia.org/wiki/Special:Contributions/AMcDermot I removed the puzzle for the above reason and because it no longer is considered among the hardest. Thanks to Pat from the players' forums who made the links available. SudokuBoss (talk) 09:39, 16 April 2008 (UTC)
[edit] Revisions to Exceptionally Difficult Sudokus
This section is being used as a web index for software. I am removing statements such as "Go here for software to solve this sudoku".
I don't think the puzzle "gen_171_59_0_10" is very difficult. One cell in the first row (r1c6) has 3 options: 2,5 or 6. If you try a 6 the rest of the puzzle can be solved with nothing more difficult than hidden pairs. But I'll leave it in the article to see if there is any other discussion about it.
The comment "while there is often a unique solution" is extraneous. By definition a sudoku puzzle has a unique solution.
The article was left with references in places which don't make sense. I am restoring the article so that statements and their references match each other.
I left Timothy57's paragraph in the article but fixed spelling mistakes such as "uaing" -> "using". As I mentioned I moved references out of the body of the article, but left the links so people can try the software. Lithiumflash (talk) 02:56, 11 April 2008 (UTC)
- There has been several discussions on the popular sudoku forums regarding the "Hardest sudokus". the most active of these is on the Sudoku Players Forums http://www.sudoku.com/boards/viewtopic.php?t=4212&postdays=0&postorder=asc&start=0.
- The Puzzle referred to as "Qassim Hamza" is a reshuffled version of a previously posted puzzle by Ocean. The rest of the puzzles currently on this wiki page are "TOO EASY" compared to the most recent "hardest".
- The following is a compilation of the hardest sudoku puzzles as of APRIL 2008 according to Openly accessible solver Programs:
Rating Program: gsf's sudoku q1 (rating) Rating: 99408 Poster: JPF Label: Easter Monster 1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1 1 . . | . . . | . . 2 . 9 . | 4 . . | . 5 . . . 6 | . . . | 7 . . ------+-------+------ . 5 . | 9 . 3 | . . . . . . | . 7 . | . . . . . . | 8 5 . | . 4 . ------+-------+------ 7 . . | . . . | 6 . . . 3 . | . . 9 | . 8 . . . 2 | . . . | . . 1
Rating Program: gsf's sudoku q1 (Processing time) Rating: 4m19s@2Ghz Poster: tarek Label: tarek071223170000-052 ..1..4.......6.3.5...9.....8.....7.3.......285...7.6..3...8...6..92......4...1... . . 1 | . . 4 | . . . . . . | . 6 . | 3 . 5 . . . | 9 . . | . . . ------+-------+------ 8 . . | . . . | 7 . 3 . . . | . . . | . 2 8 5 . . | . 7 . | 6 . . ------+-------+------ 3 . . | . 8 . | . . 6 . . 9 | 2 . . | . . . . 4 . | . . 1 | . . .
Rating Program: Nicolas Juillerat's Sudoku explainer 1.2.1 Rating: 11.9 Poster: tarek Label: golden nugget .......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7..... . . . | . . . | . 3 9 . . . | . . 1 | . . 5 . . 3 | . 5 . | 8 . . ------+-------+------ . . 8 | . 9 . | . . 6 . 7 . | . . 2 | . . . 1 . . | 4 . . | . . . ------+-------+------ . . 9 | . 8 . | . 5 . . 2 . | . . . | 6 . . 4 . . | 7 . . | . . .
Rating Program: dukuso's suexrat9 Rating: 4483 Poster: coloin Label: col-02-08-071 .2.4.37.........32........4.4.2...7.8...5.........1...5.....9...3.9....7..1..86.. . 2 . | 4 . 3 | 7 . . . . . | . . . | . 3 2 . . . | . . . | . . 4 ------+-------+------ . 4 . | 2 . . | . 7 . 8 . . | . 5 . | . . . . . . | . . 1 | . . . ------+-------+------ 5 . . | . . . | 9 . . . 3 . | 9 . . | . . 7 . . 1 | . . 8 | 6 . .
Rating Program: dukuso's suexratt (10000 2 option) Rating: 2141 Poster: tarek Label: golden nugget .......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7..... . . . | . . . | . 3 9 . . . | . . 1 | . . 5 . . 3 | . 5 . | 8 . . ------+-------+------ . . 8 | . 9 . | . . 6 . 7 . | . . 2 | . . . 1 . . | 4 . . | . . . ------+-------+------ . . 9 | . 8 . | . 5 . . 2 . | . . . | 6 . . 4 . . | 7 . . | . . .
- I will be removing all of the current puzzles, replacing them with the puzzles above within the next 48h.
- SudokuBoss (talk) 21:51, 14 April 2008 (UTC)
-
- I have rewritten the entire section. Some contributions such as the one by 129.31.206.45 had to be removed as it was referencing older material, so apologies for any inconvenience caused.
- SudokuBoss (talk) 13:21, 15 April 2008 (UTC)
[edit] Unique solution for qassim hamza puzzle?
Timothy57 has edited the article with a statement that the qassim hamza sudoku does not have a unique solution. Will he please give a reference and show TWO OR MORE solutions to the puzzle? (please dont refer us to programs with poorly designed interfaces). Please cite two different solutions to the puzzle here.
I have omited these statements from the article until Timothy57 can substantiate his information. Lithiumflash (talk) 02:38, 9 April 2008 (UTC)
Thanks Lithiumflash for spotting my error so quickly. I miscoppied the Quassim Hamza puzzle and found two distinct solutions to a different board. My sincere appologies. Now that I have correctly coppied the board, I have verified, using the program I cited, that the solution is unique. The program takes 2 ms to find the solution, makes 61 guesses of which 7 are correct and has a maximum depth of 9.
The interface to the console program is non-existant, although I don't think that the C++ interface is that bad. There is also a GUI interface for use in Windows. Timothy57
[edit] Generator is Missed!
Only solution algorithmics are showed, is very important to show a generator algorithmic. —Preceding unsigned comment added by 201.50.233.2 (talk) 20:56, 9 January 2008 (UTC)
- The backtracking algorithm will act as a generator when run on an empty board. The Perl code is still available somewhere in the history of the page. -Zahlentheorie (talk) 21:03, 9 January 2008 (UTC)
[edit] 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)
- 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)
- 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)
[edit] 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).
[edit] Dancing links
AFAICT, the dancing links algorithm is frequently used to solve sudoku problems. Yet there is not a link?
[edit] 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)
[edit] 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)
[edit] Code
I removed the code, which I agree does not belong here. -Zahlentheorie 21:42, 16 May 2007 (UTC)
[edit] 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)
[edit] 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. Ghostwo 20:30, 10 December 2007 (UTC)
I think this discussion page is to discuss the article (how to improve it), not to discuss puzzles in the article. But you still raise an interesting point. You can flip the puzzle to get a faster solution, but how would you know to do that if you don't know the solution beforehand? Lithiumflash (talk) 15:42, 1 January 2008 (UTC)
- Wouldn't it just make sense to start at the bottom right rather than the top left for the simple reason that you therefore have a digit provided in the first position? -88.109.14.76 (talk) 15:24, 13 February 2008 (UTC)
Thats a good question. For a program which solves sudokus by brute force I haven't seen any research to show if its worthwhile to manipulate the solving order to improve the solve time. In most cases a puzzle will probably solve faster if you start at a clue location. But I wonder if that is universally true for every sudoku. I think a lot of programmers have found ways to improve the solving time using a brute force search. That might be a good topic to add to the article. But remember, the content in a Wikipedia article is not for speculation or original research. Lets hope someone can provide a good substantiated reference on how a brute force algorithm can be improved.Lithiumflash (talk) 03:53, 3 March 2008 (UTC)
[edit] Bruteforce section is wrong!
I believe that the brute force section is not actually describing the bruteforce method, but it again describes the backtracking algorithm. Backtracking This should be rewritten. The subtle difference between the two is that in backtracking, you do not create the whole (probably wrong) sequence first and then check, but instead, you check for correctness with each column. It is a refined brute force.
Also, I believe part of the backtracking section should go to a sub section called mapping to graph coloring problem or something like that. Razeetg (talk) 09:15, 29 April 2008 (UTC)
- According to your reference backtracking is a subset of brute force, therefore this section IS in the scope of brute force. Can we say the algorithm is elevated to "backtracking"? When solving a sudoku the algorithm described will not test "3456" in positions 1-4 if "345" in positions 1-3 have already been proven invalid (it will advance to "346"). I don't think this shortcut is enough to place this in the realm of "backtracking". Its just a well written brute-force algorithm (in my opinion). But if others disagree then I'm OK to re-title this section as "A simple backtracking algorithm".
- I do agree with you that the section currently titled as "backtracking" needs improvement, or re-labeled as something else.
- Lithiumflash (talk) 01:48, 9 May 2008 (UTC)
