Revealing twins

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: Revealing twins

Postby dyitto » Fri Jan 21, 2011 6:56 am

One nice solvable puzzle like the ones before:

Code: Select all
734|.6.|...
...|...|..9
..2|...|.6.
---+---+---
5.9|.2.|7..
4..|...|.52
.6.|..4|..1
---+---+---
...|7.1|4.3
...|2.6|.1.
...|.4.|...

...|.6.|3..
...|.3.|2.8
...|...|...
---+---+---
...|.97|...
.84|...|9..
..3|..4|.5.
---+---+---
.5.|4.3|...
...|8..|...
...|...|.7.
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam

Re: Revealing twins

Postby dyitto » Fri Jan 21, 2011 7:00 am

See previous puzzle.
With my new depth-first algorithm with recursion I wanted to verify unique solution after removing the 6 in R6C2.
Even then it jumps to 1.4Gb memory and out of memory exception.

Hope someone can help me tackle this. The same routine seems to work fine on some regular but difficult Gattai 5 from the Sudoku Solvers forum.
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam

Re: Revealing twins

Postby dyitto » Tue Jan 25, 2011 6:27 am

dyitto wrote:
dyitto wrote:Two grids with 3 revealing digits each direction haven't been found yet after running for 8 hrs.

Aargh
New depth-first algorithm with recursion: Out of memory after running for 3 seconds :cry:


It was a bug that caused the program to collect more memory then necessary for the task. And it has been fixed.
Code: Select all
.4.|2.8|5..
.5.|1..|.47
...|...|.2.
---+---+---
.7.|...|...
5..|.91|..3
...|...|..1
---+---+---
7..|82.|..6
8..|.1.|...
..6|7.5|...

...|..9|.36
2..|.71|9..
3..|...|..1
---+---+---
...|...|.8.
...|...|...
..7|...|..2
---+---+---
...|1..|...
...|...|...
.5.|8.4|.6.

1, 2, 3 in grid 1 reveal a group in grid 2.
7, 8, 9 in grid 2 reveal a group in grid 1.

You may find that the solution grid is not exactly a random one. :)
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam

Re: Revealing twins

Postby dyitto » Tue Jan 25, 2011 9:32 pm

Code: Select all
.4.|...|..9
...|1.9|...
...|..7|...
---+---+---
...|.82|...
58.|...|47.
..3|...|2..
---+---+---
...|...|9..
...|.1.|..4
9..|...|.1.

...|...|3..
28.|3..|..9
3..|...|..4
---+---+---
..9|...|.8.
52.|..7|...
61.|...|4..
---+---+---
.63|..2|..8
...|...|6..
...|...|.2.

All digits in grid 1 reveal a group in grid 2 - and vice cersa.


I only had to check if 8 digits in one direction hold. ;)
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam

Re: Revealing twins

Postby BryanL » Wed Jan 26, 2011 6:08 am

dyitto wrote:It was a bug that caused the program to collect more memory then necessary for the task. And it has been fixed.

Well I am glad you found it because no-one else was going to from the little info you gave...

1, 2, 3 in grid 1 reveal a group in grid 2.
7, 8, 9 in grid 2 reveal a group in grid 1.

Code: Select all
147238569258169347369457128471382695582691473693574281714823956825916734936745812
175489236286371945394562871419235687528617394637948152743196528862753419951824763

You may find that the solution grid is not exactly a random one. :)

You could scramble them just a little to hide the common columns...

Code: Select all
.91|..3|5..
...|...|.7.
...|..1|...
---+---+---
82.|..6|7..
7.5|...|..6
.1.|...|8..
---+---+---
...|.2.|...
2.8|5..|.4.
1..|.47|.5.

...|...|...
...|.8.|...
...|..2|..7
---+---+---
1..|...|...
8.4|.6.|.5.
...|...|...
---+---+---
...|..1|3..
..9|.36|...
.71|9..|2..
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Revealing twins

Postby BryanL » Wed Jan 26, 2011 6:18 am

dyitto wrote:All digits in grid 1 reveal a group in grid 2 - and vice cersa.

After finishing the previous twins with 3 in each revealing groups, I was pondering if all digits could reveal and whether to try and craft one by hand... but didn't have time.

Then I just happened to refresh and your next post was there. Had to try it - so all my time got wasted anyway... :roll:

Code: Select all
147238569258169347369457128471382695582691473693574281714823956825916734936745812
174689352285374169396215874439561287528437916617928435763192548852743691941856723
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Revealing twins

Postby dyitto » Wed Jan 26, 2011 6:48 am

Your solutions again match mine. :)

The 3 each direction and 9 each direction have the same 1st grid - which I'm noticing right now.

My next target:
Random generation of similar grids.
Expand the necessary solving techniques.
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam

Re: Revealing twins

Postby BryanL » Wed Jan 26, 2011 8:42 am

dyitto wrote:Your solutions again match mine. :)

If they didn't then you would have a multi solution and I get the feeling there is always only one... :)

The 3 each direction and 9 each direction have the same 1st grid - which I'm noticing right now.

The 1st grid in both is the MC grid transposed.

Where you aware of that?

My next target:
Random generation of similar grids.

I wanted to ask you your method of generation. Do you just start with one grid, and trial and error the second grid till you get the necessary grid, then remove clues until it is minimal for the method?

By the way the 9 groups each way was awesome to see.
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Revealing twins

Postby dyitto » Wed Jan 26, 2011 8:00 pm

BryanL wrote:I wanted to ask you your method of generation. Do you just start with one grid, and trial and error the second grid till you get the necessary grid, then remove clues until it is minimal for the method?

There is a solver routine that solves or reduces the possibilities using known techniques like singles, pairs etc.

There is a depth-first routine that systematically tries all options one by one - starting with the first possible digit in the first possible cell and so on - repeatedly calling the solver routine.
(This routine was designed to conclusively tell if a situation has one unique solution - as a by-product it returns a valid one if found.)
It treats the twin grids as one collection of 162 cells.
By coincidence, since the cells of the 1st grid are ordered before the cells of the 2nd grid, this routine will start to complete the 1st grid. But on this part I could easily do some scrambling.

Till here I think it works no different from many existing sudoku programs. Only in the solver routine the reveal-constraint is applied.

(I actually started with a different random generation routine that repeatedly tries random options - and starts all over again whenever the solver routine returns Unsolvable. This routine is much slower
and couldn't even find any 3-each-directon grid in a 16hrs run.)

Once I have a complete grid, clues are removed until it is minimal for the method (of the solver routine).
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam

Re: Revealing twins

Postby BryanL » Wed Jan 26, 2011 11:02 pm

Hi Dyitto,

thanks for the reply.

Yesterday I was playing around trying to manually create a twin with more than one each way. I was trying and eliminating various symmetries - rotations, reflections and transpose. Observing what was happening gave me a clue and I came up with a pair of 9 digits revealing groups in both directions grids - like the last pair you posted. I will play around and remove some clues and post it later - my solver isn't programmed for twins so checking will be tedious and I may give up...

While playing around with the grids, I suddenly realised that this puzzle variation easily*** lends itself to the dancing links exact cover solving methodology - as a quick means of testing whether two puzzles give 0, 1 or more valid solutions. *** It may not be easy. I haven't thought it through completely. If the extra constraints don't have the same number of rows it could be messy... But the extra constraints are fairly obvious.

Just another point on 9 digits revealing groups in both directions. I suspect (prove me wrong?) that for any grid 1, there will be one and only one grid 2 with the correct property - except perhaps with symmetric relabeling.

later
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Revealing twins

Postby dyitto » Wed Jan 26, 2011 11:14 pm

dyitto wrote:My next target:
Random generation of similar grids.
Expand the necessary solving techniques.


Here's a puzzle:

Code: Select all
..3|...|8..
51.|..8|..4
...|.5.|7..
---+---+---
...|...|6.9
...|..9|..5
...|..1|...
---+---+---
4.7|8.6|...
8..|4..|...
...|.95|...

...|...|...
.73|5..|9..
.5.|...|8..
---+---+---
...|8..|..5
...|.69|7..
...|...|.64
---+---+---
7..|...|..3
.1.|...|..6
3..|..8|...


It's the variant with only 1 and 9 like the first puzzles.
[edit]
So this one has only one digit each direction:
1 in grid 1 reveals a group in grid 2 & 9 in grid 2 reveals a group in grid 1
[/edit]

There is a solving path. It requires a technique other then the puzzles so far.

BryanL wrote:The 1st grid in both is the MC grid transposed.

Where you aware of that?

Do you have a link with some more explanation about the MC grid?
Last edited by dyitto on Thu Jan 27, 2011 8:06 pm, edited 1 time in total.
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam

Re: Revealing twins

Postby dyitto » Wed Jan 26, 2011 11:24 pm

BryanL wrote:Just another point on 9 digits revealing groups in both directions. I suspect (prove me wrong?) that for any grid 1, there will be one and only one grid 2 with the correct property - except perhaps with symmetric relabeling.

The first random sudoku grid I checked hasn't.
Code: Select all
957|361|482
836|427|951
412|859|736
---+---+---
524|186|397
693|745|128
781|932|645
---+---+---
178|594|263
245|613|879
369|278|514

Maybe you can doublecheck this in JSudoku by entering new constraint groups corresponding to each digit.
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam

Re: Revealing twins

Postby BryanL » Thu Jan 27, 2011 12:53 am

dyitto wrote:
BryanL wrote:The 1st grid in both is the MC grid transposed.

Where you aware of that?

Do you have a link with some more explanation about the MC grid?


Code: Select all
123|456|789
456|789|123
789|123|456
---+---+---
214|365|897
365|897|214
897|214|365
---+---+---
531|642|978
642|978|531
978|531|642


MC = Most Canonical - the smallest lexicographical representation - also minlex - in this case row minlex.
There are many threads about canonical grids and canonicalisation - permuting and relabeling a grid to minlex form.
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Revealing twins

Postby BryanL » Thu Jan 27, 2011 1:14 am

dyitto wrote:
Code: Select all
..3|...|8..
51.|..8|..4
...|.5.|7..
---+---+---
...|...|6.9
...|..9|..5
...|..1|...
---+---+---
4.7|8.6|...
8..|4..|...
...|.95|...

...|...|...
.73|5..|9..
.5.|...|8..
---+---+---
...|8..|..5
...|.69|7..
...|...|.64
---+---+---
7..|...|..3
.1.|...|..6
3..|..8|...

There's an error with those two...
A couple of moves reveal an 8 in r5c9 in pzl2, but there is already a 5 in both r5c9 and r9c6 in pzl1
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Revealing twins

Postby BryanL » Thu Jan 27, 2011 1:55 am

dyitto wrote:
BryanL wrote:Just another point on 9 digits revealing groups in both directions. I suspect (prove me wrong?) that for any grid 1, there will be one and only one grid 2 with the correct property - except perhaps with symmetric relabeling.

The first random sudoku grid I checked hasn't.


Do you mean it hasn't got another 2nd grid with the correct property or it hasn't got only one???

Maybe you can doublecheck this in JSudoku by entering new constraint groups corresponding to each digit.

Unfortunately JSudoku author site is unavailable at the moment. - is this it? http://jcbonsai.free.fr/sudoku/
BryanL
 
Posts: 247
Joined: 28 September 2010

PreviousNext

Return to Sudoku variants

cron