Minlex Form: Min and Max Lists / Chaining

Programs which generate, solve, and analyze Sudoku puzzles

Phantom Bands

Postby Mathimagics » Thu Aug 20, 2020 1:11 am

.
Well, it's sure been a long time between posts for this thread ...

I ran a little experiment. I took the very first row2 minlex form (456789123), and enumerated all row 3 completions for which the resulting 3-rows could not be morphed into a minlex-better result.

To my surprise, there were 216 different solutions with this property, of which only 17 actually do occur (ED band #s 1 to 17 all have R2 = 456789123).

Code: Select all
123456789456789123789123456 B1
123456789456789123789123465 B2
123456789456789123789123546 *
123456789456789123789123564 B3
123456789456789123789123645 *
123456789456789123789123654 *
123456789456789123789132456 *
123456789456789123789132465 B4
123456789456789123789132546 B5
123456789456789123789132564 B6
123456789456789123789132645 *
123456789456789123789231456 *
123456789456789123789231465 *


The entries marked "B" correspond to the ED bands we know and love, the entries marked * do not, they are phantoms.

Every complete solution grid with this R1+R2, and, eg R3 = 789123546 (the first "phantom" band) can still be morphed by minlex canonicalisation into a lex-better form.

If I was looking at higher-end bands (ranks) then I'd be much less surprised, but with rank 1, and indeed so early (#3) in the set of candidates, it is a little perplexing ... :?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1578
Joined: 27 May 2015
Location: Canberra

Re: Phantom Bands

Postby Mathimagics » Thu Aug 20, 2020 2:06 pm

Mathimagics wrote:To my surprise, there were 216 different solutions with this property, of which only 17 actually do occur (ED band #s 1 to 17 all have R2 = 456789123).

And, not surprisingly, I had a bug in my band-minlex routine, it was not checking all possible transformations. :?

All is well ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1578
Joined: 27 May 2015
Location: Canberra

Re: Minlex Form: Min and Max Lists / Chaining

Postby coloin » Fri Aug 21, 2020 5:03 pm

I cant seem to find it but there was a posting where starting from row 1, 123456789
successive rows were added and minlexed, - to give these results

Row 1 - 1
Row 2 -
Row 3 - 416
Row 4
Row 5
Row 6
Row 7
Row 8
Row 9 - 5e9

Can anybody find the post - or have i dreamt it ? !
coloin
 
Posts: 1915
Joined: 05 May 2005

Re: Minlex Form: Min and Max Lists / Chaining

Postby Mathimagics » Fri Aug 21, 2020 7:11 pm

That looks like a table of # of ED grids (first N rows). So Row 2 would be 15 ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1578
Joined: 27 May 2015
Location: Canberra

Re: Minlex Form: Min and Max Lists / Chaining

Postby Mathimagics » Fri Aug 21, 2020 7:54 pm

Can someone point me to where I can find a list of the 416 bands with their gangster-44 index?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1578
Joined: 27 May 2015
Location: Canberra

Re: Minlex Form: Min and Max Lists / Chaining

Postby coloin » Fri Aug 21, 2020 7:58 pm

Ahhh its on page 1 ....!!
coloin
 
Posts: 1915
Joined: 05 May 2005

Re: Minlex Form: Min and Max Lists / Chaining

Postby Mathimagics » Fri Aug 21, 2020 8:31 pm

Silly me, I've had it open for days, but I never actually went all the way to the bottom! :lol:

Thanks!
User avatar
Mathimagics
2017 Supporter
 
Posts: 1578
Joined: 27 May 2015
Location: Canberra

Grid v Row Automorphisms

Postby Mathimagics » Thu Aug 27, 2020 6:40 am

There is a strong link between grid automorphism (GA) and (two) row automorphism (RA).

The number of potential minlex grid candidates (NGC) in Michael's minlex algorithm is NGC = 2 * NRP * NRA. Let MR = the minimum two-row rank, then these values are defined as:

  • NRP is the # of row-pairs having rank MR, max = 18
  • NRA is the # of row automorphisms fixed by MR, max = 18
  • NGC is # of minlex grid candidates, ie 2 x NRP x NRA, max = 2 x 18 x 18 = 648
  • NGA is the # of grid automorphisms, which is the number of candidates that produce identically scoring outcomes, ie the best minlex grid

Notes:
  • the max row-pair count of 18 comes from 9 row-pairs in the grid itself, and 9 in its transpose (col-pairs)
  • the doubling factor in NG comes from the fact that for any pair of rows, there are two candidates to consider, as we can swap the rows

For the MC grid, the rank is 1, every row-pair has rank 1, NRA = 18, NGC = 648, and every grid candidate leads to an identical outcome, ie NGA = 648.

Here is a table of the 35 most automorphic grids (NGA = 27 to 648). Each grid is tagged with NGA, MR, NRA, NRP and NGC:

Most Automorphic Grids: Show
Code: Select all
123456789456789123789123456231564897564897231897231564312645978645978312978312645 # 648  1 18  18 648
123456789456789123789123456267591834591834267834267591375618942618942375942375618 # 162  1 18  18 648
123456789456789123789123456231564897564897231897231564312978645645312978978645312 # 108  1 18  18 648
123456789456789123789123456231564978564978231978231564312645897645897312897312645 # 108  1 18   9 324
123456789457289163689173452245968317316745928978312645564897231731524896892631574 # 108  9  3  18 108
123456789456789123789123456231564978564897312897231645312978564645312897978645231 #  72  1 18  18 648
123456789457893612986217354274538196531964827698721435342685971715349268869172543 #  72 14  6   6  72
123456789456789123789123456231564897564897231897231564348672915672915348915348672 #  54  1 18   9 324
123456789456789123789123456231564897564897231897231564348915672672348915915672348 #  54  1 18   9 324
123456789456789123789123456234567891567891234891234567318642975642975318975318642 #  54  1 18  18 648
123456789456789123789123456234567891567891234891234567345678912678912345912345678 #  54  1 18   9 324
123456789456789123789123456234567891567891234891234567372615948615948372948372615 #  54  1 18   9 324
123456789456789123789123456235964817817235964964817235392641578578392641641578392 #  54  1 18   9 324
123456789456789123789123456267591348591834672834267915375618294618942537942375861 #  54  1 18  18 648
123456789456789123789123456267591834591834267834267591375942618618375942942618375 #  54  1 18  18 648
123456789456789123897231564231564978564978231789312645312645897645897312978123456 #  54  1 18   9 324
123456789456789231789312456231645978645978312978123645312564897564897123897231564 #  54  3  9   9 162
123456789457289163689173452235964817816735924974812635392641578568397241741528396 #  54  9  3  18 108
123456789456789123789123456231564897564897231978312645312645978645978312897231564 #  36  1 18   9 324
123456789456789123789123456231564978564978231978231564312897645645312897897645312 #  36  1 18   9 324
123456789456789123789123456231564978645897231897312564312645897564978312978231645 #  36  1 18   9 324
123456789456789123789123456231597864597864231864231597312678945678945312945312678 #  36  1 18  18 648
123456789456789123789123456231597864597864231864231597312948675675312948948675312 #  36  1 18  12 432
123456789456789123789123456231678945678945231945231678312597864597864312864312597 #  36  1 18   9 324
123456789456789123789123456231678945678945231945231678312894567567312894894567312 #  36  1 18   9 324
123456789456789123789123456231897564564231897978645312312978645645312978897564231 #  36  1 18   9 324
123456789456789123789123456231897645564312897978564231312978564645231978897645312 #  36  1 18   9 324
123456789456789123789132465231564978564978231978213546312645897645897312897321654 #  36  1 18   9 324
123456789456789123798132465231564897564897231879213546312645978645978312987321654 #  36  1 18   3 108
123456789456789231789123645231564897564897312897231456375618924618942573942375168 #  36  3  9  18 324
123456789456789231789123645231564978564897123897231564375942816618375492942618357 #  36  3  9  18 324
123456789457189236968372514291738465374265198685941327546813972732694851819527643 #  36  4  1  18  36
123456789457189326869372514214965873635847192978213465381624957546798231792531648 #  36  6  3  12  72
123456789456789123789123456231897564564231897897564231348672915672915348915348672 #  27  1 18   9 324
123456789456789231789312456231564978564978312978123564312645897645897123897231645 #  27  3  9   9 162

As one might expect, MR = 1 is the most common rank. A couple of entries stand out for me:

Code: Select all
123456789457289163689173452245968317316745928978312645564897231731524896892631574 # 108  9  3  18 108

This grid has rank 9, and all 108 grid candidates produce the same result (NGA = NGC).

Code: Select all
123456789457893612986217354274538196531964827698721435342685971715349268869172543 #  72 14  6   6  72

This is also has NGA = NGC, and has the maximum rank possible for a full grid (14). MR = 15 exists only in 2-row form, as we can't actually construct a grid that does not have some row-pair with a lower rank.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1578
Joined: 27 May 2015
Location: Canberra

Previous

Return to Software