## Untouchables and Chameleons

Everything about Sudoku that doesn't fit in one of the other sections
Red Ed wrote:(maximum in fact) rather than the usual minimal form. This seems the most natural way of doing things for pseudo-puzzles, since by leaving only the variable cells exposed you can see how much space is left in the grid for the remaining unclued unavoidables.

Of course that is better........I was only thinking of the way I was searching - It still is possible to get mutable puzzles [to coincide] with 24-26 clue minimal and non minimal puzzles.

How are you doing it ?

Red Ed wrote:For the purposes of chasing highly-mutable cells, I regard two pseudo-puzzles that have the same solution grids as being equivalent.

you mean like these two JPF mentioned from earlier.......Is this a common occurance ?
Code: Select all
`+---+---+---+|1..|.5.|...||...|3..|.6.||..8|...|2..|+---+---+---+|.3.|..2|...||9..|.*.|..5||...|6..|.7.|+---+---+---+|..5|...|1..||.6.|..7|...||...|.9.|..8|+---+---+---++---+---+---+ |123|456|789| |7..|328|.61| |6.8|.7.|2.3| +---+---+---+ |.37|..2|.16| |9.6|7*.|325| |.12|63.|.74| +---+---+---+ |..5|263|1.7| |36.|8.7|..2| |27.|.9.|638| +---+---+---+   * = 1 or 8,equivalent solution grid! `

RedEd wrote:(But if you're considering the mutability of several cells, e.g. looking for chameleons, then of course the maximal form I've been using isn't helpful.)

We found the chameleons in high clue [34] minimal puzzles - because there were so many clues - a few of the puzzles turned out to be chameleons........pure luck......

One could generate millions of minimal 33s and 32s [from the 35s and 34s we have] and possibly there might be a chameleon amonst them....
coloin

Posts: 1864
Joined: 05 May 2005

Red Ed wrote:A couple of 7-mutables:
Code: Select all
`0000850907000934000697241000034680090805103065060000006010009000000000*00209008000070835002501000043094001008000007430000570807000000000000009060003010200*0700000`

~halfway through my 225M and this 26 clue 7-mutable popped out
Code: Select all
`020400000400000037080000105001005308007900000000701064000506800500090000070203000`
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

### Finding a 9-mutable

gsf wrote:~halfway through my 225M and this 26 clue 7-mutable popped out

Very good..........but we are not going to get a 9-mutable that easily......I have reached the limit with my crude searching [non-unix] abilities.

so......letting the brain do the work [rather than the computor]

Here is the mutable clue {11} with 2-digit unavoidables associated with it.
Code: Select all
`{11,12,42,43,71,73,}    {11,17,21,24,34,37,}    {11,15,22,24,42,44,51,55,}{11,16,23,24,73,74,81,86,}{11,18,32,37,42,47,61,68,}{11,19,33,37,73,77,91,99,}`
Here is the subgrid
Code: Select all
`+---+---+---+|12.|.56|489||456|1..|...||.89|4..|1..|+---+---+---+|.12|5..|8..||5..|.1.|...||8..|...|.1.|+---+---+---+|2.1|6..|9..||6..|..1|...||9..|...|..1|+---+---+---+ this has 2x6224 grid completions`

One of which is here
Code: Select all
`+---+---+---+|*..|...|...||...|.89|237||...|.27|.56|+---+---+---+|...|.64|.93||.63|9.8|742||.94|732|6.5|+---+---+---+|.3.|.45|.78||.75|89.|324||.48|273|56.|+---+---+---+  without a clue at {11} it has 19 grid completions`

Code: Select all
`*127356489456189237389427156712564893563918742894732615231645978675891324948273561217356489456189237389427156721564893563918742894732615132645978675891324948273561327156489156489237489327156712564893563918742894732615231645978675891324948273561327456189456189237189327456712564893563918742894732615231645978675891324948273561327456819456189237819327456782564193563918742194732685231645978675891324948273561327456981456189237981327456712564893563918742894732615239645178675891324148273569327516489516489237489327156752164893163958742894732615231645978675891324948273561327651489651489237489327156712564893563918742894732615236145978175896324948273561427356189156489237389127456712564893563918742894732615231645978675891324948273561527316489416589237389427156752164893163958742894732615231645978675891324948273561627351489451689237389427156712564893563918742894732615236145978175896324948273561712356489456189237389427156127564893563918742894732615231645978675891324948273561721356489456189237389427156217564893563918742894732615132645978675891324948273561726351489451689237389427156217564893563918742894732615632145978175896324948273561729356481456189237381427956217564893563918742894732615932645178675891324148273569752316489416589237389427156527164893163958742894732615231645978675891324948273561782356419456189237319427856827564193563918742194732685231645978675891324948273561827356419456189237319427856782564193563918742194732685231645978675891324948273561927356481456189237381427956712564893563918742894732615239645178675891324148273569`

7-mutable !!

Maybe this problem isnt so hard after all ?
I suspect it might still be difficult to get a 9-mutable though.

C
coloin

Posts: 1864
Joined: 05 May 2005

### Re: Finding a 9-mutable

the 225M catalog scan finished the other day
here are the max values for some stats by number of clues
Code: Select all
` A  B  C  D  E  F19  3  3  2  6  320  8  4  3 17  821 11  5  4 25 1422 15  6  5 38 2023 18  6  5 45 2724 21  6  5 48 3025 22  6  5 50 3126 23  7  6 50 3127 22  6  5 51 3128 21  6  5 50 2929 20  6  5 47 2730 16  6  5 36 20A: cluesB: max total mutable cluesC: max mutable candidates per cellD: max mutable candidates per cell leading to unique puzzleE: max total mutable candidatesF: max total mutable candidates leading to unique puzzle`

and here are the representative puzzles, one for each max stat above

000000009000080100700203050048000000010000000000600007300007000001000800060005400 # 19 3 2 1 6 3 33263774 2006-11-30+20:45
000400009056080000080000010000510000000003000900000042070000100010070800000200000 # 19 1 3 2 3 2 164118862 2006-12-11+16:12
000000000400009302080006001207040000000010900000003060310020000000000000090700005 # 20 8 3 2 17 8 185514314 2006-12-13+10:25
020006000400000103000032500000500007300000006940200000500000400000000900017000000 # 20 1 4 3 4 3 7038422 2006-11-28+16:26
000400600050000073089020000294000000000000000000508010300070000002940000000000058 # 21 11 3 2 25 14 147703621 2006-12-10+07:38
023000000400000030000201506090010800000070000501900000070000201800500000000004000 # 21 3 5 4 9 6 38989384 2006-12-01+08:11
000006700400000200080102005060040000005007000001500800030008040000200090807000000 # 22 6 6 5 16 10 46885053 2006-12-01+23:53
100000000050009070000320400200000006000500390000014000000005062047000900090000001 # 22 15 4 3 38 20 143487033 2006-12-09+23:16
000000600400009030700030010200010008000900000034020500005000800000800004090506700 # 23 18 4 3 45 27 120088529 2006-12-08+00:56
020000780050700100080030040001090000000002006004008010017000000000604003000000520 # 23 15 5 4 39 24 43811193 2006-12-01+17:47
023000000400000000080100006000560800370000400040000000060008074000070290007003050 # 23 2 6 5 8 6 4669554 2006-11-28+11:41
000050080450009300700000040038010000601000090000300400000805007000290000002000106 # 24 16 4 3 46 30 197355926 2006-12-14+09:53
003400000006009120780030040000800074090000000000021008300000200010000095002007000 # 24 9 6 5 25 15 2892011 2006-11-28+08:08
100000009400000200000026041030500900608004000000000070070900068500070000090010003 # 24 17 4 3 46 29 93044743 2006-12-05+19:20
100000080000009200780300000000000800300070001065040070040002300000503090002000015 # 24 21 4 3 48 27 86650814 2006-12-05+06:43
000000080400009032089000510060070000390800050000230000035020090000000006002043000 # 25 22 3 2 48 26 212030902 2006-12-15+14:57
000450709006000032080003000200005060000600007900008023300900001010802000000000400 # 25 21 3 2 50 29 29594588 2006-11-30+13:25
003000009056000132080100006200004000030001090900807050001000000500000870000940000 # 25 19 5 4 49 30 15769438 2006-11-29+09:52
020000000456090102000013000237600000000000400010805000002500604500000900090000007 # 25 18 4 3 49 31 52391154 2006-12-02+10:49
023406000400780020000020500004090006008000001930001000000540000001000800060007090 # 25 12 6 5 31 19 1136365 2006-11-28+04:38
000050700456009100000100046008000071500000300967000000300070002041300000800040000 # 26 16 5 4 47 31 3540976 2006-11-28+09:25
000400009000009200780036004204003060000000900500620007605800002002010000000000530 # 26 23 3 2 49 26 126155591 2006-12-08+12:57
020400000400000037080000105001005308007900000000701064000506800500090000070203000 # 26 11 7 6 28 17 96755391 2006-12-06+02:41
120000000056000007000320500005700036300080210010200900000804000800961000070000000 # 26 22 3 2 50 28 222130842 2006-12-16+11:00
000006700000700123080200004200008090600014000000020400002800000560000300001347006 # 27 22 4 3 50 28 10094235 2006-11-28+22:34
000056700056000100000130040240597000030040000900000001000010000502000004800960035 # 27 9 6 5 23 14 3683681 2006-11-28+09:43
003057080050100000700203000204090306000006008000000102500000903608000075030600000 # 27 19 5 4 50 31 81549525 2006-12-04+20:36
020400009006180002080006410000000000671000000090020004300040090060000008900875100 # 27 20 4 3 51 31 184598092 2006-12-13+08:35
000056700056000100000130040240597000030040000900000001000010000502000004807960035 # 28 9 6 5 23 14 3683679 2006-11-28+09:43
100000780050009030700000006204800000018690000005042600000200003000008900032060401 # 28 20 4 3 49 29 12654115 2006-11-29+03:41
100007009050009070780603001200000700060200000090010300010300920800000530004000108 # 28 21 3 2 50 29 159695881 2006-12-11+07:27
000056700056000100000130040240597000030040000900000001000010000502000004807964035 # 29 9 6 5 23 14 3683678 2006-11-28+09:43
000400680000109200089000051010070000000042000070301824500600970600005100031000000 # 29 14 4 3 39 25 65362105 2006-12-03+12:36
100007009050109070780603001200000700060200000090010300010300920800000530004000108 # 29 20 3 2 47 27 159695850 2006-12-11+07:27
041000006000320050900600210100006080006709100080200005097004003060075000500000860 # 30 16 3 2 36 20 27840353 2006-11-30+09:54
200809300004020096070600008003400600050000070009002100600005030390010800008706002 # 30 5 6 5 15 10 220600997 2006-12-16+07:59

the data was collected by a modified sort that maintained the max value per-clue
for the columns B through F and emitted each record that increased any max value
out of 225M records input only 219 were output
those 219 were again sorted in reverse order to produce the 36 representatives above
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Thanks gsf for these data.

I assume that all the 225 M puzzles are minimal and non isomorphic.
Is it the result of randomly generated puzzles or a collection gathered from different sources ?

chameleons :
As coloin pointed out we found chameleons in 34,35,36 clues puzzles, but it's interesting to see that there are 26 clues with 23 mutable cells, almost chameleons (88.5%).

mutable candidates per cell:
No more than 7 !

D - F
Does it mean that the resultant puzzle Mut (P, c->c') is not equivalent to P ?

Did you keep B, C, D, E, F when you did the same screening for the 17s ?

JPF
JPF
2017 Supporter

Posts: 3861
Joined: 06 December 2005
Location: Paris, France

JPF wrote:I assume that all the 225 M puzzles are minimal and non isomorphic.
Is it the result of randomly generated puzzles or a collection gathered from different sources ?

generated and from the forums up to the beginning of 2006
no dups, but many are not minimal
JPF wrote:D - F
Does it mean that the resultant puzzle Mut (P, c->c') is not equivalent to P ?

close: for the total mutable counts each mutable value was applied for each cell and
the resultant puzzles were canonicalized and the number of different puzzles were counted
JPF wrote:Did you keep B, C, D, E, F when you did the same screening for the 17s ?

here are the max results for gordon's 17's

000040610205300000000000800400000072060010000000000000300502000000700100000000000 # 17 7 2 1 14 4 4120 2006-12-19+14:21
060740000500000001000000000000015300020000060000080000000200640100300000800000000 # 17 6 3 2 14 6 20245 2006-12-19+14:25
064000050000300000002000000700000160300200000000400500500010000080000002000060000 # 17 3 4 3 8 4 20463 2006-12-19+14:25
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

JPF wrote:As coloin pointed out we found chameleons in 34,35,36 clues puzzles, but it's interesting to see that there are 26 clues with 23 mutable cells, almost chameleons (88.5%).

Interesting on the 23/26clue - it is an easy puzzle ...is it a low stepper ?

Well, I lied.......I dont think I have a 35 clue chameleon ! I think because we have so few of these puzzles that we havnt just been lucky enough.

I have a few [hundred]more that I will post on the max clues - but I dont think there is a chameleon in these either !

The 34 clue chameleons [over 140] came from the "dukuso15" grid, the 36 clue chameleon came from the "mc" grid [only one]

Code: Select all
`dukuso15 34...........4..1.52.57.43.81.18.57.34..648...7..........91.25.4..7.1.6..8.859...13`
Code: Select all
`mc 36+---+---+---+|..3|..6|78.||..6|78.|12.||78.|12.|45.|+---+---+---+|.31|.64|8..||.64|8..|2..||8..|2..|5..|+---+---+---+|312|645|...||645|...|...||...|...|...|+---+---+---+`

The dukuso15 grid has many 4-set unavoidables, and many 34 clue puzzles......the mc grid had a 36 clue which just forced the issue.

JPF wrote:mutable candidates per cell :No more than 7 !

I have tried hard for the 9-mutable - and given up !

C
Last edited by coloin on Tue Dec 19, 2006 9:21 pm, edited 1 time in total.
coloin

Posts: 1864
Joined: 05 May 2005

coloin wrote:Interesting on the 23/26clue - it is an easy puzzle ...is it a low stepper ?

its in the 225M post, but tiny font
here it is again
Code: Select all
`000400009000009200780036004204003060000000900500620007605800002002010000000000530`

inferior (singles only) 6 steps
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

gsf wrote:
coloin wrote:Interesting on the 23/26clue - it is an easy puzzle ...is it a low stepper ?

its in the 225M post, but tiny font
here it is again

It's got 2 redundant clues (r3c9 and r8c3), each can be removed for two minimal 25-clue puzzles. Unfortunately these do not show the same percentage of mutability, only about half chameleons.

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

here is a puzzle with one 6-mutable cell at [55] with values {123456}, no other mutable cells
Code: Select all
`. . . | . . 8 | 5 . 2. 2 3 | 5 9 1 | . . 8. . 1 | . 7 4 | 9 . .------+-------+------. . . | . . . | 6 . 19 . 8 | . 1 . | 7 . .2 . . | . . 7 | . 3 .------+-------+------. 6 7 | . . 3 | . . .8 . . | 4 . . | . . 7. 9 . | . 8 2 | . 4 .`
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

From a grid [found by Red Ed] here with the maximum number 0f U4s and no U6s
Code: Select all
`+---+---+---+|..3|...|78.||4.7|...|2.6||96.|...|.14|+---+---+---+|29.|7.8|...||3.4|26.|...||.85|.41|...|+---+---+---+|.4.|81.|9.2||...|69.|85.||...|..7|.43|+---+---+---+  a 35 clue chameleon`

There are over 200 35 clue minimals [some with 3 empty boxes] in this region of this grid.

C[/url]
coloin

Posts: 1864
Joined: 05 May 2005

coloin wrote:From a grid [found by Red Ed] here with the maximum number 0f U4s and no U6s
Code: Select all
`+---+---+---+|..3|...|78.||4.7|...|2.6||96.|...|.14|+---+---+---+|29.|7.8|...||3.4|26.|...||.85|.41|...|+---+---+---+|.4.|81.|9.2||...|69.|85.||...|..7|.43|+---+---+---+  a 35 clue chameleon`

Nice ! coloin.

This 35 clues-puzzle is like your 36 clues-mc36.
properties :
- minimal
- Every clue has 2 grid solutions... therefore a chameleon puzzle
- 3-steppers (you should post both to the low-stepper Puzzles thread)
- "Nacked singles" (see here )

JPF
JPF
2017 Supporter

Posts: 3861
Joined: 06 December 2005
Location: Paris, France

### 23 clue chameleon

A 23 clue chameleon puzzle - from the mc grid
Code: Select all
`+---+---+---+ |.2.|...|.8.| |..9|1..|...| |4..|7..|.23| +---+---+---+ |..1|5..|...| |...|.9.|23.| |...|.3.|..4| +---+---+---+ |3..|.45|9..| |..5|...|...| |.78|...|6..| +---+---+---+ All clues mutable.`

Considering the mc grid is distant from a lot of grids I expected there to be more untouchable clues - but the opposite is the case - there seems to be more mutable clues. The puzzle came out of a very small sample - so probably not uncommon.

Conversly here is a 21 clue untouchable [+] puzzle.

Code: Select all
`+---+---+---+ |...|...|...| |12.|3..|8..| |34.|12.|...| +---+---+---+ |...|.6.|..7| |..9|..7|..8| |6..|...|5..| +---+---+---+ |..5|..3|..4| |.1.|...|...| |...|8..|.9.| +---+---+---+ `

There are no mutable clues, in fact there are no puzzles {-1+1} of it. Perhaps this wont be common.

C
coloin

Posts: 1864
Joined: 05 May 2005

I haven't been following closely, so ... what are the current records for chameleons?

(And, quick check, what's the definition? Chameleon <=> each "-1" sub-puzzle has 2 solutions?)
Red Ed

Posts: 633
Joined: 06 June 2005

at the beginning of this thread i wrote:Let P =(C) be a puzzle.
Ck is a cell of P and [Ck] is the given digit for the cell Ck.

A cell Ck is mutable if by replacing [Ck] by [C'k # Ck], all the other cells of the puzzle remaining equal, the new puzzle P' is valid.

A puzzle containing at least one mutable cell is volatile.
A puzzle without mutable cell is untouchable.

A puzzle in which all the cells are mutable is called a Chameleon.

JPF
JPF
2017 Supporter

Posts: 3861
Joined: 06 December 2005
Location: Paris, France

PreviousNext