I am surprised that in most puzzles changing one clue in an appropriate cell (and only in this cell) gives a new valid puzzle.
Furthermore, in some cases the nature of the puzzle changes dramatically.
By "nature", I mean the way of solving it, its difficulty, its rating, etc...
As far as I'm concerned, the best example I know is Gurth's G910:
- Code: Select all
. 4 2 | . . 9 | 1 . .
. 1 . | . 8 . | . 3 .
5 . . | 1 . . | . . 4
-------+-------+-------
6 . . | . . . | . . .
. 9 . | . . 5 | . 7 .
. . 7 | . . . | . . 8
-------+-------+-------
4 . . | . . 1 | . . 6
. 3 . | . 6 . | . . .
. . . | 7 . . | 2 4 .
rated 8.9 by Sudoku Explainer solved by a bunch of chains...
Try the same puzzle with r3c4=6 and you get an easy singles-only puzzle (11 stepper).
In a sense, the puzzle is not stable.
But some puzzles don't have this problem.
For those "untouchable" puzzles, you can't find a cell such that by modifying it only, you get a valid puzzle.
Here is one :
- Code: Select all
. . 7 | . . . | . . 2
. 1 . | . 5 4 | . . .
4 . . | . 6 2 | 8 . .
-------+-------+-------
7 . . | . . . | 1 . .
. . 6 | . 3 . | . 4 .
2 . . | 5 . . | . . .
-------+-------+-------
. 8 . | . . . | . . .
. . 9 | . . 7 | 6 . 8
. . . | 8 . 5 | . . .
Here are more examples :
- Code: Select all
001000000000000579860090002000000740009000008200007000450980000030700000000420300
000000040800050000600300008056080020709600500000030004008006072400000006001005000
090000705070860000100500090003000000006000000200048900040300809000000400001400026
007000002050900076000300000000530000630090000100070080000000004310600000024000309
020600100050080040000007000009001050002700090000850200001030060030020000000406003
000004070080700906003000000000002000097000020500000003008100700002009050039840010
000500000030900200200004706000641320000000000900030001005096000004800000827000000
000400200006000007091000300085037000060000004007000090009600400050000901000700056
gsf wrote:what is the 95% relative to?
I generated randomly 1000 minimal puzzles. I got 33 untouchables (3.3%)
I did it again but with 10000 minimal puzzles ; I had 339 unt. (3.4%)
So, my guess is that the average number of minimal untouchables in a random* sample of minimal puzzles is 3 %+, say 5%.
May be gsf could work this percentage out with a large sample of minimal puzzles ?
Red Ed wrote:"Untouchables" might be rare in the grand scheme of things, but there are lots of examples amongst Gordon's list of 17-clue puzzles. (It seems obvious that low-clue puzzles should be more likely to be untouchable.)
sure. The % for the Gordon's list would be interesting to know.
Generalization
If a puzzle is untouchable at the level 1 (changing 1 cell at a time), we can continue the test at the level 2 :
are there 2 cells (Ci,Cj) such that by changing their numbers (Ci->C'i ; Cj->C'j) we get a valid puzzle ?
If not, we have an untouchable level 2.
And so on, if necessary : level 3,4,....
In any case, the level is limited by the number of clues of the puzzle (cyclic permutation of the digits).
Any takers to produce untouchables level 2 or more ?
(the Gordon's list could be appropriate)
What are their properties ?
Chameleons
At the opposite, some puzzles can easily accept to change lots of their clues and remain valid.
We had a good example of that, given by coloin in the Megaclue thread.
In this minimal 34 clues-puzzle :
- Code: Select all
1 . . | . . . | 7 . 9
. 5 . | . 8 9 | 3 2 .
6 . . | 3 . . | . 5 .
-------+-------+-------
2 . 1 | . . 5 | . . .
. . . | 8 9 . | . 3 .
8 . . | 7 3 2 | 5 . .
-------+-------+-------
. 1 . | 2 . 4 | 9 . 5
. 7 4 | 9 1 . | . . .
. . 2 | . . 3 | 4 . .
27 cells can be changed (1 at a time) and still leave the puzzle valid.
Here are the numbers of possible changes for each clue :
- Code: Select all
1,0,0,1,1,1,1,1,2,1,2,1,0,0,1,1,2,1,1,2,1,1,0,1,1,0,2,0,1,1,1,1,1,1
Only 7 faithful cells !
Is there a minimal puzzle (chameleon) which doesn't have any faithful cell ?
JPF
* what does that mean exactly ?