Update: How many puzzles for same identical solution

Everything about Sudoku that doesn't fit in one of the other sections

Update: How many puzzles for same identical solution

Postby snowbear » Sun Dec 04, 2005 11:59 am

Update: 2005-12-04


Conclusion (So far):

There are at least 2 unique puzzles that can be solved giving the same solution.

Proof:

By providing an example for this. See [II] AN EXAMPLE



[I] APPRECIATION

First, some appreciation notes.

The puzzles (excluding the original puzzle) in this posting has been made possible thru the lessons and experiences learnt from:

http://www.pro.or.jp/~fuji/sudoku/makesudoku/sudoku01.html.en

as well as efforts and time by this 11-members team of dedicated "Sudoku enthusiasts". Also, thank you to our Japanese advisors-cum-team members who highlighted the mistakes made when we were in our baby steps in manually creating our sudoku puzzle.

All the team members have been greatly rewarded with better understanding of the sudoku game as a result.


[II] AN EXAMPLE

Note:
As far as we could determine, the two Puzzle Variation (PV) have only one unique (same) solution and is solvable. Also, to the best of our combined ability, we can't reduce them any further. Please let us now ASAP if otherwise.

This puzzle appear in a local newspaper and is rated 5 (the most difficult)



Original Puzzle

+-------+-------+-------+
| . . . | . 5 . | . 7 2 |
| 4 . . | . . 3 | . . . |
| 8 . . | . . . | . 6 1 |
+-------+-------+-------+
| . . . | . 2 . | 8 . . |
| 3 . . | 8 . 4 | . . 5 |
| . . 7 | . 9 . | . . . |
+-------+-------+-------+
| 1 2 . | . . . | . . 7 |
| . . . | 5 . . | . . 9 |
| 9 4 . | . 7 . | . . . |
+-------+-------+-------+

Solution:

+-------+-------+-------+
| 6 3 1 | 9 5 8 | 4 7 2 |
| 4 7 2 | 1 6 3 | 9 5 8 |
| 8 5 9 | 7 4 2 | 3 6 1 |
+-------+-------+-------+
| 5 1 4 | 3 2 7 | 8 9 6 |
| 3 9 6 | 8 1 4 | 7 2 5 |
| 2 8 7 | 6 9 5 | 1 3 4 |
+-------+-------+-------+
| 1 2 5 | 4 3 9 | 6 8 7 |
| 7 6 3 | 5 8 1 | 2 4 9 |
| 9 4 8 | 2 7 6 | 5 1 3 |
+-------+-------+-------+

After a combined and tedious effort of over 200 failed puzzles whereby each of us handled a different type of variation, we are lucky to discover two working unique puzzles that lead to the same solution as above.




Puzzle Variation 2 (PV2): Not easily solved.
Can be solved, somehow, according to other team members.

+-------+-------+-------+
| 6 . . | . 5 . | . 7 . |
| 4 . 2 | 1 . . | . . . |
| . . . | . 4 . | . . . |
+-------+-------+-------+
| . . . | 3 2 . | . . . |
| . . . | 8 . . | . . . |
| 2 . 7 | . . . | 1 . 4 |
+-------+-------+-------+
| 1 . . | . . . | 6 8 . |
| . . . | . . . | . . 9 |
| 9 . . | 2 7 6 | . . . |
+-------+-------+-------+



Puzzle Variation 1 (PV1) : Easy. I managed to solve this

+-------+-------+-------+
| . . . | . 5 . | . . 2 |
| 4 . 2 | . . 3 | . 5 . |
| . . . | . . . | 3 6 1 |
+-------+-------+-------+
| . 1 . | 3 . . | . . 6 |
| . . . | 8 . . | 7 2 . |
| . . . | . . 5 | . . . |
+-------+-------+-------+
| 1 . 5 | . . . | . . . |
| . 6 . | . . . | . . . |
| . . 8 | 2 7 . | 5 . . |
+-------+-------+-------+

[III] THE NEXT CHALLENGE

Besides polishing up our puzzle creation skills, we would be looking at how to reduce a puzzle to its minimum number of clues and also the puzzles with the minimum number of clues issue.

Thank you for your time.
snowbear
 
Posts: 20
Joined: 27 October 2005

Postby frazer » Sun Dec 04, 2005 2:07 pm

Take any solution grid. We can make a puzzle by choosing any of the 81 squares to be part of the hints, and to make the remaining ones blank. So each square has 2 possibilities, either to leave it as a hint, or to make it blank.

Since this works for every one of the 81 squares, there are 2^81=2417851639229258349412352 possible puzzles which do have the original grid as a solution. The question is: how many of these have the original grid as the ONLY solution.

As dukuso has said, experiments have shown that about 40% are likely to work. This means that each solution grid is likely to have about 1000000000000000000000000 (that's 10^24) corresponding puzzles. (So you have some way to go with your calculations!)
frazer
 
Posts: 46
Joined: 06 June 2005

Postby Pi » Sun Dec 04, 2005 2:13 pm

My generator program works the way that Franzer said, it takes a finished puzzle and removes come numbers and looks to see if it works, if you want i can set it up to make lots of puzzles from one finished sudoku.
Pi
 
Posts: 389
Joined: 27 May 2005

Postby Pi » Sun Dec 04, 2005 2:15 pm

frazer wrote:As dukuso has said, experiments have shown that about 40% are likely to work. This means that each solution grid is likely to have about 1000000000000000000000000 (that's 10^24) corresponding puzzles. (So you have some way to go with your calculations!)


The way my program does it is it randomly generates a number between 0 and 0.8 for each position in the grid. If the number is greater than 0.5 then it leaves the clue number it, if not it is left blank, i find that approximateley 1 in 6 of these puzzles lead by simple logic to a unique solution (i only use logic, not brute force)

However quite a lot of these puzzles are very easy.
Pi
 
Posts: 389
Joined: 27 May 2005


Return to General

cron