The New Sudoku Players' Forum

[snowbear]

If we have one solution, ie, all the numbers are filled up,
how many puzzles can we create that will lead us to the same solution?

[A] One (ie one unique solution can only have one unique puzzle)
[B] More than one

Any input?

[ChrisT]

Definitely [B]. If you imagine a valid puzzle with, say, 25 set candidates, as you solve the puzzle, the numbers that you place in empty cells could just as easily have been part of the original starting configuration. In fact, a number can be placed in any of the empty cells as long as it corresponds to the number required for the final solution, even if at that stage of solving the identity of that cell could not possibly be known. And this can of course be done with more than one cell.

It might be more interesting to consider what one might call "minimal puzzles", in which none of the cells are reduntant, i.e. removal of any one of the starting numbers from the grid would result in multiple solutions. This would rule out multiple puzzles generated in the manner described above. In this case, are there multiple "minimal puzzles" that give the same, unique, solution? My instinct would again be that yes, there are probably a large number of possibilities, but I'm not sure that I could produce a logical proof (except by spending hours coming up with a pair of examples).

Chris

[snowbear]

Background of this question:

[Stage 1]
I was learning how to manually create a puzzle at

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

From the creation method it seems that for the fixed number of blanks with one particular starting number, there seems to be only one solution.

[Stage 2]
I tried to use use the LA Times 2005-11-26 puzzle as a test puzzle

http://games.latimes.com/index_sudoku.html?uc_feature_code=lasud&uc_full_date=20051126

Puzzle:

709 100 000
080 002 000
013 006 040

000 030 198
400 000 003
836 010 000

060 800 710
000 400 050
000 009 406


I use a program to validate this puzzle.

It indicated that this puzzle is valid with one unique solution.
I then solve the puzzle.

Solution:
749 183 265
685 742 931 = B1 B2 B3
213 596 847

527 634 198
491 258 673 = B4 B5 B6
836 917 524

364 825 719
978 461 352 = B7 B8 B9
152 379 486


Note:
Boxes that need to fill in 1's: B3, B4, B7, B8


*********************
Using the original puzzle as a base,

TEST 1 - B3
I remove r1c4=1, put r2c9=1,
the program indicated that this puzzle has more than one solution.

TEST 2 - B4
I remove r1c4=1, put r5c3=1,
the program indicated that this puzzle has more than one solution.

TEST 3 - B7
I remove r1c4=1, put r9c1=1,
the program indicated that this puzzle has more than one solution.

TEST 4 - B8
I remove r1c4=1, put r8c6=1,
the program indicated that this puzzle has more than one solution.

This leads me to think that for each unique solution, there can only be one unique puzzle.

Thanks for mentioning the minimum set of clues for a valid puzzle issue. I didn't take note earlier. Will update on this later.

Hence for this part, not conclusive yet.

[Stage 3]
I checked around the forum and there were some discussion on the maximum number of puzzles for a 9X9 sudoku, and it is a very huge number.

This leads me to think that for each unique solution, there can only be one unique puzzle. Hence the huge numbers.

Not verifiable at the moment.

[gfroyle]

The URL

http://www.csse.uwa.edu.au/~gordon/sudokupat.php?cn=3

gives a list of 29 17-clue puzzles, each with the same solution.

[frazer]

Take any puzzle with a unique solution and solve it. The original puzzle together with any other squares you've found in the solution gives a new puzzle with the same solution grid. Starting with, say, a 28-clue puzzle (as I think yours was), you can include any of the remaining 53 clues in the solution grid -- you get a puzzle with the same unique solution. This gives 2^53 puzzles with the same solution. This was what ChrisT remarked; he also pointed out that minimal puzzles would be more interesting to count. I'd be astonished if there were any solution grids that had a unique minimal puzzle.

Similarly, take any solution grid, and just omit one clue -- it is clear that we have 81 different 80-clue puzzles with the same answer. This is just an easier version of Gordon's much more interesting example.

In fact, take any solution grid, and any subset of the original 81 clues (there are 2^81 subsets); my guess (based on almost no evidence!) is that maybe up to a half of these subsets will have the given solution grid as the unique solution. I'd be surprised if it were less than, say, a tenth, although my intuition may be letting me down here (it should be easy to perform tests on this, and maybe has already been done elsewhere on the forum).

[dukuso]

AFAIR we had roughly estimated 1e17 minimal sudokus per grid.

It's easy to see that there are at least two for any grid:
Just take one minimal sudoku over the grid, choose a clue not in that
one and remove it. Then minimize the remaining 80-clues-sudoku.

The maximum known size of a minimal sudoku is 32 AFAIK


I just tested 1000 random subpuzzles over 1000 random grids
and found about 40% of them with unique solution.

[snowbear]

I tried the website and puzzle supplied by {gfroyle} above.

The program I use to validate indicated that "Not enough numbers entered for a vaild puzzle" although the puzzles did all gave the same solution.

How do we know if a puzzle is valid?

[gfroyle]

The program I use to validate indicated that "Not enough numbers entered for a vaild puzzle" although the puzzles did all gave the same solution.

How do we know if a puzzle is valid?

I call a puzzle "valid" if it has exactly one completion. I wrote a program to count all the ways to complete a puzzle - there are literally hundreds, if not thousands of free and/or commercial programs for this, but it is easy enough to write.

If a program says "not enough numbers" then the programmer has specified an arbitrary limit, which is probably just to make sure their program doesn't take too long to finish. If he was my student (I teach Computer Science) he would get docked a grade or even two for doing that.

Some others may define valid in a more restricted way to mean "unique solution AND solvable without trial and error" which is problematic because then you have to specify exactly what you mean by trial and error, and no two people agree.

Cheers

Gordon

[snowbear]

Progress so far:

Based on
- ChrisT's input on "minimal puzzle"
- sample of 17-clues puzzles collection provided by gfroyle
- further inputs by frazer
- programming help & ideas from dukuso

and the LA Times 2005-11-26 puzzle as a test puzzle

709 100 000
080 002 000
013 006 040

000 030 198
400 000 003
836 010 000

060 800 710
000 400 050
000 009 406

with this solution

749 183 265
685 742 931
213 596 847

527 634 198
491 258 673
836 917 524

364 825 719
978 461 352
152 379 486

At the moment, we have managed to reduce the puzzle to the
Minimal Puzzle M1:

709 100 000
080 002 000
010 006 000

000 000 198
400 000 003
036 000 000

060 800 710
000 400 050
000 009 406

and the following Alternative Puzzle 1 (AP1) where 1 more clue is added to M1 and still give the same solution.
(ref Minimal Puzzle M1)

[AP1-1-r3c3=3]

709 100 000
080 002 000
013 006 000

000 000 198
400 000 003
036 000 000

060 800 710
000 400 050
000 009 406


[AP1-2-r3c8=4]
709 100 000
080 002 000
010 006 040

000 000 198
400 000 003
036 000 000

060 800 710
000 400 050
000 009 406


[AP1-3-r6c1=8]

709 100 000
080 002 000
010 006 000

000 000 198
400 000 003
836 000 000

060 800 710
000 400 050
000 009 406


[AP1-4-r4c5=3]

709 100 000
080 002 000
010 006 000

000 030 198
400 000 003
036 000 000

060 800 710
000 400 050
000 009 406

[AP1-5-r6c5=1]

709 100 000
080 002 000
010 006 000

000 000 198
400 000 003
036 010 000

060 800 710
000 400 050
000 009 406

AP2 puzzles would not be considered for now.

All these puzzles should give you the same solution.

Due to time constraints, I will only be able to manually confirm next weekend that:

- all the AP1 puzzles have the same solution
- all the AP1 puzzles have no multiple solutions
ie all the AP1 puzzles have only one and the same solution
- which basic or advanced techniques is needed to solve each of the AP1 puzzles
- whether M1 could be reduced even further

Thanks

[snowbear]

[HELP WANTED]

For those who have some spare time to help to solve:
you can post as follows:

For example,

Puzzle: [AP1-5-r6c5=1]
Number of solution: 1 or multiple
Same solution as M1: Yes or No
Methods used to solve:
-
-
-
......
(Note:
- Preferably with simple & basic techniques unless no choice
- Just the methods used without details
- This ref for naming solving methods has been suggested
http://angusj.com/sudoku/hints.php )

***
The methods used may help us to understand if an additional clue added to a ref puzzle will change the methods used to solve it (make it harder or simplier) even if they have the same solution.

This may even give us some idea on
- whether sudoku with more clues are tougher/easier than those with less clues.
- how to identify hard sudoku puzzles
***

Thanks