Twin Equivalent Sudokus

For fans of Killer Sudoku, Samurai Sudoku and other variants

Postby Shintaro » Sun Nov 26, 2006 5:10 am

Here is another example by Henry Kwok for tarek, RW and anybody who is interested in his variant. Have fun!:D

Twin A
Image


Twin B
Image
Shintaro
 
Posts: 35
Joined: 02 November 2006

Postby udosuk » Tue Nov 28, 2006 4:41 am

Has anyone solved the new puzzle? I tried to apply RW's method, but it gets me nowhere...:(

After SSTS on grid A, all the 2s and 3s are fixed but I couldn't see any digit from grid B would match them...:!:

Is there a new rule added where you can exchange rows/columns within bands/stacks as well?:?:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Shintaro » Tue Nov 28, 2006 7:22 am

Hi udosuk,

With no response so far, I was a bit worried, so I asked my friend to check his puzzle to see any flaw in it. He had checked the puzzle again and confirmed that it is valid and has a solution.

It was tempting for me to give some hints here, but my friend asked me to hold on for a few more days before giving some clues.

This puzzle is different from the previous two, as the shifting of the digits in the original puzzle to form the second puzzle is entirely different. Someone had noticed the interest generated by this variant and had suggested to my friend to make this variant a regular feature in this forum by providing at least one or two new puzzles of this type once a month. He also suggested a "Hall of Fame" incentive whereby the first person who can solve a new puzzle will get a point and have his or her name mentioned in this thread.

The friend thought that the idea is worth trying and has agreed to it. However, no prize will be given away. RW has earned a point by solving the first difficult puzzle. Let us see who can beat him by being the first to give the correct solution this time.:D
Shintaro
 
Posts: 35
Joined: 02 November 2006

Postby tarek » Tue Nov 28, 2006 10:23 am

I'm slightly making progress........

I think the key comes from the placed single....

My chain of thoughts focus on the fact that because r7c56 have been placed in both twins using singles....... that actually box 8 is more or less the same in both twins....

from that & because 4 in Twin B has been placed in box 3 .... then I believe that 4 in Twin B is the 3 in Twin A ......

Heavy line permutation though....

Anyone with a breakthrough using what I did?

[update]

I've permuted 2 lines in the 1st row of boxes in Twin B.....
it now looks like this...
Code: Select all
 . . 6 | . . . | . . 2
 . . . | . 3 . | . 7 5
 . . . | . . . | . . 4
-------+-------+------
 . . . | . . 9 | 5 4 .
 5 . . | 3 . . | 2 . 9
 . . . | . 5 . | . . . 
-------+-------+------
 . . 4 | 1 8 3 | . . .
 . 3 . | . . . | 4 . 8
 8 9 . | . . 4 | . . .
from the looks of it .... R789 & C789 are basically the same in both twins if my theory about the digit 4 is correct........

I don't have time today for this but essentially Box 9 now is identical in both........... r789 are correct but need some column permutation....c789 are correct but need row permutation

Does that make any sense ???

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

Postby udosuk » Wed Nov 29, 2006 12:01 am

So the rules have changed (without any notice:( )... Now the rows/columns can be permuted within bands/stacks...

Will try it later...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Shintaro » Wed Nov 29, 2006 4:50 am

Hi udosuk and tarek,

udosuk wrote:
So the rules have changed (without any notice )... Now the rows/columns can be permuted within bands/stacks...


Udosuk, you are absolutely right. Sorry for not informing everybody about the change of rules. Just as in real life, we don't expect a thief to tell the police how to catch him. The police have to make the most of whatever clues available to them. For example, if a detective finds a suspicious object at the scene of the crime, he would have to examine every part of it under his lens.

Both of you are heading in the right direction. In particular, tarek, you seem to be making some headway in solving the puzzle. All your three digits in the middle box (box 5) of twin B are correctly placed. Besides that, you are right in exchanging row 4 with row 6 in twin B.

What changes can you make in other rows or columns?

One way of solving this type of twin puzzles is to look for consistent patterns of digits in both puzzles and to find out whether the values of equivalent digits are consistent in both puzzles.

If necessary, I shall provide more clues in a few days' time.:D
Shintaro
 
Posts: 35
Joined: 02 November 2006

Postby tarek » Wed Nov 29, 2006 12:08 pm

Shintaro wrote:Both of you are heading in the right direction. In particular, tarek, you seem to be making some headway in solving the puzzle. All your three digits in the middle box (box 5) of twin B are correctly placed. Besides that, you are right in exchanging row 4 with row 6 in twin B


Then my previous conclusions were wrong:(

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

Postby Shintaro » Wed Nov 29, 2006 3:06 pm

Never mind, tarek. At least some of your steps are correct. Just continue from where you are correct.:)
Shintaro
 
Posts: 35
Joined: 02 November 2006

Postby gsf » Wed Nov 29, 2006 5:36 pm

here's a unix way to verify twin sudoku puzzles a.dat and b.dat (using my solver)
Code: Select all
for p in a b
do
    sudoku -qFN -d -a -f%#0v $p.dat |
    sudoku -f'%#0c %#0v' |
    sort > $p.can
done
join -j 1 a.can b.can

valid twins will result in one line printed by join containing 3 fields,
the (one) canonical solution for both twins, the solution for a.dat, and the solution for b.dat

the loop operates on each puzzle individually
the first sudoku generates all solutions
the second sudoku lists each puzzle with the canonical solution in field 1 and solution in field 2
the sort sorts by canonical solution (the join key)

the final join joins on the canonical solution
if the twins are valid only one solution from each twin will have the same canonical solution

this can be foiled by dropping enough clues from each twin to make
enumeration intractable -- so there's a challenge
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Shintaro » Wed Nov 29, 2006 6:34 pm

Hi gsf

It looks like you have found the solution, but unfortunately not many people can understand the unix way. Can you post your solution for both twins here? Don't post your solution in the so-called canonical form. You can post your solution in tiny letters or better still, post them together with the grids.

Your solver looks very interesting. Can you tell us where to get it -- preferably free of charge.

It would benefit many forum users if somebody could offer a simple explanation, either logically or mathematically, on how to arrive at the solution.:D
Shintaro
 
Posts: 35
Joined: 02 November 2006

Postby gsf » Wed Nov 29, 2006 7:12 pm

Shintaro wrote:It would benefit many forum users if somebody could offer a simple explanation, either logically or mathematically, on how to arrive at the solution.:D

the mathematical solution technique is basically in the previous message:
canonicalize each of the many solutions for both puzzles and use the
canonical solution as a sort/join key for the original solutions
then find the canonical solution that is the same for both twins
(that's the join operation)

that's a machine solution not recommended for humans

here's the canonical solution and original solutions for the twins

123456789456789123789132546231698475578341962694275318362914857847523691915867234
726349158394185672581267493648951237973624581152738946237596814819472365465813729
346578192785921634921436875419652783568347219273819546654183927137295468892764351
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Wed Nov 29, 2006 7:36 pm

It would be very simple if you put a sort key.......

1. if you have 1 duplicate then you have valid twins with a single answer
2. if you have more than 1 duplicate then you have multiple solutions.
3. if you have 0 duplicates then there is NO solution that fits both Twins.

it is simple.... The problem happens when you have Zillions of solutions to look through if you have few clues per Twin.......There is a possibility that the Twins do not share a single clue & still have one single solution to fit them both.........

Any chance of a 9 Clue Twin A & an 8 clue Twin B ?


I'm afraid that with the current format it is a bit of T&E ......... Show us a way Shintaro to solve this without T&E then you have a point.... I'm afraid if that is not the case then it is very easy for anyone to create such puzzles......

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

Postby Shintaro » Thu Nov 30, 2006 1:55 am

Hi gsf and tarek,

Gsf, your solution is absolutely correct, but unfortunately it is what you called -- a "machine solution". Of course, everybody is more interested in a "human solution" than a "machine solution" so that the same technique can be applied to other similar problems in the future. Can anyone, especially mathematicians, show us a simple mathematical or logical method of solving this puzzle?

tarek wrote:
it is simple.... The problem happens when you have Zillions of solutions to look through if you have few clues per Twin.......There is a possibility that the Twins do not share a single clue & still have one single solution to fit them both...I'm afraid that with the current format it is a bit of T&E ......... Show us a way Shintaro to solve this without T&E then you have a point.... I'm afraid if that is not the case then it is very easy for anyone to create such puzzles......


Nowadays a large number of standard sudoku puzzles are created daily by generators for newspapers and puzzle websites. Creating a standard sudoku manually seems to be so easy that even a child can be taught to do it.

In theory, two equivalent puzzles are actually one standard sudoku puzzle with different arrangement of the nine digits, or with two rows (columns) exchanged within the same block of rows (columns), or with two boxes exchanged within the same row (column) of boxes in the same grid.

Hence tarek is partially correct to say that it "very easy for anyone to create such puzzles". However such puzzles, when created haphazardly, will turn out to be two extremes. They are either too easy -- with too many redundant clues -- or so difficult that no solution can be found, even with a machine.

Such puzzles are different in quality from those done painstakingly by handcrafting. That's why the Japanese claim that their puzzles are all handcrafted, not generated by software. They also say they prefer handcrafting their puzzles rather than by using software.

Tarek mentions of "Zillions of solutions to look through", but a generator is not a supercomputer software to do such astronomical calculation. A "machine solution" found by a simple software points to the existence of a "human solution".

I have consulted my friend about the puzzles. He said that some of the clues are hidden in the twin puzzles and could be made visible by first solving both puzzles with the usual sudoku strategy or technique.

Can tarek or anyone else help to post on the forum the two original grids with all the available clues they can find by the usual sudoku strategy? Then we can try to spot any interesting pattern or any telltale sign or link between the twin puzzles.

Thanks for your interest and help.:)
Shintaro
 
Posts: 35
Joined: 02 November 2006

Postby gsf » Thu Nov 30, 2006 7:33 am

Shintaro wrote:Gsf, your solution is absolutely correct, but unfortunately it is what you called -- a "machine solution".

my initial post stated up front that it was a method to verify that a twin sudoku puzzle was valid
you subsequently asked for the solution and I posted it
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Shintaro » Thu Nov 30, 2006 8:35 am

gsf wrote:
that's a machine solution not recommended for humans


I refer you to what you had said above which you appear to have forgotten, and also what tarek said below:

tarek wrote:
I'm afraid that with the current format it is a bit of T&E ......... Show us a way Shintaro to solve this without T&E then you have a point.... I'm afraid if that is not the case then it is very easy for anyone to create such puzzles...... "


It is true that you have obtained the solution and your method has verified that the twin sudoku puzzles are valid, but at the same time you have admitted that it is "a machine solution not recommended for humans".

I also agree with you that the puzzle is valid and has a solution. There is no doubt about it. However, you can see that tarek is not satisfied with your method, considering it a trial and error method using a generator. If I am not wrong, you have to convince him and perhaps many others by showing your working step by step just like the way high school students prove mathematical theorems in schools.:D
Shintaro
 
Posts: 35
Joined: 02 November 2006

PreviousNext

Return to Sudoku variants