Untouchables and Chameleons

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

Postby coloin » Sat Dec 02, 2006 2:39 pm

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: 1637
Joined: 05 May 2005

Postby gsf » Wed Dec 06, 2006 5:23 pm

Red Ed wrote:A couple of 7-mutables:
Code: Select all
0000850907000934000697241000034680090805103065060000006010009000000000*0020900800
0070835002501000043094001008000007430000570807000000000000009060003010200*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

Postby coloin » Thu Dec 07, 2006 12:07 am

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
*
127356489456189237389427156712564893563918742894732615231645978675891324948273561
217356489456189237389427156721564893563918742894732615132645978675891324948273561
327156489156489237489327156712564893563918742894732615231645978675891324948273561
327456189456189237189327456712564893563918742894732615231645978675891324948273561
327456819456189237819327456782564193563918742194732685231645978675891324948273561
327456981456189237981327456712564893563918742894732615239645178675891324148273569
327516489516489237489327156752164893163958742894732615231645978675891324948273561
327651489651489237489327156712564893563918742894732615236145978175896324948273561
427356189156489237389127456712564893563918742894732615231645978675891324948273561
527316489416589237389427156752164893163958742894732615231645978675891324948273561
627351489451689237389427156712564893563918742894732615236145978175896324948273561
712356489456189237389427156127564893563918742894732615231645978675891324948273561
721356489456189237389427156217564893563918742894732615132645978675891324948273561
726351489451689237389427156217564893563918742894732615632145978175896324948273561
729356481456189237381427956217564893563918742894732615932645178675891324148273569
752316489416589237389427156527164893163958742894732615231645978675891324948273561
782356419456189237319427856827564193563918742194732685231645978675891324948273561
827356419456189237319427856782564193563918742194732685231645978675891324948273561
927356481456189237381427956712564893563918742894732615239645178675891324148273569


7-mutable !!:D

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

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Re: Finding a 9-mutable

Postby gsf » Tue Dec 19, 2006 5:31 am

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  F
19  3  3  2  6  3
20  8  4  3 17  8
21 11  5  4 25 14
22 15  6  5 38 20
23 18  6  5 45 27
24 21  6  5 48 30
25 22  6  5 50 31
26 23  7  6 50 31
27 22  6  5 51 31
28 21  6  5 50 29
29 20  6  5 47 27
30 16  6  5 36 20

A: clues
B: max total mutable clues
C: max mutable candidates per cell
D: max mutable candidates per cell leading to unique puzzle
E: max total mutable candidates
F: 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

Postby JPF » Tue Dec 19, 2006 6:55 pm

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 :
no chameleons in your catalog.
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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby gsf » Tue Dec 19, 2006 8:38 pm

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

Postby coloin » Tue Dec 19, 2006 9:27 pm

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: 1637
Joined: 05 May 2005

Postby gsf » Tue Dec 19, 2006 11:28 pm

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

Postby RW » Tue Dec 19, 2006 11:59 pm

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

Postby gsf » Wed Dec 20, 2006 8:10 am

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 . 1
9 . 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

Postby coloin » Fri Dec 29, 2006 10:43 pm

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: 1637
Joined: 05 May 2005

Postby JPF » Sat Dec 30, 2006 9:42 pm

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: 3752
Joined: 06 December 2005
Location: Paris, France

23 clue chameleon

Postby coloin » Wed Nov 05, 2008 12:08 pm

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: 1637
Joined: 05 May 2005

Postby Red Ed » Thu Nov 06, 2008 11:35 am

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

Postby JPF » Thu Nov 06, 2008 12:43 pm

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: 3752
Joined: 06 December 2005
Location: Paris, France

PreviousNext

Return to General