## Troika Sudokus. A challenge.

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

### Troika Sudokus. A challenge.

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.257..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 redundant578164923439782156126539847841623795263975418957841632385417269712396584694258371`

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 solutions178246395349851762652937148216584973987163254534792816495318627821675439763429581`

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

m_b_metcalf
2017 Supporter

Posts: 13094
Joined: 15 May 2006
Location: Berlin

### Re: Troika Sudokus. A challenge.

m_b_metcalf wrote: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...12645123...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 ...

Mathimagics
2017 Supporter

Posts: 1870
Joined: 27 May 2015
Location: Canberra

### Re: Troika Sudokus. A challenge.

Mathimagics wrote:
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

m_b_metcalf
2017 Supporter

Posts: 13094
Joined: 15 May 2006
Location: Berlin

### Re: Troika Sudokus. A challenge.

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, minimal123...........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, minimal1.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, minimal1...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, minimal1...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.

Mathimagics
2017 Supporter

Posts: 1870
Joined: 27 May 2015
Location: Canberra

### Re: Troika Sudokus. A challenge.

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

Serg
Serg
2018 Supporter

Posts: 785
Joined: 01 June 2010
Location: Russia

### Re: Troika Sudokus. A challenge.

Mathimagics wrote:Happy to advise that "Perfect Troikas" do exist ...

A stunning achievement! Well done!

Mike

m_b_metcalf
2017 Supporter

Posts: 13094
Joined: 15 May 2006
Location: Berlin

### Re: Troika Sudokus. A challenge.

Mathimagics wrote: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.

Mathimagics
2017 Supporter

Posts: 1870
Joined: 27 May 2015
Location: Canberra

### Re: Troika Sudokus. A challenge.

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

m_b_metcalf
2017 Supporter

Posts: 13094
Joined: 15 May 2006
Location: Berlin

### Re: Troika Sudokus. A challenge.

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!

Mathimagics
2017 Supporter

Posts: 1870
Joined: 27 May 2015
Location: Canberra

### Re: Troika Sudokus. A challenge.

Mathimagics wrote: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

m_b_metcalf
2017 Supporter

Posts: 13094
Joined: 15 May 2006
Location: Berlin

### Re: Troika Sudokus. A challenge.

.
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, minimal1..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, minimal1..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, minimal1........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, minimal1......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?)

Mathimagics
2017 Supporter

Posts: 1870
Joined: 27 May 2015
Location: Canberra

### Re: Troika Sudokus. A challenge.

Mathimagics wrote:.

(Mike, can you verify these?)

Pefectly Perfect (how could it be otherwise?)!

Mike

m_b_metcalf
2017 Supporter

Posts: 13094
Joined: 15 May 2006
Location: Berlin

### Re: Troika Sudokus. A challenge.

Hi, Mathimagics!
Mathimagics wrote: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, minimal1..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, minimal1..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, minimal1........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, minimal1......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
Serg
2018 Supporter

Posts: 785
Joined: 01 June 2010
Location: Russia

### Re: Troika Sudokus. A challenge.

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
2017 Supporter

Posts: 1870
Joined: 27 May 2015
Location: Canberra

### Re: Troika Sudokus. A challenge.

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.26....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`

Mathimagics
2017 Supporter

Posts: 1870
Joined: 27 May 2015
Location: Canberra

Next