Untouchables and Chameleons

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

Untouchables and Chameleons

Postby JPF » Tue Oct 03, 2006 10:11 pm

Untouchables

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 ?
JPF
2017 Supporter
 
Posts: 6139
Joined: 06 December 2005
Location: Paris, France

Postby tarek » Wed Oct 04, 2006 4:54 pm

The untouchable of level=Number of clues should be rare.....where no ismorphic valid pattern exists:!:

This is nice becuase you can claim the puzzle to be yours as no body else will have anything SIMILAR........

tarek
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby RW » Wed Oct 04, 2006 8:38 pm

JPF wrote:Any takers to produce untouchables level 2 or more ?
(the Gordon's list could be appropriate)

There's several puzzles in Gordons list that have an unique pattern, therefore you could say that they are untouchable of level 17. Unless you consider swapping all instances of two different digits as a legal way to produce a new puzzle, in which case you could find untouchables of max level 2 among the 17s, and these only among the puzzles with the different digits appearing {2,2,2,2,2,2,2,2,1}. Can't find the thread now were these puzzles were listed, If I recall correctly there wasn't that many of them.

You used a couple of level 17s to solve a riddle here a while ago:

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

and

 . . . | 3 . . | 4 . .
 8 . . | 5 . . | . . .
 7 . 6 | . . . | . . .
-------+-------+-------
 . 3 . | . . . | 1 . .
 . . . | . 6 . | . . .
 . . . | . . 8 | . . .
-------+-------+-------
 . . . | 1 5 . | . 7 .
 . . . | . . . | 2 . 9
 . . . | . . . | . 8 6


RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby coloin » Wed Oct 04, 2006 9:19 pm

Nick70 found 851 puzzles with this pattern of clues - so scope for searching here !

Code: Select all
+---+---+---+
|1..|.5.|...|
|...|1..|.3.|
|..7|...|6..|
+---+---+---+
|.5.|..8|...|
|9..|.2.|..1|
|...|3..|.6.|
+---+---+---+
|..6|...|8..|
|.3.|..7|...|
|...|.9.|..5|
+---+---+---+ apparently this is the hardest [?]


All printed Complete Suduko Collection - Volume 1

Red Ed is right when he said you would logiclly expect the 17s to be untouchable....in that a substituted clue might fit but would be unlikely to completely solve the grid.

Definition and wording.....

suggest a grid which is"not untouchable" = volatile
clues that can be changed to give a valid grid = mutable clues


..........but.........

From the thead above there is another collection of 34 17 clue puzzles of this pattern - here are two of them
Code: Select all
1.2.3...........5.3.........6.7.8.........1.9...5.........1.2...5.....8.4..6.....
1.2.3...........5.3.........6.7.8.........1.9...5.........1.2...5.....7.4..6.....

So here is an example of a 17 which is volatile, the mutable clue is the 7 or 8 at r8c8, without any clue at this position there are amazingly 3561 grid completions !

Here is the full series of 34 - of note all the puzzles are non-isomorphic [relabeled] and all the solution grids are different.
Code: Select all
1.2.3...........6.4.........7.8.6.........1.4...5.........1.2...6.....8.5..3.....
1.2.3...........6.4.........7.6.8.........1.4...9.........1.2...6.....8.5..3.....
1.2.3...........6.4.........7.6.8.........2.1...9.........1.3...6.....8.5..2.....
1.2.3...........6.4.........7.6.8.........2.4...7.........2.1...6.....8.5..9.....
1.2.3...........6.4.........7.6.8.........2.3...7.........1.3...6.....8.5..9.....
1.2.3...........6.4.........7.6.8.........1.4...7.........1.2...6.....8.5..9.....
1.2.3...........6.4.........7.6.8.........5.2...7.........2.1...6.....8.5..3.....
1.2.3...........6.4.........7.6.8.........2.5...7.........2.1...6.....8.5..3.....
1.2.3...........6.4.........7.6.8.........2.4...7.........2.1...6.....8.5..3.....
1.2.3...........6.4.........5.6.7.........9.2...3.........2.1...6.....7.5..8.....
1.2.3...........6.4.........3.7.6.........4.1...8.........1.2...6.....8.5..9.....
1.2.3...........6.4.........3.7.6.........4.1...8.........1.2...6.....7.5..9.....
1.2.3...........6.4.........3.6.7.........4.1...8.........1.2...6.....7.5..9.....
1.2.3...........6.4.........3.6.7.........5.1...3.........1.2...6.....7.5..8.....
1.2.3...........6.4.........3.6.7.........4.1...3.........1.2...6.....7.5..8.....
1.2.3...........6.4.........3.6.7.........1.5...3.........1.2...6.....7.5..8.....
1.2.3...........5.4.........6.7.8.........4.9...5.........4.2...5.....8.3..6.....
1.2.3...........5.4.........6.7.8.........9.4...5.........4.2...5.....7.3..6.....
1.2.3...........5.4.........6.7.5.........1.4...1.........1.2...5.....7.3..8.....
1.2.3...........5.4.........6.5.7.........6.4...8.........4.2...5.....7.3..9.....
1.2.3...........5.4.........6.5.7.........9.4...8.........4.2...5.....8.3..6.....
1.2.3...........5.4.........6.5.7.........4.9...8.........4.2...5.....8.3..6.....
1.2.3...........5.4.........6.5.7.........9.1...8.........1.2...5.....8.3..6.....
1.2.3...........5.4.........6.5.7.........4.9...6.........4.1...5.....7.3..8.....
1.2.3...........5.4.........6.5.7.........4.2...6.........2.1...5.....7.3..8.....
1.2.3...........5.4.........6.5.7.........2.4...6.........2.1...5.....7.3..8.....
1.2.3...........5.4.........6.5.7.........1.2...6.........1.8...5.....7.3..2.....
1.2.3...........5.4.........6.2.7.........8.4...5.........4.1...5.....7.3..6.....
1.2.3...........5.4.........6.2.7.........4.8...5.........4.1...5.....7.3..6.....
1.2.3...........5.3.........6.7.8.........1.9...5.........1.2...5.....8.4..6.....
1.2.3...........5.3.........6.7.8.........9.1...5.........1.2...5.....7.4..6.....
1.2.3...........5.3.........6.7.8.........1.9...5.........1.2...5.....7.4..6.....
1.2.3...........5.3.........6.7.5.........1.9...8.........1.2...5.....8.4..6.....
1.2.3...........5.3.........6.5.7.........9.1...8.........1.2...5.....8.4..6.....

im not sure what these differing clues really mean......................apart from many of the clues are going to be mutable - to a relabelled isomorph of one of the other puzzles.....although I doubt there will be a grid where all the clues are mutable clues.......this would be a chameleon puzzle.........ah

I agree a chameleon puzzzle is by definition minimal

All valid 17 clue puzzles are minimal too !

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

Postby JPF » Mon Oct 09, 2006 11:54 am

Maybe the definitions I gave was not clear enough.
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.

Roughly 95% of the minimal puzzles are volatile (what Red Ed called "the grand sheme of things").
Of course this proportion might be different when considering a specific class of puzzles.
In the Gordon's list for instance, this % is around 60 %. (I made a calculation on 1000 randomly picked puzzles).
Here's the most volatile puzzle I found in this sample (5 mutable clues)
Code: Select all
 . . . | . . . | . 8 1
 . 3 . | 5 . . | . . .
 . . . | . 2 . | . . .
-------+-------+-------
 1 . . | . . 7 | . . .
 . . . | . 8 . | 5 . .
 . 5 . | . . . | 4 . .
-------+-------+-------
 6 . . | 1 . . | . 7 .
 . . . | 4 . 3 | . . .
 8 . . | . . . | . . .

Mutable clues : 0,1,0,0,1,0,1,0,0,0,0,1,0,1,0,0,0

I presume (I haven't ckeck) that each "mutation" of a volatile 17-clues puzzle is (or has an equivalent) in the Gordon's list.
It's how I understood the work done by Gordon.

As a by-product of the exercice, I found these 16 clues puzzles with low number of solutions from puzzles N°16555 & N° 19869
#2 solutions :
Code: Select all
030025000000000710060000000000060005700000600100400000400000000050000002000100000
060053000000000801020000000000020030800000200100700000030000050700000000000100000
which are equivalent.

#4 solutions : (from 4434 ; 15105 ; 19505 )
Code: Select all
000050028031000000000000000000304700800000040000100000200080000040000300000600000
020000060000030400700000000090602000000000301000000000304050000000400020100000000
060000035000201000000000000000050080208000700100000000000800200050030000400000000
probably equivalent (I haven't check...)

For such puzzles see here .

There is no obvious connexion between volatility and difficulty.
For example, the 2 hardest puzzles (tarek and Ocean):
* 292: Tarek #1/1 (9.9)
Code: Select all
600001900080030000001700002002000007050000010400000300300009600000040080008200005
has 3 mutable cells.

The SE rating varies accordingly (initial = 9.9)
Code: Select all
D3=5   8.6
G7=4   9.4
C9=7   8.3

but
* 201: Ocean #1/M21/D21
Code: Select all
000001002010020030400500000004000006070030010800000900500008000000010070006400500
is an Untouchable.

Chameleon
Here's a Chameleon found in the list of minimal 34s given to me by coloin (thanks:) ) based on dukuso15 :
Code: Select all
 . . . | . . . | . . .
 . . 4 | . . 1 | . 5 2
 . 5 7 | . 4 3 | . 8 1
-------+-------+-------
 . 1 8 | . 5 7 | . 3 4
 . 3 . | . 8 9 | . . 7
 . . . | . . . | . . .
-------+-------+-------
 . . 1 | . 2 5 | . 4 .
 . 7 2 | 1 . 6 | 5 . .
 . 8 5 | 9 . . | . 1 3

Mutable clues :1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
In this puzzle, each digit can be replaced by one (and only one) other digit.

In the list of 34s given by coloin, I found 144 chameleons !
23 of them are such that each cell can have 2 digits (1,1,...,1,1)

Untouchables level 2 or more
I will come back on this subject in a next post.

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

Postby ravel » Mon Oct 09, 2006 2:20 pm

JPF wrote:There is no obvious connexion between volatility and difficulty.
For example ...
* 292: Tarek #1/1 (9.9)
Code: Select all
600001900080030000001700002002000007050000010400000300300009600000040080008200005
has 3 mutable cells.

The SE rating varies accordingly (initial = 9.9)
Code: Select all
D3=5   8.6
G7=4   9.4
C9=7   8.3
Also my ratings differ very much: 20, 3,9 and 3 steps. So the ways to get to a solution obviously differ very much in this case (not in others) - and i should take version 3 into my hardest list.

Congratulations for finding the chameleons.
ravel
 
Posts: 998
Joined: 21 February 2006

re: 19-clue puzzles with a given pattern - Nick70's 851

Postby Pat » Tue Oct 10, 2006 9:24 am

[ off-topic ] re: 19-clue puzzles with a given pattern - Nick70's 851

coloin (2006.Oct.4) wrote:Nick70 found 851 puzzles with this pattern of clues - so scope for searching here !


Code: Select all
+---+---+---+
|1..|.5.|...|
|...|1..|.3.|
|..7|...|6..|
+---+---+---+
|.5.|..8|...|
|9..|.2.|..1|
|...|3..|.6.|
+---+---+---+
|..6|...|8..|
|.3.|..7|...|
|...|.9.|..5|
+---+---+---+
apparently this is the hardest [?]

certainly not the hardest - Nick70's list starts with the easiest puzzles - the 7 which he solved by "forcing tree" are at the end of his list -
Code: Select all
1...5.......2...3...7...2...3...8...5...1...4...3...5...8...9...4...1.......4...2
1...5.......2...3...7...4...9...3...7...4...8...6...5...8...5...3...4.......1...7
1...5.......2...3...6...4...7...9...4...1...5...3...9...2...1...3...7.......6...4
1...5.......2...3...4...6...9...3...6...7...5...1...7...1...2...3...9.......6...1
1...5.......2...3...6...1...9...4...8...6...5...3...7...7...8...3...9.......1...6
1...5.......1...6...9...3...6...3...4...2...5...7...2...7...8...3...2.......4...1
1...5.......3...6...8...2...3...2...9...1...5...6...7...5...1...6...7.......9...8
User avatar
Pat
 
Posts: 4056
Joined: 18 July 2005

Postby coloin » Tue Oct 10, 2006 10:57 am

Thanks for that correction Pat, I assumed the hard ones were first.

Congratulations to JPF on finding all the Chameleons in the [large] set of minimal 34s in the Dukuso15 grid.

I think we need to add that the number of solutions following successive removal of a single clues is...
Code: Select all
2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol,2 sol.


I presume they all represent 4-clue unavoidable sets. [2-digit unavoidable]

The grid was picked by dukuso as having a large number of 4-clue unavoidable sets. [mcn15] .

I searched it for 35s without success a while back.......but I just kept getting 34s,[over 3000 !]
The number of unavoidables must prevent a 35 - I dont know. There may be a 35 somewhere - but I dont know which 34 to look around !
There are some of the 34s which have significantly more grid solutions per clue [> 2 sol.].....but this just revealed more 34s !

Removing a clue e.g the 7 in r2c8 gives 2 solution grids, each of the solutions can be completed with 4 clues...only one [the 7 in r2c8 is minimal]

Code: Select all
...........4..1.52.57.43.81.18.57.34.3..89..74..........1.25.4...21.65...859...13
...........4..1.52.57.43.81.18.57.34.3..89..7.7.........1.25.4...21.65...859...13
...........4..1.52.57.43.81.18.57.34.3..89..7...........1.25.4.7.21.65...859...13
...........4..1.52.57.43.81.18.57.34.3..89..7...........1.25.4..421.65...859...13
...........4..1.52.57.43.81.18.57.34.3..89..77..........1.25.4...21.65...859...13
...........4..1.52.57.43.81.18.57.34.3..89..7.4.........1.25.4...21.65...859...13
...........4..1.52.57.43.81.18.57.34.3..89..7...........1.25.4.4.21.65...859...13
...........4..1.52.57.43.81.18.57.34.3..89..7...........1.25.4..721.65...859...13

average number of clues in these subgrids, using dukuso's suexsfl.exe
0 0 0 0 0 0 0  30.000000
0 0 0 0 0 0 0  29.000000
0 0 0 0 0 0 0  30.441999
0 0 0 0 0 0 0  30.448000
0 0 0 0 0 0 0  31.000000
0 0 0 0 0 0 0  33.000000
0 0 0 0 0 0 0  33.000000
0 0 0 0 0 0 0  34.000000  the 7 ar r8c2

http://magictour.free.fr/suexsfl.exe

Regarding the set of 17s with a set pattern - it was confirmed that there were only 34 [non-isomorphic] of this pattern.

The grids with #2 solutions would be SF related subgrids [with 29 17s]

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

Postby ronk » Tue Oct 10, 2006 11:01 am

coloin wrote:Definition and wording.....

suggest a grid which is"not untouchable" = volatile

Hmm! That seems backwards to me, as in nitro-glycerin is volatile and therefore untouchable. Or a house of cards is volatile (fragile) and not touchable.

coloin wrote:clues that can be changed to give a valid grid = mutable clues

So why not mutable (puzzle) instead of volatile?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby coloin » Tue Oct 10, 2006 11:09 am

Mutable is good, Volatile was chosen to reflect "unstable" and to change into another form [as in liquid into a vapour]. I didnt want to use the same word for clues and puzzles......as in the use of the word "solutions" to refer to grid solutions and clue completions[solutions]

I think Nitrogyerine is chemically unstable - not really volatile - it does smell I think - so it must be a bit volatile !
Its not so untouchable - only when you hit it with a hammer !

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

Postby ronk » Tue Oct 10, 2006 12:43 pm

coloin wrote:Volatile was chosen to reflect "unstable" and to change into another form [as in liquid into a vapour].

I agree that volatility reflects instability, but the analogous state change in Sudoku is from a valid puzzle to an invalid one. That always happens when touching an untouchable ... making it the volatile puzzle IMO.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby JPF » Tue Oct 10, 2006 8:59 pm

coloin wrote:Nick70 found 851 puzzles with this pattern of clues - so scope for searching here !
All printed Complete Suduko Collection - Volume 1

I have checked the Nick70’s list.
25% Untouchables, 75% Volatiles
The most volatile puzzles (10 puzzles) have 5 mutable clues.

One [ off-topic ] question :
Here are the 10 puzzles with the highest suex rate.
ER is the S. Explainer rating and N the puzzle number in Nick70's list.
Code: Select all

suex   ER   N     Puzzles

172   8,8   847   1...5.......2...3...6...4...7...9...4...1...5...3...9...2...1...3...7.......6...4
198   7,1   738   1...5.......1...2...8...4...5...4...3...1...5...6...7...2...6...7...2.......3...1
198   8,3   830   1...5.......1...6...4...2...3...2...5...8...7...9...1...6...9...5...3.......7...3
198   9,0   850   1...5.......1...6...9...3...6...3...4...2...5...7...2...7...8...3...2.......4...1
199   9,0   846   1...5.......2...3...7...4...9...3...7...4...8...6...5...8...5...3...4.......1...7
218   8,4   838   1...5.......2...3...4...6...9...3...6...4...5...8...7...5...2...3...9.......6...1
276   8,4   836   1...5.......2...6...4...3...3...9...5...2...1...6...7...6...2...7...4.......1...5
293   8,4   831   1...5.......2...6...4...3...3...4...9...8...5...3...2...7...9...6...3.......9...8
360   9,1   848   1...5.......2...3...4...6...9...3...6...7...5...1...7...1...2...3...9.......6...1
433   8,5   851   1...5.......3...6...8...2...3...2...9...1...5...6...7...5...1...6...7.......9...8
 

The last one (puzzle 851) has one mutable cell r5c5 : 1->8.
The resultant puzzle
Code: Select all
 1...5.......3...6...8...2...3...2...9...8...5...6...7...5...1...6...7.......9...8

has a suex rating of 451 and ER = 8.5.

Could you help me to find it (or one equivalent) in the Nick70's list ?

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

Postby ravel » Tue Oct 10, 2006 9:57 pm

If i made no mistake, the last one in Nicks list should be equivalent:
Code: Select all
1...5.......3...6...8...2...3...2...9...1...5...6...7...5...1...6...7.......9...8
to yours
Code: Select all
1...5.......3...6...8...2...3...2...9...8...5...6...7...5...1...6...7.......9...8
Both are normalized to
Code: Select all
....5.6..4....9....8......12....4......8...9...5.1.3...6......5...2...4...1.3....
by gsf's program.

Howto:
Batch file (.bat) with
Code: Select all
sudoku -qFN -f%%#0c puzzles.txt > puzzles.can
to normalize.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby JPF » Tue Oct 10, 2006 11:18 pm

Thanks ravel for the check by canonicalization !

so the mutable r5c5 in P851 gives :
Mut (851) ~ (851) ;

It took me some time to find the exact operations* transforming this puzzle :
(851)
Code: Select all
 1 . . | . 5 . | . . .
 . . . | 3 . . | . 6 .
 . . 8 | . . . | 2 . .
-------+-------+-------
 . 3 . | . . 2 | . . .
 9 . . | . 1 . | . . 5
 . . . | 6 . . | . 7 .
-------+-------+-------
 . . 5 | . . . | 1 . .
 . 6 . | . . 7 | . . .
 . . . | . 9 . | . . 8

into this equivalent one :
Mut (851)
Code: Select all
 1 . . | . 5 . | . . .
 . . . | 3 . . | . 6 .
 . . 8 | . . . | 2 . .
-------+-------+-------
 . 3 . | . . 2 | . . .
 9 . . | . 8 . | . . 5
 . . . | 6 . . | . 7 .
-------+-------+-------
 . . 5 | . . . | 1 . .
 . 6 . | . . 7 | . . .
 . . . | . 9 . | . . 8

* Here gsf wrote:the permutations that leave a sudoku unchanged are:
(a) rotate the grid 90 degrees
(b) swap the top two rows
(c) swap the top two bands
(d) swap any two cell values for all cells with those values

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

Postby ronk » Wed Oct 11, 2006 12:04 am

JPF wrote:It took me some time to find the exact operations* transforming this puzzle : (851) ... into this equivalent one : Mut (851) ...

Swap digits 1 and 8
Swap digits 3 and 7
Reflect diagonally

Diagonal reflection is equivalent to a combination of other permutation steps.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Next

Return to General