Talk:Sudoku solving algorithms/Archive 1
 | This is an archive of past discussions about Sudoku solving algorithms. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
| Archive 1 |
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)
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)
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)
Code
I removed the code, which I agree does not belong here. -Zahlentheorie 21:42, 16 May 2007 (UTC)
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)
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)
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
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)
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 of 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)
Naked pair, hidden pair, x-fish identity
Shouldn't it be noted that "naked pair", "hidden pair", "x-fish" strategies are computationally identical? --Voidvector (talk) 10:49, 17 October 2008 (UTC)
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).
- That's simply Hidden + Hidden Single + brute force. --Voidvector (talk) 16:27, 26 October 2008 (UTC)
Strange layout effect
I noticed a strange layout-effect. I solved it crude, maybe there is a better more elegant way. Problem was [this version]: start of section 7. ==Solving a blank sudoku grid== The section comes after two Images. Original source code:
Two examples of symmetrical sudokus with a small number of givens are shown here: [[Image:Symmetrical H and V 19 clue.JPG|thumb|180px|left|A 19-Clue Sudoku with Horizontal and Vertical Symmetry.]] [[Image:Symmetrical 18 clue sudoku 01.JPG|thumb|180px|none|An 18-Clue Sudoku with Symmetry on Both Diagonal Axes.]] ==Solving a blank sudoku grid== Although sudoku grids that etc
This way the sectiontitle appears in the middle of the page, not left-justified. Als, the first, left Image starts lower than the second, free (right) one.
As I can see no error in the code, I made a forced solution (i.e. left-justified section title) by adding a </nowiki>
</nowiki> after the second Image. </brIs there a correct/more elegant way? -DePiep (talk) 08:09, 3 April 2009 (UTC)
Greedy algorithm
Guys, use greedy algorithm! Sudoku is trivial programming task indeed.
Under "greedy" I mean:
place(x, y, num)
if not may_place(x, y, num)
return
put <num> on desk
find one of the cells with most filled row, column and subsquare
get its coordinates to <minx>, <miny>
for all possible numbers for that cell
place(minx, miny, possible number)
remove <num> from desk
Please sorry for clumsy pseudocode. More tricky thing is how to implement may_place() quick. But it does not very critically. I've code this task in BorlandPascal in 2005 (it was one of the tasks in our university programming contest). Today I've ported this to Delphi and tested with a dozen "hard" sudokus, from Paul Hsieh and this wiki page. It solves all momentarily, in less than second.91.199.156.161 (talk) 10:11, 19 May 2009 (UTC)
Dancing links
AFAICT, the dancing links algorithm is frequently used to solve sudoku problems. Yet there is not a link?
More on this....
The "exact cover" article explains the use of dancing links to solve sudoku. It should be mentioned here (not really needed there) that, as implemented simply in Knuth's paper, DLX will do additional backtracking. AFAIK the S-heuristic is equivalent to propagating naked singles and hidden singles. It does not account for "naked pairs" or row/column interaction.
For example, DLX with the S heuristic on 4*81 columns will not notice that {1,3} in {r1c8,r1c9} will eliminate 1 in r1c1. The smallest S value here is 2 and it is shared among both good and bad choices. Simply choosing the first candidate with the best S would place a 1 in r1c1 for the typical ascending/left-to-right ordered matrix. It will then find S=0 (Doh!) for placing a 1 in upper right block. The vertical linked list for that column is now empty and search(), with nothing left to do, will be forced to undo it's stupidity.
.46...9.. .59...784 783...562 ......... ......... ......... ......... ......... .........
More info on this here.
http://www.stolaf.edu/people/hansonr/sudoku/exactcover.htm
It's not a performance issue on 9x9 or even 16x16 puzzles but I am still waiting for an answer on a 25x25 puzzle using the S-heuristic alone. —Preceding unsigned comment added by 68.100.55.114 (talk) 21:12, 2 June 2009 (UTC)
Refactoring page
For what it is worth here is my suggestion on refactoring the page.
Breakout along following outline
(1) Solving puzzles
(1.a) Brute force techniques (NP-complete)
(1.a.1) depth first search (eg backtracking)
(1.a.2) breath first search
(1.b) Heuristics methods - (not Np-Complete)
(2) creating puzzles - (Always NP-complete)
Backtracking is a brute force method because you'd have to visit half of the nodes in the tree on average to get a solution.
Add any other techniques for solving puzzles to either (1.a) or (1.b)
The other variable in all of this is when do you stop? "Backtracking" typically stops when you find a solution, but it is simply a depth first search and you could spin through the rest of the nodes to find all the solutions.
The whole point with heuristics is to avoid having an NP-complete problem. Let's consider solving NxN puzzles with just naked singles and hidden singles. If the puzzle is solvable using these heuristics I don't have to guess at all. No guessing means no NP-completeness.
Now let's let N get bigger and bigger. You wouldn't be able to solve all puzzles, but the solutions to the ones that you could solve would occur in polynomial time. The difference between brute force and heuristics is the set of puzzles that you couldn't solve. More complex rules, then you can solve even a larger percentage. But solving with heuristics goes in polynomial time. Brute force (however refined the technique doesn't). —Preceding unsigned comment added by Um297zoa (talk • contribs) 00:52, 12 October 2010 (UTC)
Nitpick about terminology...
First paragraph of the "Exact Cover in solving sudokus" section reads as follows:
Sudoku can be described as an instance of the exact cover problem. This allows both for a very elegant description of the problem and an efficient solution using a backtracking algorithm.
I think the usage of the word "efficient" here is an opinion word, and it certainly doesn't match the usage of the word that I'm familiar with in the context of algorithmic study. The algorithm is still in NP--perhaps it is very fast for solving all proper 9x9 sudoku puzzles, but from a complexity theoretic point of view, this algorithm is still in the same category as the rest (still in NP, still in superpolynomial time on classical computers). If there aren't any objections, I think the above should be rewritten to avoid this vague, arguably incorrect introduction (perhaps even simply changing it to "relatively efficient"?) —Preceding unsigned comment added by 66.220.144.27 (talk) 16:44, 6 August 2010 (UTC)
- I removed the following inline paragraph from this section, partly because the focus is misleading, and partly because it's not worded for article space.
- Beware that Exact Cover is NP-complete problem, therefore it doesn't have efficient solution and description bellow substantially increases the size of data/memory, lacks the full definition (V is not defined at all) and can easily lead to a solution much more expensive than graph coloring for example. Mapping problems to NP-complete solutions is theoretical technique valuable for proofs but not for establishing efficient solutions. Shortcuts that allow efficient solution of some NP-complete problems become impossible when they get mapped to a more general problem.
- Lacks the full definition but always achieves the correct solution anyway? How is this a problem?
- potentiallyI've taken introductory courses in complexity theory in the distant past. Sudoku is being mapped into a larger problem space that encompasses all exact cover problems. This doesn't automatically make Sudoku as mapped NP complete; some clever person would have to verify that the Sudoku mapping subspace has the NP-complete property of the parent set (usually it does). Furthermore, it's not even possible to define NP complete on a fixed-size problem instance, and most readers are thinking grids that fit on a printed page. By the time you have a large enough Sudoku board where the running time sucks with Knuth's Dancing Links, I think many of the other solution methods would also be suffering from scaling pains. I've just run half a dozen exemplars of "most difficult" 9x9 Sudoku's through DLX (with my own heuristic to choose shortest columns) and had trouble finding problem examples exceeding 5000 digit placements running against a rudimentary choice heuristic. In Knuth's own paper, some tiling problems he set up for DLX ran incredibly fast, others didn't. A lot depends on how the problem embeds. What needs to be said is that mapping a problem into an NP complete potentially exposes you to run-away execution time as the size of the grid scales, but in practice, it's known to run dang fast on any Sudoku grid you're likely to find printed in a newspaper. One thing I will say about DLX is that it uses a generous amount of memory and really hits memory hard. It's not a great algorithm for resource constrained devices.
- Waving the NP complete voodoo doll a the exact cover is even sillier if Sudoku itself is NP complete. See the question posed to a complexity theorist by Robin Houston. It's subtle, which is another reason not to put too fine a point on this. — MaxEnt 01:13, 19 January 2011 (UTC)
What happened with this article?
Compare the article as of January 9, 2013 with some much older version, for example this.
They have almost nothing in common. The article lost most of the sudoku specific facts and is still problematic with referencing reliable sources.
"Computation time" section is about generating but not solving, is not correct at all, and ends with strange reference to a picture.
External links are out of the context too, especially the last one.
IMO the new version does not add value at all.
Isn't the article in this form a candidate for removal? Dobrichev (talk) 21:19, 9 January 2013 (UTC)
- Note the revision dated 05:00, 16 December 2012 by 1292simon, who reduced the size of the article by 24,391 characters (!!!) without any discussion on the talk page. I find this to be inconsistent with WP:CAUTIOUS, especially because he cited WP:NOTMANUAL and WP:TECHNICAL without discussing whether the removed material actually fell under those guidelines, or, if it did, whether it could be fixed (see WP:CANTFIX). I'm seriously inclined to revert the page to the previous version. 163.231.6.71 (talk) 05:02, 6 February 2013 (UTC)
- I intend to rewrite this at some point in the near future. I agree that the previous edit removed a lot of good information which should probably be brought back to the article. --LordSputnik (talk) 23:42, 5 June 2014 (UTC)
- Hello LordSputnik! I am a webmaster and I would like to have my page linked here. Being linked by wikipedia is good for the reputation of my page. To make it valueable enough I wrote a detailed theory section with almost everything I know about solving methods. On my page it is intended to be an instruction manual for my users. And I had a native speaker to translate it into "real" english. When you rewrite this article please consider www.SignumSingulare.com as a source of information - and if you think it's good, link it as reference, read further or where ever it belongs. If needed, I am willing to authorize the use of my pictures for the sudoku related articles in wikipedia as long as the source is named. Best regards, webmaster@SignumSingulare.com
- I intend to rewrite this at some point in the near future. I agree that the previous edit removed a lot of good information which should probably be brought back to the article. --LordSputnik (talk) 23:42, 5 June 2014 (UTC)
Refs
A user has added a link to a publication of their own in this pair of edits. Someone better than me with policies as well as Sudoku, please check whether it is appropriate or not. --Rsrikanth05 (talk) 04:01, 22 July 2014 (UTC)
Done. Dobrichev (talk) 05:52, 22 July 2014 (UTC)
- Hi, I didn't say remove it. I said, please check whether it is appropriate, as in whether it needs to be there or a hoax or not. That's all. --Rsrikanth05 (talk) 07:45, 22 July 2014 (UTC)
Comment about Brute force section
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)
- I agree with Razeetg's comments on both the backtracking and brute force sections. Maybe 'brute force search' implies that
- you enumerate all complete solutions and validate them. Note the examples in the speeding up brute-force search section of Brute force search
- cleverly reduce the size of the set enumerated, but this seems like a preprocessing stage. Once you start working through the enumeration
- you keep going. This contrasts to the 'brute force' algorithm given here, which considers partial solutions and avoids generating a vast
- number of complete (invalid) solutions.
- I don't see that this algorithm is some kind of minimal form of backtracking either. The article says If a cell is discovered where none
- of the 9 digits is allowed, then the algorithm leaves that cell blank and moves back to the previous cell. That's the backtracking part,
- and if the previous cell had a 9, then it would backtrack again, and keep going back as far as it needed to. In summary, I don't know what the
- exact definition of brute force is, and I suspect there isn't one. But to me the algorithm in this article is clearly backtracking. Housecarl (talk) 20:10, 13 August 2008 (UTC)
- I think its OK to rename the section as "Solving sudokus by simple backtracking". The article already has another section which describes backtracking, but it is describing a different algorithm. Here's one proposal for new titles for two of the sections:
- current title:
- Solving sudokus by backtracking
- rename to:
- Solving sudokus by backtracking with color assignment
- current title:
- Solving sudokus by a brute-force algorithm
- rename to:
- Solving sudokus by simple backtracking
- In renaming these sections I would place this later section above the other since it is the nominal algorithm. The other section employs color assignments, which is a slightly more advanced variation. If there are no objections I'll change the section labels later this week.Lithiumflash (talk) 15:33, 17 August 2008 (UTC)
- OK I started to adjust the article with the new proposed titles and then realized it won't make sense. There is sudoku in the article (near worst case) which may not be worst case for backtracking. Also, there are already TWO sections in the overall article which already cover backtracking.
- Furthermore, after review of the definition of brute force methodology, the existance of backtracking doesn't nullify the fact that the algorithm is a brute force search. Take a 4 digit number and imagine counting from 0 to 9999. In doing so, the singles digit advances from 1 to 9. At that point you change the singles digit back to a zero, and you backtrack to the 10's digit and advance it. Then you start incrementing the singles digit again. So even in simple counting it is necessary to backtrack. But one does not use the term "backtracking" to describe counting. It's an exhaustive enumeration. In the case where you test each instance against a rule then it is a brute force search.Lithiumflash (talk) 02:23, 24 August 2008 (UTC)
- Sorry, Lithiumflash, but I think you are wrong, and Housecarl above is right. The explanation given now (5 months after the discussion above) in the article is still two methods of backtracking, not backtracking and brute-force. You say that the presence of backtracking doesn't nullify the fact that the algorithm is a brute force search. Well, that is precisely the point: it is only brute-force if there is no backtracking. The minute you design an algorithm in which partial completions are discarded if they can not lead to the complete solution, then the method becomes backtracking. A method is really brute-force only if it generates candidates to a complete solution, and then discards them. You can not be clever, by abandoning partial candidates that won't be solutions, and be brute at the same time. It's an oxymoron. — isilanes (talk|contribs) 15:31, 30 January 2009 (UTC)
- So does that mean a "brute-force" algorithm cannot intelligently select the next possible candidate? Should a brute-force algorithm generate and check for 11111...1111, 11111...1112, etc? --Voidvector (talk)
- Yes. A Sudoku contains 81 single numbers (9 ones, 9 twos, 9 threes...) by definition. For an algorithm to really be brute-force, all combinations of these numbers should be tested (until a solution is found), in no preferential order, and discarding only full candidates, never partial candidates. Discarding partial candidates is, by definition, the distinctive mark of backtracking. E.g.: the combination "123456789(x9)" would be a valid candidate, as "111111111222222222...". The latter could be discarded as invalid the moment we introduce the second "one" in the same row as the first one, only if the algorithm is backtracking. If it's brute-force, then the whole 81-number guess should be tested for correctness. The combination "1(x81)", for example, is not a valid brute-force guess, because it is not formed with the initial 81 single elements available. Begin "smart" about not using 81 ones is within the algorithm (because by definition we have to use the possible combinations of the elements available), but being "smart" enough to discard partial guesses is not. — isilanes (talk|contribs) 12:03, 3 February 2009 (UTC)
- Seems we have totally different interpretation of "brute force". "Brute force" should simply a characteristic of a search algorithm whereby it goes through all the possible elements in the search space. It should not matter what the search algorithm use as its search space. For a sudoku problem, search space can potentially be input space, solution space, candidate space, constraint space, or something else. I do agree that a "brute force" algorithm should not backtrack, but disagree with whole idea of partial candidate/partial solution, since depending on the search space chosen, it is not always the same thing. --Voidvector (talk) 13:18, 3 February 2009 (UTC)
- Wikipedia has an article about mathematical brute force searches (http://en.wikipedia.org/wiki/Brute-force_search). The article explains partial candidates can be tested: "brute-force search is typically used when ... there are problem-specific heuristics that can be used to reduce the set of candidate solutions to a manageable size." Also: "One way to speed up a brute-force algorithm is to reduce the search space, that is, the set of candidate solutions, by using heuristics specific to the problem class." Currently the two articles are in agreement with each other, but if revisions are necessary I'm not opposed to them. In this article (sudoku) we should just be mindful of the fact that there are already two sections which discuss backtracking, and it's not the same methodology described in the brute force section.Lithiumflash (talk) 03:11, 9 February 2009 (UTC)
Currently, brute force and backtracking are describing the same thing as far as I can see 130.126.215.139 (talk) 04:17, 13 March 2017 (UTC)
Blank Sudoku grids - Remove this Section?
I think this entire section should be removed. A blank grid is not a Sudoku. It is also not an interesting puzzle, and it is not an interesting math problem. Since it is not a Sudoku it should be removed from this article. Since it is not an item of interest, it doesn't need to be moved to any other Wikipedia article. It should just be deleted. Any objections to this? LithiumFlash (talk) 00:59, 25 March 2017 (UTC)
Backtracking and Brute force algorithm Sections
From the references cited in the article it appears that "Backtracking" and "Brute force Algorithms" is the same algorithm concept. Therefore I will plan to merge these two sections. Also, about half the text in "Backtracking" is computer code, which I think should be removed. Please let me know if any comments or objections. LithiumFlash (talk) 15:36, 29 March 2017 (UTC)
Standardized Format for Sudoku Images
Between Sudoku, Mathematics of Sudoku, and Sudoku solving algorithms there are several formats for displaying a Sudoku (even within a single article). If any editors Add new Sudoku images, please go to ***Talk:Mathematics of Sudoku*** to see the suggested format. If comments please do not reply here. All comments on standardizing the format should be in the same Talk place.LithiumFlash (talk) 02:46, 1 April 2017 (UTC)
Developing (searching for) Sudokus
The section content at the moment:
"Computer programs are often used to "search" for Sudokus with certain properties, such as a small number of clues, or certain types of symmetry.[14] An algorithm will usually require more cycles (longer time) when searching for Sudokus with 20 clues or fewer. Sudokus with 17 clues are notoriously difficult to find, and when the constraint of symmetry is applied, the expected search time will dramatically increase yet further."
Some Sudoku generation algorithms benefit from the small number of clues, so the second sentence is invalid. Sudokus with 17 clues are difficult to find from scratch. The vast majority of the known 17-clue puzzles are close to each other and are easy to find by neighbour searching. The constraint of symmetry reduces the search space and dramatically decreases the search process.
After removal of the incorrect content only this would remain:
"Computer programs are often used to "search" for Sudokus with certain properties, such as a small number of clues, or certain types of symmetry."
Since this means nothing, I am removing the whole section. Dobrichev (talk) 23:48, 11 April 2017 (UTC)
- Dobrichev, I updated the text so it contains useful information. The Talk page of Mathematics of Sudoku shows there is an interest in knowing how Sudokus are created (topic #16). This section is short, but maybe it can be expanded in the future.—LithiumFlash (talk) 02:32, 13 April 2017 (UTC)
- I wouldn't argue whether the new edition contains useful information, but why you re-introduced the references to the same pictures in your site? I marked them as irrelevant. Dobrichev (talk) 08:01, 13 April 2017 (UTC)
- Dobrichev, I updated the text so it contains useful information. The Talk page of Mathematics of Sudoku shows there is an interest in knowing how Sudokus are created (topic #16). This section is short, but maybe it can be expanded in the future.—LithiumFlash (talk) 02:32, 13 April 2017 (UTC)
- The reference (#14) properly shows the source of a 17-clue symmetrical Sudoku. (RedEd making it from a list of non-symmetricals by Gordon Royle). Reference (#15) shows the original source of an 18-clue symmetrical Sudoku. It was posted in 7/2008, and I don't see it posted anywhere else at an earler time.
- This section in the article is still very short. There's plenty of room to add information about how Sudokus are made, and examples of interesting one's that have been discovered. Information about how Sudoku's are rated for difficulty would be good too. If you have any draft material (with references) that can be added let me know (here or at LithiumFlash). I can help clean it up and add it to the article.—LithiumFlash (talk) 15:17, 13 April 2017 (UTC)
worst case scenario compute timing
i find it very strange that a 3GHz cpu would take 30 to 45 minutes to solve this worst case puzzle. i made a java version based entirely on the description in this section and it solved the puzzle in 30.031 seconds on a 2.8 GHz Core 2 Duo 4000 series --116.15.178.189 (talk) 18:56, 25 July 2008 (UTC)
- On my old PC running at 500MHz I get 96 minutes. Yes I know my PC is archaic and I'm still using BASIC! The solution does require 641,580,843 iterations as described in the article. I wonder if you get the same number of iterations? Or is java that much faster???Lithiumflash (talk) —Preceding undated comment was added at 15:45, 17 August 2008 (UTC)
- I've got 69175316 iterations on my PC, as well using algorithm below and my own. Strange... 95.40.72.40 (talk) 18:27, 25 March 2010 (UTC)
I wrote a solver in Python for my own amusement before looking at this article. It used a recursive backtracking algorithm. After reading the article, I tried the puzzle that is aimed at backtracking. The original version took 69,175,315 iterations, same as the previous commenter reported. Given the clue that the first line was 987654321, I changed it to present the candidate numbers in reversed order. It solved the same puzzle with 31,974 iterations. With the order of presentation randomized before startup (one trial) it took 36,697,171 iterations. FWIW Maurice Fox (talk) 20:12, 10 August 2017 (UTC)
I since modified my solver to attack the rows that have the most clues first. After that change it solved the backtracking puzzle in 191,878 iterations, quite a way down from the original 69+ million. That change has equally beneficial effects on all the other puzzles that I have tried. I attribute that to two effects: First, the number of free cells in the rows attacked first is less than for empty rows. Second, the number of possibilities to try in subsequent rows is reduced. Again, FWIW. Time to set this aside and do something useful! :-). Maurice Fox (talk) 16:06, 14 August 2017 (UTC)
- Using scripting languages in an interpreter thad does not have JIT, this algorithm will be very slow. Probably, your Basic program is run in such an interpreter. Java, that uses JIT, is slower than the native code generated by g++, but much faster than Matlab, for example. See below.
- on my 533 MHz PPC 7410 solving the "near worst case" sudoku took 14 seconds with a "smart" brute force algorithm in assembler ... 141.20.5.230 (talk) 08:14, 20 October 2011 (UTC)
- Back-tracking brute force (simple recursion) algorithm solves the "near worst case" sudoku in Java ME (SDK 3.0.5, JDK 7u2) MIDP emulator in 2 min 15 s (JRE 7u2, Win7Ent, HP EliteBook 8440p, Core i5 M520, 2.4GHz). In Nokia 6210 Classic (ARM11 369MHz, S60) the same Midlet application takes 43 m 9s to solve the problem. :) Lauri.pirttiaho (talk) 16:55, 14 February 2012 (UTC)
- The following code compiled using
g++ sudoku.cpp -O3
- runs in 28 seconds on a 3.4 GHz Pentium 4.
#include <cstdio>
#include <ctime>
template<class T>
class Stack
{
public:
Stack(unsigned int n)
{
base=new T[n];
sp=base;
}
void push(T x)
{
*sp=x;
sp++;
}
T pop()
{
sp--;
return *sp;
}
~Stack()
{delete[] base;}
private:
T* sp;
T* base;
};
struct Sudoku
{
int data[9][9];
};
bool checkDigit(const Sudoku* s,int digit,int row,int col)
{
int i;
int j;
for(i=3 * (row/3) ; i<3 * (row/3) + 3 ; i++)
{
for(j=3 * (col/3) ; j<3 * (col/3) + 3;j++)
{
if(s->data[i][j]==digit && !(i==row && j==col))
{return 0;}
}
}
for(i=0;i<9;i++)
{
if(s->data[row][i]==digit && i!=col)
{return 0;}
}
for(i=0;i<9;i++)
{
if(s->data[i][col]==digit && i!=row)
{return 0;}
}
return 1;
}
void print(const Sudoku* s)
{
unsigned int i,j;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{printf("%d ",s->data[i][j]);}
putchar('\n');
}
}
int main()
{
unsigned int i;
unsigned int j;
unsigned int k=0;
Stack<int> iStack(81);
Stack<int> jStack(81);
Sudoku s={{{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,3,0,8,5},
{0,0,1,0,2,0,0,0,0},
{0,0,0,5,0,7,0,0,0},
{0,0,4,0,0,0,1,0,0},
{0,9,0,0,0,0,0,0,0},
{5,0,0,0,0,0,0,7,3},
{0,0,2,0,1,0,0,0,0},
{0,0,0,0,4,0,0,0,9}}};
Sudoku s0=s;
int t0=clock();
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(s0.data[i][j]==0)
{
for(k=s.data[i][j]+1;k<10;k++)
{
if(checkDigit(&s,k,i,j))
{
s.data[i][j]=k;
break;
}
}
if(k==10)
{
s.data[i][j]=0;
i=iStack.pop();
j=jStack.pop();
j--;
}
else
{
iStack.push(i);
jStack.push(j);
}
}
}
}
printf("Time: %d\n",clock()-t0);
print(&s);
return 0;
}
- The compiler version is version 3.4.5. It takes 239 seconds on Pentium II.
- The same algorithm implemented in Java runs on the Pentium 4 in 80 seconds.
java version "1.6.0_14" Java(TM) SE Runtime Environment (build 1.6.0_14-b08) Java HotSpot(TM) Client VM (build 14.0-b16, mixed mode, sharing)
- Compiler version is 1.6.0_14
- I currently try to test it in Matlab but it seems to take a lot of time! —Preceding unsigned comment added by 90.229.143.249 (talk) 12:06, 15 July 2009 (UTC)
- I have a simple implementation of the brute force approach which solves this grid in 24 seconds on pentium dual core 1.5GHz. My approach is brute force but it does contain a hand coding of the colour graph of the standard sudoku grid. Could it be that the overhead in calculating the graph despite being very simple to do adds significantly to the overhead given its required at every iteration?
#include <memory.h>
#include <stdio.h>
#include <time.h>
void Init(char* strI);
void Put(FILE* os);
void Test(FILE* os);
int Solve();
int MoveIsLegal(int nI, int nJ);
// Cells are numbered starting at zero in the top left to 80 in the bottom right
// and sequentially across each row. This 2d array contains the set of 20 cells
// connected to a given cell.
static const int g_nGraph[81][20] = {
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 18, 27, 36, 45, 54, 63, 72, 10, 11, 19, 20 },
{ 0, 2, 3, 4, 5, 6, 7, 8, 10, 19, 28, 37, 46, 55, 64, 73, 9, 11, 18, 20 },
{ 0, 1, 3, 4, 5, 6, 7, 8, 11, 20, 29, 38, 47, 56, 65, 74, 9, 10, 18, 19 },
{ 0, 1, 2, 4, 5, 6, 7, 8, 12, 21, 30, 39, 48, 57, 66, 75, 13, 14, 22, 23 },
{ 0, 1, 2, 3, 5, 6, 7, 8, 13, 22, 31, 40, 49, 58, 67, 76, 12, 14, 21, 23 },
{ 0, 1, 2, 3, 4, 6, 7, 8, 14, 23, 32, 41, 50, 59, 68, 77, 12, 13, 21, 22 },
{ 0, 1, 2, 3, 4, 5, 7, 8, 15, 24, 33, 42, 51, 60, 69, 78, 16, 17, 25, 26 },
{ 0, 1, 2, 3, 4, 5, 6, 8, 16, 25, 34, 43, 52, 61, 70, 79, 15, 17, 24, 26 },
{ 0, 1, 2, 3, 4, 5, 6, 7, 17, 26, 35, 44, 53, 62, 71, 80, 15, 16, 24, 25 },
{ 10, 11, 12, 13, 14, 15, 16, 17, 0, 18, 27, 36, 45, 54, 63, 72, 1, 2, 19, 20 },
{ 9, 11, 12, 13, 14, 15, 16, 17, 1, 19, 28, 37, 46, 55, 64, 73, 0, 2, 18, 20 },
{ 9, 10, 12, 13, 14, 15, 16, 17, 2, 20, 29, 38, 47, 56, 65, 74, 0, 1, 18, 19 },
{ 9, 10, 11, 13, 14, 15, 16, 17, 3, 21, 30, 39, 48, 57, 66, 75, 4, 5, 22, 23 },
{ 9, 10, 11, 12, 14, 15, 16, 17, 4, 22, 31, 40, 49, 58, 67, 76, 3, 5, 21, 23 },
{ 9, 10, 11, 12, 13, 15, 16, 17, 5, 23, 32, 41, 50, 59, 68, 77, 3, 4, 21, 22 },
{ 9, 10, 11, 12, 13, 14, 16, 17, 6, 24, 33, 42, 51, 60, 69, 78, 7, 8, 25, 26 },
{ 9, 10, 11, 12, 13, 14, 15, 17, 7, 25, 34, 43, 52, 61, 70, 79, 6, 8, 24, 26 },
{ 9, 10, 11, 12, 13, 14, 15, 16, 8, 26, 35, 44, 53, 62, 71, 80, 6, 7, 24, 25 },
{ 19, 20, 21, 22, 23, 24, 25, 26, 0, 9, 27, 36, 45, 54, 63, 72, 1, 2, 10, 11 },
{ 18, 20, 21, 22, 23, 24, 25, 26, 1, 10, 28, 37, 46, 55, 64, 73, 0, 2, 9, 11 },
{ 18, 19, 21, 22, 23, 24, 25, 26, 2, 11, 29, 38, 47, 56, 65, 74, 0, 1, 9, 10 },
{ 18, 19, 20, 22, 23, 24, 25, 26, 3, 12, 30, 39, 48, 57, 66, 75, 4, 5, 13, 14 },
{ 18, 19, 20, 21, 23, 24, 25, 26, 4, 13, 31, 40, 49, 58, 67, 76, 3, 5, 12, 14 },
{ 18, 19, 20, 21, 22, 24, 25, 26, 5, 14, 32, 41, 50, 59, 68, 77, 3, 4, 12, 13 },
{ 18, 19, 20, 21, 22, 23, 25, 26, 6, 15, 33, 42, 51, 60, 69, 78, 7, 8, 16, 17 },
{ 18, 19, 20, 21, 22, 23, 24, 26, 7, 16, 34, 43, 52, 61, 70, 79, 6, 8, 15, 17 },
{ 18, 19, 20, 21, 22, 23, 24, 25, 8, 17, 35, 44, 53, 62, 71, 80, 6, 7, 15, 16 },
{ 28, 29, 30, 31, 32, 33, 34, 35, 0, 9, 18, 36, 45, 54, 63, 72, 37, 38, 46, 47 },
{ 27, 29, 30, 31, 32, 33, 34, 35, 1, 10, 19, 37, 46, 55, 64, 73, 36, 38, 45, 47 },
{ 27, 28, 30, 31, 32, 33, 34, 35, 2, 11, 20, 38, 47, 56, 65, 74, 36, 37, 45, 46 },
{ 27, 28, 29, 31, 32, 33, 34, 35, 3, 12, 21, 39, 48, 57, 66, 75, 40, 41, 49, 50 },
{ 27, 28, 29, 30, 32, 33, 34, 35, 4, 13, 22, 40, 49, 58, 67, 76, 39, 41, 48, 50 },
{ 27, 28, 29, 30, 31, 33, 34, 35, 5, 14, 23, 41, 50, 59, 68, 77, 39, 40, 48, 49 },
{ 27, 28, 29, 30, 31, 32, 34, 35, 6, 15, 24, 42, 51, 60, 69, 78, 43, 44, 52, 53 },
{ 27, 28, 29, 30, 31, 32, 33, 35, 7, 16, 25, 43, 52, 61, 70, 79, 42, 44, 51, 53 },
{ 27, 28, 29, 30, 31, 32, 33, 34, 8, 17, 26, 44, 53, 62, 71, 80, 42, 43, 51, 52 },
{ 37, 38, 39, 40, 41, 42, 43, 44, 0, 9, 18, 27, 45, 54, 63, 72, 28, 29, 46, 47 },
{ 36, 38, 39, 40, 41, 42, 43, 44, 1, 10, 19, 28, 46, 55, 64, 73, 27, 29, 45, 47 },
{ 36, 37, 39, 40, 41, 42, 43, 44, 2, 11, 20, 29, 47, 56, 65, 74, 27, 28, 45, 46 },
{ 36, 37, 38, 40, 41, 42, 43, 44, 3, 12, 21, 30, 48, 57, 66, 75, 31, 32, 49, 50 },
{ 36, 37, 38, 39, 41, 42, 43, 44, 4, 13, 22, 31, 49, 58, 67, 76, 30, 32, 48, 50 },
{ 36, 37, 38, 39, 40, 42, 43, 44, 5, 14, 23, 32, 50, 59, 68, 77, 30, 31, 48, 49 },
{ 36, 37, 38, 39, 40, 41, 43, 44, 6, 15, 24, 33, 51, 60, 69, 78, 34, 35, 52, 53 },
{ 36, 37, 38, 39, 40, 41, 42, 44, 7, 16, 25, 34, 52, 61, 70, 79, 33, 35, 51, 53 },
{ 36, 37, 38, 39, 40, 41, 42, 43, 8, 17, 26, 35, 53, 62, 71, 80, 33, 34, 51, 52 },
{ 46, 47, 48, 49, 50, 51, 52, 53, 0, 9, 18, 27, 36, 54, 63, 72, 28, 29, 37, 38 },
{ 45, 47, 48, 49, 50, 51, 52, 53, 1, 10, 19, 28, 37, 55, 64, 73, 27, 29, 36, 38 },
{ 45, 46, 48, 49, 50, 51, 52, 53, 2, 11, 20, 29, 38, 56, 65, 74, 27, 28, 36, 37 },
{ 45, 46, 47, 49, 50, 51, 52, 53, 3, 12, 21, 30, 39, 57, 66, 75, 31, 32, 40, 41 },
{ 45, 46, 47, 48, 50, 51, 52, 53, 4, 13, 22, 31, 40, 58, 67, 76, 30, 32, 39, 41 },
{ 45, 46, 47, 48, 49, 51, 52, 53, 5, 14, 23, 32, 41, 59, 68, 77, 30, 31, 39, 40 },
{ 45, 46, 47, 48, 49, 50, 52, 53, 6, 15, 24, 33, 42, 60, 69, 78, 34, 35, 43, 44 },
{ 45, 46, 47, 48, 49, 50, 51, 53, 7, 16, 25, 34, 43, 61, 70, 79, 33, 35, 42, 44 },
{ 45, 46, 47, 48, 49, 50, 51, 52, 8, 17, 26, 35, 44, 62, 71, 80, 33, 34, 42, 43 },
{ 55, 56, 57, 58, 59, 60, 61, 62, 0, 9, 18, 27, 36, 45, 63, 72, 64, 65, 73, 74 },
{ 54, 56, 57, 58, 59, 60, 61, 62, 1, 10, 19, 28, 37, 46, 64, 73, 63, 65, 72, 74 },
{ 54, 55, 57, 58, 59, 60, 61, 62, 2, 11, 20, 29, 38, 47, 65, 74, 63, 64, 72, 73 },
{ 54, 55, 56, 58, 59, 60, 61, 62, 3, 12, 21, 30, 39, 48, 66, 75, 67, 68, 76, 77 },
{ 54, 55, 56, 57, 59, 60, 61, 62, 4, 13, 22, 31, 40, 49, 67, 76, 66, 68, 75, 77 },
{ 54, 55, 56, 57, 58, 60, 61, 62, 5, 14, 23, 32, 41, 50, 68, 77, 66, 67, 75, 76 },
{ 54, 55, 56, 57, 58, 59, 61, 62, 6, 15, 24, 33, 42, 51, 69, 78, 70, 71, 79, 80 },
{ 54, 55, 56, 57, 58, 59, 60, 62, 7, 16, 25, 34, 43, 52, 70, 79, 69, 71, 78, 80 },
{ 54, 55, 56, 57, 58, 59, 60, 61, 8, 17, 26, 35, 44, 53, 71, 80, 69, 70, 78, 79 },
{ 64, 65, 66, 67, 68, 69, 70, 71, 0, 9, 18, 27, 36, 45, 54, 72, 55, 56, 73, 74 },
{ 63, 65, 66, 67, 68, 69, 70, 71, 1, 10, 19, 28, 37, 46, 55, 73, 54, 56, 72, 74 },
{ 63, 64, 66, 67, 68, 69, 70, 71, 2, 11, 20, 29, 38, 47, 56, 74, 54, 55, 72, 73 },
{ 63, 64, 65, 67, 68, 69, 70, 71, 3, 12, 21, 30, 39, 48, 57, 75, 58, 59, 76, 77 },
{ 63, 64, 65, 66, 68, 69, 70, 71, 4, 13, 22, 31, 40, 49, 58, 76, 57, 59, 75, 77 },
{ 63, 64, 65, 66, 67, 69, 70, 71, 5, 14, 23, 32, 41, 50, 59, 77, 57, 58, 75, 76 },
{ 63, 64, 65, 66, 67, 68, 70, 71, 6, 15, 24, 33, 42, 51, 60, 78, 61, 62, 79, 80 },
{ 63, 64, 65, 66, 67, 68, 69, 71, 7, 16, 25, 34, 43, 52, 61, 79, 60, 62, 78, 80 },
{ 63, 64, 65, 66, 67, 68, 69, 70, 8, 17, 26, 35, 44, 53, 62, 80, 60, 61, 78, 79 },
{ 73, 74, 75, 76, 77, 78, 79, 80, 0, 9, 18, 27, 36, 45, 54, 63, 55, 56, 64, 65 },
{ 72, 74, 75, 76, 77, 78, 79, 80, 1, 10, 19, 28, 37, 46, 55, 64, 54, 56, 63, 65 },
{ 72, 73, 75, 76, 77, 78, 79, 80, 2, 11, 20, 29, 38, 47, 56, 65, 54, 55, 63, 64 },
{ 72, 73, 74, 76, 77, 78, 79, 80, 3, 12, 21, 30, 39, 48, 57, 66, 58, 59, 67, 68 },
{ 72, 73, 74, 75, 77, 78, 79, 80, 4, 13, 22, 31, 40, 49, 58, 67, 57, 59, 66, 68 },
{ 72, 73, 74, 75, 76, 78, 79, 80, 5, 14, 23, 32, 41, 50, 59, 68, 57, 58, 66, 67 },
{ 72, 73, 74, 75, 76, 77, 79, 80, 6, 15, 24, 33, 42, 51, 60, 69, 61, 62, 70, 71 },
{ 72, 73, 74, 75, 76, 77, 78, 80, 7, 16, 25, 34, 43, 52, 61, 70, 60, 62, 69, 71 },
{ 72, 73, 74, 75, 76, 77, 78, 79, 8, 17, 26, 35, 44, 53, 62, 71, 60, 61, 69, 70 } };
int g_nG[81];
void Clear()
{
memset( g_nG, 0, 81 * sizeof(int) );
}
void Init(char* pS)
{
int nI;
for ( nI = 0; (*pS) && (nI < 81); nI++, pS++ )
if ( (*pS) == '.' )
g_nG[nI] = 0;
else
g_nG[nI] = (int)( (*pS) - '0' );
}
void Put(FILE* os)
{
int nI;
for ( nI = 0; nI < 81; nI++ )
{
if ( (nI) && !( nI % 27 ) )
fprintf ( os, "|\n+---------+---------+---------+\n|" );
else if ( !( nI % 27 ) )
fprintf ( os, "\n+---------+---------+---------+\n|" );
else if ( !(nI % 9 ) )
fprintf ( os, "|\n|" );
else if ( !(nI % 3 ) )
fprintf ( os, "|" );
if ( g_nG[nI] )
fprintf ( os, " %c ", (char)(g_nG[nI]) + '0' );
else
fprintf ( os, " " );
}
fprintf ( os, "|\n+---------+---------+---------+\n" );
}
void gTest(FILE* os)
{
int nI;
Clear();
Put( os );
for ( nI = 0; nI < 81; nI++ )
{
int nJ;
fprintf ( os, "%02d:\n", nI );
Clear();
g_nG[nI] = 9;
for ( nJ = 0; nJ < 20; nJ++ )
g_nG[g_nGraph[nI][nJ]]++;
Put( os );
}
}
int Solve()
{
int nI = 0;
while ( nI < 81 )
{
if ( !( g_nG[nI] ) )
{
int nJ;
for ( nJ = 1; nJ < 10; nJ++ )
if ( MoveIsLegal( nI, nJ ) )
{
g_nG[nI] = nJ;
if ( !( Solve() ) )
g_nG[nI] = 0;
}
return 0;
}
nI++;
}
Put( stdout );
return 1;
}
int MoveIsLegal(int nI, int nJ)
{
int nK;
for ( nK = 0; nK < 20; nK++ )
if ( g_nG[g_nGraph[nI][nK]] == nJ )
return 0;
return 1;
}
int main()
{
time_t lt;
Init( "..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9" );
Put( stdout );
time( < ); fprintf ( stdout, "%ld\n", lt );
Solve();
time( < ); fprintf ( stdout, "%ld\n", lt );
return 0;
}
Fizzackerly (talk) 22:31, 16 December 2009 (UTC)
Proving max hypothesis rank on classic 9*9 sudokus?
Hello, I think it is rather easy and should have been done : Prove that any 9x9 standard sudoku, even the 17-clues, or others among the hardest ones, can be solved using >=50% assumptions?
Said differently: that all classic sudokus can be solved (i.e. using constraints/backtracking), branching matrices with max two options at a given cell, no options greater than 2 (3-9) are needed?
Another reformulation : when blocked looking for sure cells (given the constraints, only one value belongs there), you only need to make your (possibly various) hypothesis on cells that have two values possible. Then you explore the two sub-sudokus you created and find the right one. My point is to prove that making an hypothesis on a cell with more than two possibilities is not needed (i.e. creating 3 or more sub-sudokus from one cell). --Maxorazon (talk) 12:39, 30 November 2017 (UTC)
Animated Solving with recursive Backtrack Alogrithm
It displays ALL solutions if there are more than one and animates the process: https://0x8.ch/sudoku.js/
I pubilshed the solution under free MIT Clause 2 License: https://github.com/braindef/sudoku.js — Preceding unsigned comment added by 178.82.219.75 (talk) 23:35, 30 June 2018 (UTC)
External link to Sudoku Explainer by Nicolas Juillerat (Popular for rating Sudokus in general)
In this edition two dead links were removed (which was OK). Later in this edition I restored one of them to a valid source, and temporary restored the other to the dead link to Sudoku Explainer intending to fix it soon.
Later I unable to find a clone of Sudoku Explainer to point the link to.
Since then a project in github named Sukaku Explainer was created and IMO it is a good candidate to point the link to. In its initial version the original code from Nicolas Juillerat was assembled and checked by several independent sources.
If you find as appropriate replacement of the dead link to original Sudoku Explainer by a link to https://github.com/SudokuMonster/SukakuExplainer, keeping the name of the project an the attribution as is (to Nicolas Juillerat), please do it. Else probably the dead link is better to be removed.
It happened that I was involved in this project and I don't want to do this myself. --Dobrichev (talk) 12:07, 22 September 2019 (UTC)
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)
- The article is about solving, not generating Sudoku's. That would be off-topic. — MFH:Talk 13:18, 30 June 2023 (UTC)