MinLex Puzzles

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

Re: MinLex Puzzles

Postby Mathimagics » Mon Jan 25, 2021 4:48 pm

dobrichev wrote:A solver for this puzzle can loop over the minlex grid catalogue represented as 81*9 compressed bitmap indexes. Circularly looping over cells with givens would give each iteration a chance for big leap over an index which has first matching value far ahead.

Of course first indexes will be all-zero or all-one and useless. Compression of the indexes is the real magic in such approach.

Mladen, can you add some flesh to this description? It's not clear to me how the catalogue is represented in this model ...

That could be because I'm an idiot, of course ... :?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby dobrichev » Mon Jan 25, 2021 7:57 pm

81 * 9 = 729 indexes, each of size 5,472,730,538 - if that is more clear. Waste of memory.

The topmost 2 and bottommost 2 grids of the whole catalog, with your puzzle at the bottom, are

Code: Select all
123456789456789123789123456214365897365897214897214365531642978642978531978531642
123456789456789123789123456214365897365897214897214365531642978648971532972538641
...
123456789457389621896217354268741593745893162931625847382164975574938216619572438
123456789457893612986217354274538196531964827698721435342685971715349268869172543
.............................................6......3.....8......5........9.72...


In penclimarks representation
Code: Select all
1.........2.........3.........4.........5.........6.........7.........8.........9...4.........5.........6.........7.........8.........91.........2.........3............7.........8.........91.........2.........3.........4.........5.........6....2.......1...........4.......3...........6.......5...........8.........9......7....3...........6.......5...........8.........9......7...2.......1...........4............8.........9......7...2.......1...........4.......3...........6.......5........5......3......1.............6......4......2...............9......7.........8......6......4......2...............9......7.........8.....5......3......1................9......7.........8.....5......3......1.............6......4......2.......
1.........2.........3.........4.........5.........6.........7.........8.........9...4.........5.........6.........7.........8.........91.........2.........3............7.........8.........91.........2.........3.........4.........5.........6....2.......1...........4.......3...........6.......5...........8.........9......7....3...........6.......5...........8.........9......7...2.......1...........4............8.........9......7...2.......1...........4.......3...........6.......5........5......3......1.............6......4......2...............9......7.........8......6......4............8.........9......7..1............5......3.......2...............9......7...2...........5......3.............8......6......4.....1........
...
1.........2.........3.........4.........5.........6.........7.........8.........9...4.........5..........7....3.............8.........9.....6....2.......1...............8.........9.....6....2.......1..............7....3..........5.......4......2............6..........8.......7.....4.....1............5............9..3............7.....4.........5...........8.........9..3......1.............6....2...............9..3......1.............6....2...........5...........8....4...........7....3.............8..2.......1.............6......4.............9......7......5........5..........7.....4.............9..3.............8..2.......1.............6........6...1................9....5..........7...2..........4.......3.............8.
1.........2.........3.........4.........5.........6.........7.........8.........9...4.........5..........7.........8.........9..3...........6...1.........2...............9.......8......6....2.......1..............7....3..........5.......4......2.............7.....4.........5......3.............8.1................9.....6.......5......3......1................9.....6......4............8..2.............7.......6...........9.......8.......7...2.......1...........4.......3..........5......3.........4......2............6..........8.....5............9......7..1..............7..1............5......3.........4.............9.2............6..........8........8......6...........91..............7...2...........5.......4.......3......

.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________.________._____________6___.________.________.________.________.________.__________3______.________.________.________.________._______________8_.________.________.________.________.________.____________5____.________.________.________.________.________.________.________.________________9.______________7___2_______.________.________.________
123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789.....6...123456789123456789123456789123456789123456789123456789..3......123456789123456789123456789123456789123456789.......8.123456789123456789123456789123456789123456789123456789....5....123456789123456789123456789123456789123456789123456789123456789123456789........9123456789......7...2.......123456789123456789123456789


Index values for your givens for the first 2 and last 2 grids. 1=matches, 0=doesn't match. Only they are using in finding all solutions.
Code: Select all
6 00...01
3 00...01
8 00...01
5 00...01
9 00...11
7 00...11
2 00...11

In the above table you should find all columns having 1 for all rows. In your case this is the last column = last grid.

Naive approach is doing bitwise AND on the uncompressed indexes of interest.

Better approach is to keep indexes in compressed form, start from root=grid0, loop trough indexes by leaving the root the same if index matches, or incrementing the root to the next matched grid for the current index.
If all indexes match particular root, then it is a solution - export it and increment root. Continue until root reaches end of some index.
At the moment I have no solution how to keep the indexes in compressed form efficiently. The only question an index should be able to answer is "Give me your first match for grid number >= N".
dobrichev
2016 Supporter
 
Posts: 1807
Joined: 24 May 2010

Re: MinLex Puzzles

Postby Mathimagics » Mon Jan 25, 2021 8:43 pm

Thanks, Mladen, I will think about that idea some more ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby JPF » Mon Jan 25, 2021 10:05 pm

What about a data structure like trie,binary search tree, etc..?

JPF
JPF
2017 Supporter
 
Posts: 4603
Joined: 06 December 2005
Location: Paris, France

Re: MinLex Puzzles

Postby dobrichev » Tue Jan 26, 2021 3:06 pm

BTW, hasn't this single-clue SudokuM puzzle unique solution? [Edit: It was already published in this post by Mathimagics on previous page.]

Code: Select all
.........
...8.....
.........
.........
.........
.........
.........
.........
.........


Or the number of clues should be doubled for uniqueness, like below?

Code: Select all
.........
..78.....
.........
.........
.........
.........
.........
.........
.........

Code: Select all
123456789457389621896217354268741593745893162931625847382164975574938216619572438
123456789457893612986217354274538196531964827698721435342685971715349268869172543
............8....................................................................
...........78....................................................................
Last edited by dobrichev on Tue Jan 26, 2021 7:26 pm, edited 1 time in total.
dobrichev
2016 Supporter
 
Posts: 1807
Joined: 24 May 2010

Re: MinLex Puzzles

Postby dobrichev » Tue Jan 26, 2021 4:00 pm

The single-given puzzle from the above post is proven valid.

Code: Select all
time ./gridchecker --catalog --extract --range 0- < grids.bin | grep -P "^.{12}8"

Total time 2086.250 seconds.
123456789457893612986217354274538196531964827698721435342685971715349268869172543

real   35m15.081s
user   45m12.109s
sys   6m9.042s
dobrichev
2016 Supporter
 
Posts: 1807
Joined: 24 May 2010

Re: MinLex Puzzles

Postby JPF » Tue Jan 26, 2021 4:30 pm

In the 416 bands, only 5 bands have the digit 8 in position 13:
Code: Select all
412   123456789457839612896271345
413   123456789457893612896127345
414   123456789457893612896127354
415   123456789457893612896217354
416   123456789457893612986217354

Only band 416 represents the first 27 digits of one (and only one) sudokuM.

Then, yes your 1-clue puzzleM is valid ; solution:
123456789457893612986217354274538196531964827698721435342685971715349268869172543

JPF
Last edited by JPF on Tue Jan 26, 2021 4:37 pm, edited 1 time in total.
JPF
2017 Supporter
 
Posts: 4603
Joined: 06 December 2005
Location: Paris, France

Re: MinLex Puzzles

Postby Mathimagics » Tue Jan 26, 2021 4:33 pm

dobrichev wrote:BTW, hasn't this single-clue SudokuM puzzle unique solution?

Code: Select all
.........
...8.....
.........
.........
.........
.........
.........
.........
.........


See this post from a couple of days ago: 5 x 1-clue puzzles

They were found in a scan of the catalog ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby dobrichev » Tue Jan 26, 2021 7:41 pm

Hi Mathimagics,

I missed this post while debating on coloring. Edited my announce.

I am sure once with Colin (and JPF?) we counted values per cell in the catalog. I could not find this discussion.
dobrichev
2016 Supporter
 
Posts: 1807
Joined: 24 May 2010

Re: MinLex Puzzles

Postby JPF » Tue Jan 26, 2021 9:22 pm

Mathimagics wrote:1-clue puzzles

Band 416 is the only grid with 1-clue puzzles. There are 5 cells with values that do NOT occur in any other ED (Minlex) grid, so there are 5 puzzles with unique solutions for just the 1 clue:

Code: Select all
 r2c4 = 8
 r2c5 = 9
 r2c6 = 3
 r7c5 = 8
 r8c6 = 9


I am probably missing something, but why does it work for r2c5 = 9?
For instance : Band 236
Code: Select all
123456789457198236689237451

JPF
JPF
2017 Supporter
 
Posts: 4603
Joined: 06 December 2005
Location: Paris, France

Re: MinLex Puzzles

Postby Mathimagics » Wed Jan 27, 2021 2:10 am

JPF wrote:I am probably missing something, but why does it work for r2c5 = 9? For instance : Band 236
Code: Select all
123456789457198236689237451


That's not a minlex band!

The real band 236, according to my catalog, is:
Code: Select all
123456789457189326698237541
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby Mathimagics » Wed Jan 27, 2021 5:13 am

2-clue SudokuM Puzzles

If my scan was done correctly, there are 80 minimal 2-clue puzzles.

In the list below, for each puzzle, the listing shows the two clues, the unique solution grid identified, and the band index for that grid.

2-clue Puzzles: Show
Code: Select all
r3c9=2, r4c4=3: 123456789457289163689173452245318697761594328938627514372861945596742831814935276 (bn 348)
r3c9=2, r7c8=3: 123456789457289163689173452245968317316745928978312645564897231731524896892631574 (bn 348)
r3c9=2, r8c2=3: 123456789457289163689173452245968317316745928978312645564897231731524896892631574 (bn 348)
r3c9=2, r7c4=3: 123456789457289163689173452246597318378621945915834627594368271762915834831742596 (bn 348)
r3c9=2, r7c5=3: 123456789457289163689173452246791835378562914915348627561934278792815346834627591 (bn 348)
r2c9=1, r6c7=2: 123456789457289631896137425264571893785392164931648257342815976578964312619723548 (bn 389)
r3c8=2, r4c9=3: 123456789457289631896137425264571893785392164931648257342815976578964312619723548 (bn 389)
r2c4=3, r3c6=2: 123456789457389612896172354285793146631524978749618523312945867568237491974861235 (bn 401)
r2c4=3, r4c5=9: 123456789457389612896172354285793146631524978749618523312945867568237491974861235 (bn 401)
r2c4=3, r5c2=3: 123456789457389612896172354285793146631524978749618523312945867568237491974861235 (bn 401)
r2c4=3, r5c6=4: 123456789457389612896172354285793146631524978749618523312945867568237491974861235 (bn 401)
r2c4=3, r6c2=4: 123456789457389612896172354285793146631524978749618523312945867568237491974861235 (bn 401)
r2c4=3, r6c5=1: 123456789457389612896172354285793146631524978749618523312945867568237491974861235 (bn 401)
r2c4=3, r9c6=1: 123456789457389612896172354285793146631524978749618523312945867568237491974861235 (bn 401)
r2c8=1, r3c6=2: 123456789457389612896172354285793146631524978749618523312945867568237491974861235 (bn 401)
r3c6=2, r3c7=3: 123456789457389612896172354285793146631524978749618523312945867568237491974861235 (bn 401)
r3c7=3, r4c5=9: 123456789457389612896172354285793146631524978749618523312945867568237491974861235 (bn 401)
r3c7=3, r6c2=4: 123456789457389612896172354285793146631524978749618523312945867568237491974861235 (bn 401)
r3c7=3, r6c5=1: 123456789457389612896172354285793146631524978749618523312945867568237491974861235 (bn 401)
r3c7=3, r9c6=1: 123456789457389612896172354285793146631524978749618523312945867568237491974861235 (bn 401)
r3c5=7, r4c4=1: 123456789457389612896271354285137946641928573739564128312645897568792431974813265 (bn 405)
r2c4=3, r8c5=2: 123456789457389612896271354285713946641892573739645128312564897568927431974138265 (bn 405)
r3c5=7, r9c4=1: 123456789457389612896271354285713946641892573739645128312564897568927431974138265 (bn 405)
r3c6=1, r4c4=7: 123456789457389612896271354285713946641892573739645128312564897568927431974138265 (bn 405)
r3c7=3, r8c5=2: 123456789457389612896271354285713946641892573739645128312564897568927431974138265 (bn 405)
r2c8=1, r4c9=3: 123456789457389612896271354289564173641937528735128946312645897568792431974813265 (bn 405)
r3c6=1, r9c4=2: 123456789457389612896721354231564978649178523785932146318645297562897431974213865 (bn 407)
r2c4=3, r7c7=4: 123456789457389612896721354231645978649817523785293146312978465568134297974562831 (bn 407)
r3c7=3, r7c7=4: 123456789457389612896721354231645978649817523785293146312978465568134297974562831 (bn 407)
r2c4=3, r9c5=2: 123456789457389621896217354268174593745938162931562847382641975574893216619725438 (bn 411)
r3c7=3, r9c5=2: 123456789457389621896217354268174593745938162931562847382641975574893216619725438 (bn 411)
r2c4=3, r7c4=7: 123456789457389621896217354268174593745938162931562847384725916579641238612893475 (bn 411)
r2c4=3, r7c5=2: 123456789457389621896217354268174593745938162931562847384725916579641238612893475 (bn 411)
r2c4=3, r7c8=1: 123456789457389621896217354268174593745938162931562847384725916579641238612893475 (bn 411)
r2c4=3, r8c3=9: 123456789457389621896217354268174593745938162931562847384725916579641238612893475 (bn 411)
r2c4=3, r8c4=6: 123456789457389621896217354268174593745938162931562847384725916579641238612893475 (bn 411)
r2c4=3, r8c5=4: 123456789457389621896217354268174593745938162931562847384725916579641238612893475 (bn 411)
r2c4=3, r8c9=8: 123456789457389621896217354268174593745938162931562847384725916579641238612893475 (bn 411)
r2c4=3, r9c5=9: 123456789457389621896217354268174593745938162931562847384725916579641238612893475 (bn 411)
r2c4=3, r9c8=7: 123456789457389621896217354268174593745938162931562847384725916579641238612893475 (bn 411)
r2c9=1, r8c8=3: 123456789457389621896217354268174593745938162931562847384725916579641238612893475 (bn 411)
r3c7=3, r7c4=7: 123456789457389621896217354268174593745938162931562847384725916579641238612893475 (bn 411)
r3c7=3, r7c5=2: 123456789457389621896217354268174593745938162931562847384725916579641238612893475 (bn 411)
r3c7=3, r7c8=1: 123456789457389621896217354268174593745938162931562847384725916579641238612893475 (bn 411)
r3c7=3, r8c3=9: 123456789457389621896217354268174593745938162931562847384725916579641238612893475 (bn 411)
r3c7=3, r8c4=6: 123456789457389621896217354268174593745938162931562847384725916579641238612893475 (bn 411)
r3c7=3, r9c5=9: 123456789457389621896217354268174593745938162931562847384725916579641238612893475 (bn 411)
r3c7=3, r9c8=7: 123456789457389621896217354268174593745938162931562847384725916579641238612893475 (bn 411)
r2c4=3, r4c6=1: 123456789457389621896217354268741593745893162931625847382164975574938216619572438 (bn 411)
r2c4=3, r7c4=1: 123456789457389621896217354268741593745893162931625847382164975574938216619572438 (bn 411)
r3c7=3, r4c6=1: 123456789457389621896217354268741593745893162931625847382164975574938216619572438 (bn 411)
r3c7=3, r7c4=1: 123456789457389621896217354268741593745893162931625847382164975574938216619572438 (bn 411)
r2c8=1, r9c9=3: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r2c9=2, r6c8=3: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c1=9, r3c5=1: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c1=9, r3c7=3: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c2=8, r3c7=3: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r4c2=7: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r5c5=6: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r5c7=8: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r5c9=7: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r6c1=6: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r6c2=9: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r6c3=8: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r6c4=7: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r6c6=1: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r6c7=4: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r6c8=3: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r6c9=5: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r7c2=4: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r8c1=7: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r8c2=1: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r8c3=5: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r8c4=3: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r8c8=6: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r9c1=8: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r9c2=6: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r9c7=5: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r9c8=4: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
r3c7=3, r9c9=3: 123456789457893612986217354274538196531964827698721435342685971715349268869172543 (bn 416)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby JPF » Wed Jan 27, 2021 11:44 am

nice work Mathimagics!
I am impressed with the speed of the catalog scan!

Mathimagics wrote:
JPF wrote:I am probably missing something, but why does it work for r2c5 = 9? For instance : Band 236
Code: Select all
123456789457198236689237451

That's not a minlex band!

I took my B236 band from an old wrong file ; unfortunately I didn't bother to check its "minlexity"...

JPF
JPF
2017 Supporter
 
Posts: 4603
Joined: 06 December 2005
Location: Paris, France

Re: MinLex Puzzles

Postby Mathimagics » Wed Jan 27, 2021 1:10 pm

JPF wrote:I am impressed with the speed of the catalog scan!

It was not really due to any ingenuity on my part! I had 16 cores going hard at it for 36 hours ... :?

By this time tomorrow I should have a complete list of the 3-clue puzzles. I do intend to stop there, as I have to give those cores back to running champagne's 17C search ... I promised to be back on duty by 1 Feb. ;)

Knowing all of the possible 1-, 2- and 3-clue puzzles is quite useful information. I've built a SudokuM solver, and it can handle 4+ clues fairly quickly, so a relatively fast minimality test is on offer. More on that later ...

Cheers
MM
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby Mathimagics » Wed Jan 27, 2021 1:39 pm

Mathimagics wrote:Since there is no obvious method for testing an incomplete grid for the minlex property, a solver for this puzzle type has to "filter" the solutions obtained from a normal solver, testing each solution for being in minlex form.

  • Since this testing is will inevitably involve many, many, calls to the grid minlex function, I strongly advise to use Michael Deverin's Minlex code


Just to demonstrate that point, here's my solver times for a tough puzzle, comparing times when linked with two different MinLex functions:


Code: Select all
P:  ..........................2...3..................................................

 a) nSolns = 1, et =  16.449s      [optimised Deverin]

 b) nSolns = 1, et = 287.772s      [GridChecker CanonForm]
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

PreviousNext

Return to General