STR #1361: fltk-sudoku does not generate sudokus

STR #1361

Application:	FLTK Library
Status:	1 - Closed w/Resolution
Priority:	2 - Low, e.g. a documentation error or undocumented side-effect
Scope:	3 - Applies to all machines and operating systems
Subsystem:	Example Programs
Summary:	fltk-sudoku does not generate sudokus
Version:	1.1-current
Created By:	rillig
Assigned To:	mike
Fix Version:	1.1-current (SVN: v5356)
Update Notification:	Receive EMails Don't Receive EMails

Trouble Report Files:

No files

Trouble Report Comments:

#1	rillig 22:45 Jul 21, 2006

A sudoku is defined to have _one_ _unique_ solution. The code that generates sudokus does not include this test. For example, in the "impossible" level it generated the following "sudoku", which has 57635 solutions. 32-9----- 7-----96- ------3-2 8----9--- -----5-1- 2----8--- -----4--7 ----5---4 --6--1---

#2	mike 06:31 Jul 22, 2006

Please provide a reference to official documentation (not Wikipedia) that defines this restriction. I've played many Sudoku puzzles from published books that have multiple possible solutions. The first three FLTK Sudoku game levels will generate puzzles with only 1 or 2 possible solutions (2 solutions == a matter of transposed pairs), but Hard and Impossible introduce more possible solutions in order to make the game challenging.

#3	rillig 12:33 Jul 22, 2006

Sorry, I don't know where to find the "official" definition. But do you really think it is challenging to calculate all 57000 solutions by hand? -- I don't. For one or two solutions I can understand the challenge, but up to now, I have only seen sudokus with one unique solution. How many published sudokus with more than one solution have you seen? Has it been documented for these sudokus that the number of solutions is larger than one? Roland

#4	mike 21:34 Jul 22, 2006

It is not hard to generate puzzles with only 1 solution, however such puzzles have a *lot* of exposed cells so they are super-easy to solve. As for the published books I've seen, I'd say most of the ones near the back of the books (the harder puzzles) have at least 1 pair of cells that can be put in 2 different ways.

#5	matt 14:27 Aug 08, 2006

"Fill in the grid so that every row, every column, and every 3x3 box contains the digits 1 through 9. " That's all there is to it. It's fun. It's challenging. It's addictive! http://www.sudoku.com/ (the official website of the re-discoverer of sudoku). ;-)

#6	greg.ercolano 15:04 Aug 08, 2006

> Please provide a reference to official documentation > (not Wikipedia) that defines this restriction. I'm no expert on this, just doing the googling foot work (ie. searching for "sudoku rules") Assuming Matthais' link is authoritative on the subject: http://www.sudoku.com/rule.htm ..it does seem to say: ---- [..] You can't change the digits already provided in the grid. You have to work around them. *Every puzzle has just one correct solution.* ---- Another page seems to echo this: ---- http://www.forbeginners.info/sudoku-puzzles/rules.htm A "good" sudoku puzzle has only one solution. ---- ..which sounds like it at least leaves room for the alternatives, whereas this page seems slightly more opinionated: ---- http://www.angusj.com/sudoku/hints.php There are also some puzzles which have multiple solutions and are generally considered invalid or broken. ---- I know nothing about the puzzle myself, just doing the legwork cause I was curious. This puzzle certainly is 'everywhere' now.. even on the checkout line at the market and liquor stores.

#7	bluekid 10:43 Aug 24, 2006

http://www.answers.com/topic/dancing-links "So far my approach only began to have success when I used an algorithm called Dancing Links (DLX) developed by Donald Knuth, which reformulates Sudoku into a binary matrix of 324 columns, 729 rows, and tries to find 81 rows (including existing clues) for which each of the 324 columns has only a single 1. It's an elegant algorithm and uses backtracking, with which it can tell you if a grid is insoluble or if there are multiple solutions. Using Dancing Links alone I can add a numbe of clues to the puzzle, look for insolubility and remove clues if need be, then add clues as long as there are multiple solutions. Then I shuffle the clues and remove them one by one, replacing them again if the board has multiple solutions as a result. The problem with this approach is that while it gives you a valid sudoku puzzle with a unique solution, most of that time the solution requires messy trial-and-error techniques to solve. At best such boards should be reserved for only the clinically insane--present or future. Today I finally got a human-style solver working using most of the common techniques except trial-and-error ones, and used that as a further guideline. (My first attempt at a human-style solver was a disaster. This one is based more on dancing links.) Now, new clues are added as long as the puzzle is not solvable by those techniques, and then removed at random as long as the result doesn't screw with that constraint. Well now I face an even weirder problem. Rating the resulting puzzles for difficulty and checking out how the human-style solver would solve them, I found that an alarming number of puzzles are solvable with only the dirt-simple naked single and hidden single techniques. In other words, most of these puzzles would be categorized as easy, and some medium at best. Running an Evil level puzzle from websudoku.com through my difficulty rater I found a much higher degree of difficulty than anything my generator typically spits out (and yet, the Evil level turns out to be not so evil after all!). Originally I planned to generate grids en masse and just sort them by difficulty. However it seems more likely now that a better approach will be to tweak the difficulty. I hope to do this by adding a random clue, then removing the other clues at random as per my earlier method. Or I may choose to remove one at a time and only take out the one that increases difficulty the most, and then remove any others that are expendable." http://members.byond.com/LummoxJR?command=view_comments&post=3564

#8	mike 11:12 Aug 24, 2006

Fixed in Subversion repository. The updated Sudoku game now displays a notice when you choose Hard or Impossible puzzles for the first time stating that Hard and Impossible puzzles have multiple possible solutions *on purpose*, because Easy and Normal puzzles are boring. The on-line help has also been updated with a notice for this as well. Any future complaints about the "correctness" of the puzzles generated by the FLTK Sudoku program will be immediately closed without resolution.