The New Sudoku Players' Forum

[m_b_metcalf]

Allow me to introduce what I think is a new concept: Troika sudokus. I start with some definitions:

Magic Troika: A set of three standard, valid, minimal puzzles that:


1. share the same solution;

2. do not overlap (are disjoint);

3. when added together (placed on top of one another), exactly cover the solution grid (the sum of their individual number of clues equals 81).

Perfect Troika: a Magic Troika in which each puzzle has 27 clues.

Sublime Troika: A Perfect Troika in which each puzzle has some form of symmetry.

Here is a not-quite Magic Troika:

Code: Select all

.....4.23....8.156...5..84...1..3..5.6.....1.9..8..6...85..7...712.9....69.2.....  28 clues ED=7.7/7.7/7.3
..81..9...3...2...1.6.....7....2.79....9....8.5.....3.3..4..2.......6.84..4..83.1  25 clues ED=8.8/1.2/1.2
57..6....4.97......2..39...84.6.....2.3.754....7.41..2....1..69...3..5......5..7.  28 clues ED=2.0/1.2/1.2, 3 clues individually redundant
578164923439782156126539847841623795263975418957841632385417269712396584694258371

It suffers from the third puzzle not being minimal.

And here is a not-quite Perfect Troika:

Code: Select all

1..2..3...4..5..6...2..7..82....49...8..6..5...47....64..3..6...2..7..3...3..9..1  27 clues  ED=9.7/9.7/9.7
.7..46.....98..7..65.93..4..16....739.7.....453..9........1....8.......9...4..58.  27 clues  ED=9.0/1.2/1.2
..8....953....1..2......1.....58.......1.32.......281..95..8.27..16.54..76..2....  27 clues    5 solutions
178246395349851762652937148216584973987163254534792816495318627821675439763429581

It suffers from the third puzzle not having a unque solution.

With so many clever programmers here, is it possible that someone can create better ones? (And can Mathimagics tell us how many Perfect Troikas exist in the known universe?)

Regards,

Mike

[Mathimagics]

can Mathimagics tell us how many Perfect Troikas exist in the known universe?

I had the answer scribbled on a piece of paper somewhere, but the cat ate it!

It's a serious challenge, really. My first attempt targeted the MC grid, for which I generated some 300,000 x 27-clue minimal puzzles. I only found 7500 instances of disjoint pairs. These all had multiple solutions for the implied 3rd puzzle, and only one case had just 2 solutions:

Code: Select all

....56....5.7....378.1..4...3....8.75.4...2......3.56...264..7....9.831...8......
...4...8...6.8.1....9.2...62...6..9....8.7.31..7......31......86.5......9...12645
123...7.94....9.2......3.5...15.4....6..9....89.2.1..4.....59...4..7...2.7.3..... # 2 solutions


So, really close, but no cigar!

The search continues ...

[m_b_metcalf]

So, really close, but no cigar!

The search continues ...

Yes, close, and thanks for trying. In the meantime I've come up with a flawed Sublime Troika. I display it in long form to reveal the left-right symmetry of each puzzle.

Code: Select all

 . 3 8 . . . 2 1 .
 . 9 . . 2 . . 4 .
 . . . 5 . 3 . . .
 2 . . . . . . . 6
 . . . 4 . 7 . . .
 8 7 . . 3 . . 9 5
 . 8 5 . . . 1 6 .
 . . . . . . . . .
 . . 4 3 5 8 9 . .   ED=2.0/1.2/1.2,  5 clues individually redundant

 . . . . . . . . .
 6 . . 8 . 1 . . 3
 . . 2 . 9 . 6 . .
 . . . 9 . 5 . . .
 9 5 . . 6 . . 2 1
 . . 6 . . . 4 . .
 3 . . . 7 . . . 4
 7 2 . 6 . 4 . 5 8
 1 . . . . . . . 2   ED=2.0/1.2/1.2,  6 clues individually redundant

 5 . . 7 4 6 . . 9
 . . 7 . . . 5 . .
 4 1 . . . . . 8 7
 . 4 1 . 8 . 7 3 .
 . . 3 . . . 8 . .
 . . . 1 . 2 . . .
 . . . 2 . 9 . . .
 . . 9 . 1 . 3 . .
 . 6 . . . . . 7 .   ED=1.5/1.2/1.2,  6 clues individually redundant


.38...21..9..2..4....5.3...2.......6...4.7...87..3..95.85...16............43589..                                 
.........6..8.1..3..2.9.6.....9.5...95..6..21..6...4..3...7...472.6.4.581.......2 
5..746..9..7...5..41.....87.41.8.73...3...8.....1.2......2.9.....9.1.3...6.....7. 
538746219697821543412593687241985736953467821876132495385279164729614358164358972


Regards,

Mike

[Mathimagics]

Happy to advise that "Perfect Troikas" do exist ...

Code: Select all

....56...45.7.....7891......3....8.75....7..1....3.56...264..7....9...129.......5 # 27c, minimal
...4..789..6.8.12......3..62.1.6.......8...3.8..2.1..43.....9..6.5.7.....7...2.4. # 27c, minimal
123...........9..3....2.45....5.4.9..64.9.2...97.......1...5..8.4...83....831.6.. # 27c, minimal

....567....6.....3.8.1..4...3....8.75.4..7.......3.56...2.4..7....9.83129.8...... # 27c, minimal
.2.4...894...8.1..7....3.562.1.64......8...3.8....1.........9...45.7.....7.3.26.. # 27c, minimal
1.3.......5.7.9.2...9.2.......5...9..6..9.2.1.972....431.6.5..86............1..45 # 27c, minimal

..3...7..456.....3.8..2.4..2.1.64.9.....9.2.......15....2..5.7.6..97....9...1...5 # 27c, minimal
.2.4.6.89...7..12...9............8..5..8.7.3..97.3...43...4.....4.....12..83.26.. # 27c, minimal
1...5........89...7..1.3.56.3.5....7.64.....18..2...6..1.6..9.8..5..83...7.....4. # 27c, minimal

..3...7..456.....3.8..2.4..2.1.64.9.....9.2.......15....2..5.7.6..97....9...1...5 # 27c, minimal
.2.4.6.89...7..12...9............8..5..8.7.3..9723...43...4.....4.....12..8..26.. # 27c, minimal
1...5........89...7..1.3.56.3.5....7.64.....18......6..1.6..9.8..5..83...7.3...4. # 27c, minimal


It was necessary to seriously expand the minimal 27-clue pool. I let the pool grow to nearly 2 million, then crunched the numbers:

• pool size = 1,942,846

• disj pairs = 8,960,039

• valid p3 = 296 (valid 3rd puzzle derived from pair)

• minimal p3 = 4

I will try one more expansion of the pool (on this grid = MC grid) to get some idea of the effect on these numbers, then I intend to try a random non-automorphic grid for comparison.

[Serg]

Hi, Mathimagics!
Congratulations for finding Perfect Troikas! (I was very doubt if they do exist.)

Serg

[m_b_metcalf]

Happy to advise that "Perfect Troikas" do exist ...

A stunning achievement! Well done!

Mike

[Mathimagics]

I will try one more expansion of the pool (on this grid = MC grid) to get some idea of the effect on these numbers

Ok, I extended the pool of minimal 27-clue puzzles by 50%, and obtained the following results:

• pool size = 2,931,822

• disj pairs = 20,005,620

• valid p3 = 4227

• minimal p3 = 104

So for a 50% boost in the pool, we get 2.2 times the # of disjoint pairs, 14 times the # of valid p3's, and 25 times the number of perfect troikas!

Considering that the pool generation process (random reductions + minimal 27 enumeration) is still finding minimal 27's that are almost always new (99.9%), then this seems to be just a fraction of the many, many more perfect troikas that can be found on this grid.

But the cost of mining them goes up as the pool size is increased ...

So, for other grids I will simply start with a smaller pool, adding increments until any perfect troikas are found.

[m_b_metcalf]

That's an astonishing yield and I can't compete with that. I'm happy that Perfect Troikas aren't just some crazy idea. I've produced some in which p3 is now at least a valid puzzle, the best of the bunch being:

Code: Select all

1..2..3...2..1..4...3..4..53..6..5...7..5..3...8..1..78..1..4...3..6..9...9..2..3  27 ED=6.6/6.6/3.4(!)                           
..4....7...53.6..86..97.....4..2..8.2.6...1.495..............52..25.87...1.7...6.  27 ED=1.5/1.2/1.2
.9..85..67.....9...8....21...1..7..9...8.9......43.62..67.93...4.......15...4.8..  27 ED=7.1/1.2/1.2, 3 redundant clues 
194285376725316948683974215341627589276859134958431627867193452432568791519742863

I'll stop there. Thanks for your effort. I think you should publish the Perfect Troikas somewhere where they'll get more attention. They really are remarkable.

Regard,

Mike

[Mathimagics]

I still need to verify whether I can find them for arbitrary grids.

I chose the MC grid initially simply because I had a hunch that a grid with a large number of small UA's was more likely to produce troikas. That turned out to be true, but what I really want to do is look at general population grids and see if I can find a perfect troika that doesn't have repeating minirows/columns in the solution grid ...


I'm running a trial grid right now ... we'll see if it produces!

[m_b_metcalf]

I still need to verify whether I can find them for arbitrary grids.

That's what I used. I have files of mimimal 27-clue puzzles and looked for minimal p2s with 27 clues within the solution grids, and then tested the implied p3s.

Mike

[Mathimagics]

.
Bingo!!

I found 4 Perfect Troikas in this gen-pop grid, which was listed by Mike above:

Code: Select all

178246395349851762652937148216584973987163254534792816495318627821675439763429581


Code: Select all

..8..6...34..51..2.52......21......39......5..34.9..16.9.3.86.........3.....2.5.1 # 27C, minimal
1..24.39...9...7........148..658......71..2.45.....8..4...1...7..1..54...6...9... # 27C, minimal
.7......5...8...6.6..937........497..8..63......7.2.....5....2.82.67...97.34...8. # 27C, minimal

..8.4....34..5.7...529....8......97.....6.254........64..3.86.....6....97.3..95.. # 27C, minimal
.7....3.5..9....62....371....65....398...3...5...928......1..2.8.1.7.....6.4....1 # 27C, minimal
1..2.6.9....8.1...6......4.21..84.....71......347...1..95.....7.2...543.....2..8. # 27C, minimal

...2..3......5.7...5.93..4.21.......9.7.....4.34792.1....3..6..8.1..5..97..4..... # 27C, minimal
1........3.9..1..26.....1.8..65....3.8.16.25.......8...95....27...67.4......2.58. # 27C, minimal
.78.46.95.4.8...6...2..7.......8497......3...5.......64...18....2.....3..63..9..1 # 27C, minimal

..8......34.8......5...7...21...49....7..3...53...2.16..5.1.6......7.439...4..58. # 27C, minimal
.7.2463.5..9.5.76...2...1.....5...73...1..25.....9....4........8216......6...9..1 # 27C, minimal
1......9......1..26..93..48..6.8....98..6...4..47..8...9.3.8.27.....5...7.3.2.... # 27C, minimal


Process stats:

• pool size = 2,126,289

• disj pairs = 2,826,229

• valid p3 = 5148 (valid 3rd puzzle derived from pair)

• minimal p3 = 4

(Mike, can you verify these?)

[m_b_metcalf]

.

(Mike, can you verify these?)

Pefectly Perfect (how could it be otherwise?)!

Mike

[Serg]

Hi, Mathimagics!

I found 4 Perfect Troikas in this gen-pop grid, which was listed by Mike above:

Code: Select all

178246395349851762652937148216584973987163254534792816495318627821675439763429581


Code: Select all

..8..6...34..51..2.52......21......39......5..34.9..16.9.3.86.........3.....2.5.1 # 27C, minimal
1..24.39...9...7........148..658......71..2.45.....8..4...1...7..1..54...6...9... # 27C, minimal
.7......5...8...6.6..937........497..8..63......7.2.....5....2.82.67...97.34...8. # 27C, minimal

..8.4....34..5.7...529....8......97.....6.254........64..3.86.....6....97.3..95.. # 27C, minimal
.7....3.5..9....62....371....65....398...3...5...928......1..2.8.1.7.....6.4....1 # 27C, minimal
1..2.6.9....8.1...6......4.21..84.....71......347...1..95.....7.2...543.....2..8. # 27C, minimal

...2..3......5.7...5.93..4.21.......9.7.....4.34792.1....3..6..8.1..5..97..4..... # 27C, minimal
1........3.9..1..26.....1.8..65....3.8.16.25.......8...95....27...67.4......2.58. # 27C, minimal
.78.46.95.4.8...6...2..7.......8497......3...5.......64...18....2.....3..63..9..1 # 27C, minimal

..8......34.8......5...7...21...49....7..3...53...2.16..5.1.6......7.439...4..58. # 27C, minimal
.7.2463.5..9.5.76...2...1.....5...73...1..25.....9....4........8216......6...9..1 # 27C, minimal
1......9......1..26..93..48..6.8....98..6...4..47..8...9.3.8.27.....5...7.3.2.... # 27C, minimal


First, I confirm that this (random) solution grid isn't MC grid. All 12 published puzzles have unique solutions and are minimal. Each published Perfect Troika contains disjoint puzzles only. 4 Perfect Troikas for MC grid are valid too.

Well done!

Serg

[Mathimagics]

Hello Serg!

Thank you (and Mike) for the confirmation ...

I have now tested a further 3 random grids, each in a different band, and all with similar results to the one above.

In each case I stopped the pool generation at ~2 million minimal 27's, and from that pool the pairs-search found 2 to 4 Perfect Troikas.

I will not do many more grids, since this is very much an expensive exercise - the cost for one grid is ~36 core-hours. I do have 14 available so I was able to do these 4 grids in around 8-9 hours. The processing was easy to distribute across the cores.

I will do just one more set tomorrow, to see if this trend continues (namely, every grid having Perfect Troikas).

I have some ideas for an alternative procedure, but it would need to be very, very much faster than this one ...


Cheers
MM

[Mathimagics]

This Perfect Troika seems to be highly rated?

Code: Select all

..17....2379.4..8.8...1......7.2.9...9.6....341...9......3..8.....4...36....82..5 ED=8.3/1.2/1.2
6....8.9......65.1.5.9..6.7........4..8..415...653..2.7.4.6.....8...72..9..1..... ED=8.4/1.2/1.2
.4..5.3.....2.......2..3.4.53.8.1.6.2...7..........7.8.2...5.191.5.9.....63...47. ED=8.4/1.2/1.2