The New Sudoku Players' Forum

by **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 ...

by **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".

by **Mathimagics** » Mon Jan 25, 2021 8:43 pm

Thanks, Mladen, I will think about that idea some more ...

by **JPF** » Mon Jan 25, 2021 10:05 pm

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

JPF

by **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....................................................................

by **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

by **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

by **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 ...

by **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.

by **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

by **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

by **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)

by **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

by **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

by **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]

The New Sudoku Players' Forum

MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles