Troika Sudokus. A challenge.

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

Troika Sudokus. A challenge.

Postby m_b_metcalf » Sun Jan 09, 2022 8:56 pm

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13094
Joined: 15 May 2006
Location: Berlin

Re: Troika Sudokus. A challenge.

Postby Mathimagics » Mon Jan 10, 2022 5:29 pm

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! :o

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 ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1870
Joined: 27 May 2015
Location: Canberra

Re: Troika Sudokus. A challenge.

Postby m_b_metcalf » Mon Jan 10, 2022 5:47 pm

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13094
Joined: 15 May 2006
Location: Berlin

Re: Troika Sudokus. A challenge.

Postby Mathimagics » Tue Jan 11, 2022 5:19 am

Happy to advise that "Perfect Troikas" do exist ... 8-)

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1870
Joined: 27 May 2015
Location: Canberra

Re: Troika Sudokus. A challenge.

Postby Serg » Tue Jan 11, 2022 7:28 am

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.

Postby m_b_metcalf » Tue Jan 11, 2022 7:38 am

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

A stunning achievement! Well done!

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13094
Joined: 15 May 2006
Location: Berlin

Re: Troika Sudokus. A challenge.

Postby Mathimagics » Tue Jan 11, 2022 2:08 pm

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 ... :cry:

So, for other grids I will simply start with a smaller pool, adding increments until any perfect troikas are found.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1870
Joined: 27 May 2015
Location: Canberra

Re: Troika Sudokus. A challenge.

Postby m_b_metcalf » Tue Jan 11, 2022 8:07 pm

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13094
Joined: 15 May 2006
Location: Berlin

Re: Troika Sudokus. A challenge.

Postby Mathimagics » Tue Jan 11, 2022 9:52 pm

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!
User avatar
Mathimagics
2017 Supporter
 
Posts: 1870
Joined: 27 May 2015
Location: Canberra

Re: Troika Sudokus. A challenge.

Postby m_b_metcalf » Tue Jan 11, 2022 10:00 pm

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13094
Joined: 15 May 2006
Location: Berlin

Re: Troika Sudokus. A challenge.

Postby Mathimagics » Wed Jan 12, 2022 1:38 am

.
Bingo!! 8-)

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?)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1870
Joined: 27 May 2015
Location: Canberra

Re: Troika Sudokus. A challenge.

Postby m_b_metcalf » Wed Jan 12, 2022 9:35 am

Mathimagics wrote:.

(Mike, can you verify these?)

Pefectly Perfect (how could it be otherwise?)!

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13094
Joined: 15 May 2006
Location: Berlin

Re: Troika Sudokus. A challenge.

Postby Serg » Wed Jan 12, 2022 9:51 am

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, 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
Serg
2018 Supporter
 
Posts: 785
Joined: 01 June 2010
Location: Russia

Re: Troika Sudokus. A challenge.

Postby Mathimagics » Wed Jan 12, 2022 10:52 am

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
User avatar
Mathimagics
2017 Supporter
 
Posts: 1870
Joined: 27 May 2015
Location: Canberra

Re: Troika Sudokus. A challenge.

Postby Mathimagics » Wed Jan 12, 2022 2:02 pm

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
User avatar
Mathimagics
2017 Supporter
 
Posts: 1870
Joined: 27 May 2015
Location: Canberra

Next

Return to General