Local permutation and hints needed

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

Local permutation and hints needed

Postby Addlan » Wed Aug 06, 2008 11:48 am

The most canonical sudoku below needs at least 20 hints to solve.
123456789456789123789123456231564897564897231897231564312645978645978312978312645

It can be first permutated locally to
216543897543789126798126543162435789435897261987261435621354978354978612879612354
with mainly two digits swaps

Then further permutated locally to
793216845518734926246958713965187234187342569432569187379621458851473692624895371
with three digits swaps

Use checker to run this permutated sodoku for about two hours and five sodokus with 19 hints have already been found.
700200800500700000006000710000007000080040009030500000000001000000000602020090000
700200800500700000006000013000007000080040009030500000000001000000000602020090000
700200800500700000006000010000007000080040009030500007000001000000000602020090000
700200800500700000000008003000000000080040560032009000000000400000000002600090001
700200800500030900006000010000007034080000000000500007000001000000000602020090000

The problem is how to permutate the canonical sudoku each time to reduce the number of hints needed. Finally it may possibley solve the minimum hint problem.

I suspect that any permutation will produce a non-isomorphic sudokus. The question will be: is it possible to produce its isomorphic sudokus through a series of permutations. If it is the case, I strongly favour that all Sudokus can be tranformed into each other.

It is quite sensible to perform the permutations within the unavoidable sets. I also notice that permutating three digits in all 9*9 grids can produce lots of permutation variations.
Last edited by Addlan on Wed Aug 06, 2008 11:08 am, edited 1 time in total.
Addlan
 
Posts: 62
Joined: 15 July 2005

Postby tarek » Wed Aug 06, 2008 12:00 pm

an isomorphic grid should generate the same results.

Therefore your grids which produced different results are not isomorphic.

an isomorphic grid is produced through any sequence of well known permutations.

Are we talking here about different permutations ?


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

Postby Addlan » Wed Aug 06, 2008 3:13 pm

tarek wrote:an isomorphic grid should generate the same results.

Therefore your grids which produced different results are not isomorphic.


Surely isomorphic sudokus should generate same results. But I am pretty sure all permutations will lead to its non-isomorphic sudokus. That it why I wonder if it is possible to reach the minimum clue sudoku, which will be non-isomorphic to the original one, through a series of permutations.

B. W.
Addlan
 
Posts: 62
Joined: 15 July 2005

Postby JPF » Wed Aug 06, 2008 4:12 pm

Addlan wrote:It can be first permutated locally to
216543897543789126798126543162435789435897261987261435621354978354978612879612354
with mainly two digits swaps

Then further permutated locally to
793216845518734926246958713965187234187342569432569187379621458851473692624895371
with three digits swaps

What do you mean by "locally permuted" with 2/3 digits swaps ?

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

Re: Local permutation and hints needed

Postby RW » Wed Aug 06, 2008 5:40 pm

Addlan wrote:It is quite sensible to perform the permutations within the unavoidable sets.

:?::?:

I think this is where your logic might have gone wrong... To preserve isomorphism, any permutation must always be applied to the whole grid, not just some unavoidable sets. None of your two permutated grids are isomorphic to the MC-grid. They are different grids, therefore they will produce different sudoku puzzles.

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

Postby Addlan » Wed Aug 06, 2008 5:44 pm

JPF wrote:What do you mean by "locally permuted" with 2/3 digits swaps ?
JPF


The most canonical
*-----------*
|123|456|789|
|456|789|123|
|789|123|456|
|---+---+---|
|231|564|897|
|564|897|231|
|897|231|564|
|---+---+---|
|312|645|978|
|645|978|312|
|978|312|645|
*-----------*

If you swap digits (1,2) in grid pairs (r1c1,r1c2), (r4c1,r4c3) and (r6c2,r6c3), and in the same way swap digits (3,6) in (r1c3,r2c3) in the first band, etc, except digits (7,8,9), you will get the sudoku below:

permutation 1:
*-----------*
|216|543|897|
|543|789|126|
|798|126|543|
|---+---+---|
|162|435|789|
|435|897|261|
|987|261|435|
|---+---+---|
|621|354|978|
|354|978|612|
|879|612|354|
*-----------*

If you swap digits (2,5,7) in the first row of the first box, in a way, with the rest 2s,5s,7s in the whole 3*3 grids, and do the same with digits (1,4,9) and (6,3,8) in the first box, you will get the permutation 2 as below:

permutation 2
*-----------*
|793|216|845|
|518|734|926|
|246|958|713|
|---+---+---|
|965|187|234|
|187|342|569|
|432|569|187|
|---+---+---|
|379|621|458|
|851|473|692|
|624|895|371|
*-----------*

Checker has run for more than 5 hours and find 35 unique 19-hints sudokus. The weird thing is that it says it needs to run 417 days to get the 100% results. Whatever, it is enough to prove that some kinds of permutations can reduce the number of hints needed.

Whether someone is able to produce two randomly selected, normalised non-isomorphic sudokus (ideally with different minimum hints) to check whether they can be transformed somehow into each other, and in what sort of transformation paths if that is at all possible.
Addlan
 
Posts: 62
Joined: 15 July 2005

Re: Local permutation and hints needed

Postby Addlan » Wed Aug 06, 2008 5:54 pm

RW wrote:
None of your two permutated grids are isomorphic to the MC-grid.

RW


But this is exactly what is intended. What is the most non-isomorphic sudoku to the MC one? Maybe the one is able to produce least hints (or perhaps the pseudo 16-hint sudokus), and can be transformed from MC through some permutations.
Addlan
 
Posts: 62
Joined: 15 July 2005

Re: Local permutation and hints needed

Postby RW » Wed Aug 06, 2008 6:16 pm

Addlan wrote:But this is exactly what is intended. What is the most non-isomorphic sudoku to the MC one? Maybe the one is able to produce least hints (or perhaps the pseudo 16-hint sudoku), and can be transformed from MC through some permutations.

Around here, when we talk about "grid permutation", we mean permutational operations that preserve isomorphism. What you are doing is something totally different. Hence the confusion about what you are trying to say.

Swapping digits within only a few unavoidable sets will produce a new grid. Doing this long enough... hmm, can't remember if this has been discussed somewhere here before... but I think you can produce all sudoku grids starting from just one grid. In case this hasn't been discussed before, a proof for or against would of course be welcome.

Anyway, using checker on a grid produced this way gives you really no usefull info at all. A non isomorphic grid will have different qualities and produce different sudokus.

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


Return to General