Untouchables and Chameleons

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

Postby coloin » Mon Nov 27, 2006 1:37 am

I could not get better than a 3-mutable for a long time - Till I luckily got a 5-mutable....mutable clue is @r9c9

Maybe there is furthur to go
Code: Select all
+---+---+---+
|...|5..|3..|
|1..|6..|.7.|
|83.|..2|.6.|
+---+---+---+
|..7|.1.|.9.|
|6..|.8.|...|
|95.|...|48.|
+---+---+---+
|2..|.69|...|
|.4.|3..|...|
|...|...|..2|
+---+---+---+

Code: Select all
4 sol.         ...5..3..1..6...7.83...2.6...7.1..9.6...8....95....48.2...69....4.3.............1
1 sol.         ...5..3..1..6...7.83...2.6...7.1..9.6...8....95....48.2...69....4.3.............2
1 sol.         ...5..3..1..6...7.83...2.6...7.1..9.6...8....95....48.2...69....4.3.............3
1 sol.         ...5..3..1..6...7.83...2.6...7.1..9.6...8....95....48.2...69....4.3.............4
0 sol.         ...5..3..1..6...7.83...2.6...7.1..9.6...8....95....48.2...69....4.3.............5
1 sol.         ...5..3..1..6...7.83...2.6...7.1..9.6...8....95....48.2...69....4.3.............6
0 sol.         ...5..3..1..6...7.83...2.6...7.1..9.6...8....95....48.2...69....4.3.............7
1 sol.         ...5..3..1..6...7.83...2.6...7.1..9.6...8....95....48.2...69....4.3.............8
5 sol.         ...5..3..1..6...7.83...2.6...7.1..9.6...8....95....48.2...69....4.3.............9

For info - I based my search on one of Gordon's 17s, which has a single clue in an empty row, column, and box. It looks easy to find these high muters but I assure you it was not !.
Code: Select all
+---+---+---+
|...|5..|34.|
|1..|6..|...|
|8..|...|...|
+---+---+---+
|...|.1.|.9.|
|6..|.8.|...|
|.5.|...|4..|
+---+---+---+
|2..|.7.|...|
|.4.|3..|...|
|...|...|..1|
+---+---+---+ One of Gordon Royle's 17-clue puzzles  SE 6.6

To JPF - I think Red Ed is the man to help regarding these grids which are "invarient on transpose" He would also know about the G1-G2 permatations.

I dont know how exceptional your pair of grids are and I dont know how it could help us find mutable clues....

Thinking about the unavoidable sets which have to be solved simultaeously with one clue [position]....it .makes high mutables unlikely...............at least with the above pattern it is potentially possible to achieve a higher than 6-mutable.

C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby gsf » Mon Nov 27, 2006 5:24 am

a partial scan of the 225M catalog found these mutable puzzles
the comment is
# mutable-candidates # mutable-clues # mutable-signature
the first mutable-signature value is the max # mutable candidates for one mutable clue

the search filtered max mutable candidate per clue >= 6 or
# mutable clues >= 20
the search terminated in a machine crash
I restarted the search, this time with stats for mutable candidates that induce non-isomorphic puzzles
that search will take a fews days to complete

.23......4.........8.1....6...56.8..37....4...4........6...8.74....7.29...7..3.5. # 8 # 2 # 6 2
12...67..4.6.8......9...5.......761........2....23....3...1...86......9.9....245. # 10 # 3 # 6 2 2
......789..6.........1325..2..69.....4...32..9.7........89...1.........8.....534. # 12 # 4 # 6 2 2 2
1..4...89.56............5....89...51...362........13....1....6..9..3..748....7.1. # 14 # 4 # 6 4 2 2
.2.4.6.8....7..1....9.2.5....7.3..9...59.7..86......1...1.9....8..3..........56.. # 14 # 5 # 6 2 2 2 2
1..4...89.56............5....89.4.51....62........13....1....6..9..3..748....7.1. # 16 # 5 # 6 4 2 2 2
12.....8......91........645.6.8.....8.59.......7.6..2....6.....5.8.2..1.6...7.3.. # 16 # 6 # 6 2 2 2 2 2
...45....4.....23....2...6.215..7....741..89...............3.....197.4.2.9.....73 # 18 # 6 # 6 3 3 2 2 2
....5...94.67...3.7..1...6.2....4..........9....5....75.432.6...3...827...2...... # 18 # 7 # 6 2 2 2 2 2 2
....5.7..4....9.3.7.92.15...1...4.....7......86....2..53.8....4..2....9.........1 # 20 # 8 # 6 2 2 2 2 2 2 2
..34...89..67.......91..5....4.9...351..2..4..3...........6.27......1...8.....3.6 # 21 # 8 # 6 3 2 2 2 2 2 2
.2....7...567.9.3.7.....5.42..84...6.........94...5..8..19.....6.....4.1....1..5. # 22 # 9 # 6 2 2 2 2 2 2 2 2
.23...7.......912.7.......5..7..8.94.3..14...8..2..6....8.....65..36..1..6..4.... # 23 # 9 # 6 3 2 2 2 2 2 2 2
.234..78...67.9....8.......2..3..5........21...75....45..2....8..1834.......7.6.. # 27 # 10 # 6 3 3 3 2 2 2 2 2 2
...4...89....89..27......6.2...7.....4..1.....7.8.23....2.4..56.....8.9..645..... # 27 # 11 # 6 3 2 2 2 2 2 2 2 2 2
1.....7.9.56..91.....1...6.2.5.4.....7.....53..86....1.....76.....91.4.8.9...4... # 41 # 20 # 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
1......8.4...8..32..9...4...3.84.96......2...6..3....1..46...9.8.......3962..7... # 43 # 20 # 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
...4.......6.8...7..9.3.14.2.......3...71.4..6.5....7..71..38.6.3.5..........2... # 48 # 20 # 4 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2
1...5.......7....3..9..25...15.6...........9..6.3.7.1.5..6...3...48...72.7.2....6 # 47 # 21 # 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
...45.6.94......3...9...15.2..6.....56.8......31..4..2........1675..1....1..2.79. # 47 # 22 # 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Ocean » Mon Nov 27, 2006 5:02 pm

gsf wrote:a partial scan of the 225M catalog found these mutable puzzles
the comment is
# mutable-candidates # mutable-clues # mutable-signature
the first mutable-signature value is the max # mutable candidates for one mutable clue

the search filtered max mutable candidate per clue >= 6 or
# mutable clues >= 20

Thanks for the list, which shows a good diversity: all signatures are different. Did you limit the list to only one puzzle per signature, or did all found puzzles in fact have different signature ?
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby gsf » Mon Nov 27, 2006 5:31 pm

Ocean wrote:Did you limit the list to only one puzzle per signature, or did all found puzzles in fact have different signature ?

good point
first, the posting was limited to minimal puzzles
second, the results were sort uniq'd in the last two # separated fields
66M/225M puzzles were scanned before the machine crash

the scan I'm running now will provide better maxima stats
it will also include the number of non-isomorphic puzzles induced by the mutable clues

estimated run time is 2 weeks for the 225M catalog
canonicalization (for the isomorphism stats) approx doubles the run time
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby JPF » Mon Nov 27, 2006 9:19 pm

gsf wrote:the search filtered max mutable candidate per clue >= 6 or
# mutable clues >= 20

Does it mean that there are no chameleon in your first 66M puzzles ?

This animal would be more rare than a 6 mutable cell ?

JPF
JPF
2017 Supporter
 
Posts: 6123
Joined: 06 December 2005
Location: Paris, France

Postby gsf » Tue Nov 28, 2006 1:57 am

JPF wrote:Does it mean that there are no chameleon in your first 66M puzzles ?

This animal would be more rare than a 6 mutable cell ?

no chameleons, so they seem rare, at least for the generator as it stood ~1 year ago
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Red Ed » Tue Nov 28, 2006 7:20 am

A couple of 7-mutables:
Code: Select all
0000850907000934000697241000034680090805103065060000006010009000000000*0020900800
0070835002501000043094001008000007430000570807000000000000009060003010200*0700000
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby JPF » Tue Nov 28, 2006 4:42 pm

Red Ed wrote:A couple of 7-mutables...
Nice findings !

Red Ed wrote:We normally improve max/min grids of various types incrementally.

Let's go for 8 !

JPF
JPF
2017 Supporter
 
Posts: 6123
Joined: 06 December 2005
Location: Paris, France

Postby coloin » Wed Nov 29, 2006 12:14 am

Red Ed wrote:A couple of 7-mutables

Well done Red Ed...that is some going...I think this is a very hard challenge !.

Do we really think think there will be 8 [or all 9 clues mutable] ?
It is really some coincidence that 7 puzzles have the same 26 or so clues - and are all each solved by an additional different clue in the same position.

The sheer number of puzzles out there makes a 9-mutable a virtual certainty.........

I dont think searching all random [canonized/canicolized] puzzles is going to yield it without a huge search.
I tried to make puzzles with 20 common clues - and I was able to add 3 clues plus the mutable clue at r9c9. That would be all puzzles with at most 24 clues.

The two runs I did generated 7 and 14 5-mutable pseudopuzzles
Code: Select all
47055 puzzles   with 20 common clues any 3 other clues and a clue at r9c9
78101 puzzles   with 21 common clues any 3 other clues and a clue at r9c9

1 24593     35967   
2  9878     28070   
3  2217     12006   
4   332      1988   
5    35 [7]    70 [14]

If the extrapolation is exponential the number of puzzles we would have to look at is enormous.

So I tried a different way, I produced 58405 different minimal puzzles generated from a single random subgrid
Code: Select all
+---+---+---+
|8..|...|...|
|...|273|958|
|...|869|417|
+---+---+---+
|.84|391|562|
|.26|485|379|
|.93|627|184|
+---+---+---+
|.52|918|743|
|.18|742|695|
|.47|536|821|
+---+---+---+

removing the mutable clue[r1c1] - leaving puzzles with more than 1 solution
Code: Select all
02 sol.   251   
03 sol.   360
04 sol.   376
05 sol.   357
06 sol.   400
07 sol.   414
08 sol.   432
09 sol.   458
10 sol.   404
11 sol.   438
12 sol.   479
13 sol.   384
14 sol.   438
15 sol.   391
16 sol.   402
17 sol.   340
18 sol.   467
19 sol.   337
20 sol.   357
90 sol.   156
>99 sol.    33399


Optimistically I searched the 458 9 sols [ our magical 9-mutable will have 9 grid solutions !]

Only one 5-mutable
Code: Select all
0............7.958....6.4.7.8...156..2...5.7..93.......5.9.8......74.........68.1


a better strike rate, but still not even near Red Ed's.

JPF wrote:Does it mean that there are no chameleon in your first 66M puzzles ?


Well - the chameleon puzzles that we know of have 34,35and 36 clues - and I doubt there are many 33 clue puzzles in the collection !

C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby Red Ed » Thu Nov 30, 2006 8:18 pm

JPF wrote:Let's go for 8 !
OK, after much searching ...
Code: Select all
12034056053060000040005072320103080074020000008070060200290008007000021500000*900
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby gsf » Thu Nov 30, 2006 8:51 pm

coloin wrote:
JPF wrote:Does it mean that there are no chameleon in your first 66M puzzles ?


Well - the chameleon puzzles that we know of have 34,35and 36 clues - and I doubt there are many 33 clue puzzles in the collection !

that's right
very few < 20 clues or > 30 clues
the filter is still running

to give an idea of the hit rates
the filter maximizes 5 stats
the output of the solver, on line per puzzle { puzzle #clues stats puzzle-ordinal timestamp }
is piped to a sort with a plugin that keeps track of the
maximum value for each stat for each number of clues and emits the record when any of the 5 stats beats the maximum for its stat

its >10% through (29M puzzles) and only 189 records have been emitted
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Thu Nov 30, 2006 8:52 pm

Red Ed wrote:
JPF wrote:Let's go for 8 !
OK, after much searching ...
Code: Select all
12034056053060000040005072320103080074020000008070060200290008007000021500000*900

neat
do you have a catalog of >30 clues or maybe some generation hints?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Fri Dec 01, 2006 2:29 pm

Well done in finding the 8-mutable.

I am going to presume that it will be 9 times [at least] more difficult to find the 9-mutable !

I guess that you must be adding clues to make the other mutable clue puzzles solve. This might be more difficult for the 9-mutable.

Heres my best so far
Code: Select all
+---+---+---+
|.12|.86|5..|
|.57|..9|6..|
|6..|2..|.4.|
+---+---+---+
|.8.|6.3|.7.|
|.64|.1.|.8.|
|7..|...|...|
+---+---+---+
|.31|...|...|
|9..|.42|...|
|...|...|..*|
+---+---+---+  a 6-mutable ...[27 clues]


No amount of adding clues can improve it.

C
Last edited by coloin on Fri Dec 01, 2006 11:52 pm, edited 2 times in total.
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby coloin » Fri Dec 01, 2006 7:54 pm

Well perhaps I thought it really needed all of the 34 clues - but no it doesnt!

Here are two reductions on Red Ed's 8-mutable needing only 26 clues.....

Code: Select all
....4..6.53.6.....4...5..232.1.3.8..74.2......8.7..6....29...8........15......*9..
....4.5..53.6.....4...5..232.1.3.8..74.2......8.7..6....29...8........15......*9..

Both have 8 solutions, here is one, with the 5 as the mutable clue at r9c6.
Code: Select all
+---+---+---+
|...|.4.|.6.|
|53.|6..|...|
|4..|.5.|.23|
+---+---+---+
|2.1|.3.|8..|
|74.|2..|...|
|.8.|7..|6..|
+---+---+---+
|..2|9..|.8.|
|...|...|.15|
|...|..5|9..|
+---+---+---+  SE 8.4


So perhaps we dont need to search that many [minimal plus 2 clue ] puzzles..........

I still think searching every potential puzzle [with similar clue distribution] which has 9 solutions will be the easiest way !

C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby Red Ed » Sat Dec 02, 2006 7:42 am

It's not surprising that you can reduce the 8-mutable that I posted, as I deliberately put it (and others I have, plus a load of 7-mutables although not the ones first posted) in a form that specifies as many clues as possible, i.e. maximal (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.

For the purposes of chasing highly-mutable cells, I regard two pseudo-puzzles that have the same solution grids as being equivalent. (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.)
Red Ed
 
Posts: 633
Joined: 06 June 2005

PreviousNext

Return to General