isomorphic sudokus give different minlex (on Windows)

[1to9only]

Input (sudoku grids):

500000008003007040090000100000400020000580000004029000006200030010000500800000009
500000008003007040090000100000400020000910000004025000006200030010000500800000009

Output (minlex grids):

000000012000001304005000060003007100800400000020060000007009030040020000600800000
000000012000001304005000060070400000003008100200060000008009030060700000400020000

The program produces different minlex grid for the 2 sudoku grids, obtained from Patterns Game post here, and the minlex grids should be the same (as shown in the next post in the forum thread).

Replacing 0 with . for empty cell for better viewing.

Input (sudoku grids):

5.......8..3..7.4..9....1.....4...2....58......4.29.....62...3..1....5..8.......9
5.......8..3..7.4..9....1.....4...2....91......4.25.....62...3..1....5..8.......9

Output (minlex grids):

.......12.....13.4..5....6...3..71..8..4......2..6......7..9.3..4..2....6..8.....
.......12.....13.4..5....6..7.4.......3..81..2...6......8..9.3..6.7.....4...2....

There are several minlex tools available on GitHub and elsewhere, these give the same minlex grids for both grids:

dclamage's SudokuClassicMinLex program gives the same minlex for both grids:

.......12.....13.4..5....6...3..71...2..6....8..4.......7..9.3..4..2....6..8.....
.......12.....13.4..5....6...3..71...2..6....8..4.......7..9.3..4..2....6..8.....

The other programs also give the same minlex for both grids:

dobrichev's sudoku-minlexing-tool:

.......12.....3..4..2...56...7..8..5.1..6....9..4.......8..52...4..1....6..9.....
.......12.....3..4..2...56...7..8..5.1..6....9..4.......8..52...4..1....6..9.....

gsf's (Glenn Fowler) sudoku.exe downloaded from here:

.......12.....3..4..2...56...7..52...4..1....6..8.......9..7..5.1..6....8..4.....
.......12.....3..4..2...56...7..52...4..1....6..8.......9..7..5.1..6....8..4.....

There is another minlex tool here first announced here, but I've not used it as it is not a 'self contained' applicatiion, i.e. it requires a .NET core install.

Note: gsf's minlex is based on Michael Deverin's row-minlex code, improved on by dobrichev. dclamage's minlex (is written in Rust language) is more recent.

[kaityo256]

Hello @1to9only

Thank you for your report. But my code produces identical results for the input you provided.

$ cat test.txt
500000008003007040090000100000400020000580000004029000006200030010000500800000009
500000008003007040090000100000400020000910000004025000006200030010000500800000009

$ ./minlex test.txt
000000012000001304005000060003007100020060000800400000007009030040020000600800000
000000012000001304005000060003007100020060000800400000007009030040020000600800000

I confirmed the above behavior for g++ 9.4.0 on Ubuntu, g++ 4.8.5 on CentOS, and Apple clang 13.1.6 on Mac.

Could you specify the environment in which you got the incorrect result, especially the type and version of the compiler and the options?

[1to9only]

I'm using an old version downloaded a few years ago!! g++ -dumpversion says 8.1.0. Running on Windows 10. I'll switch to a newer version (maybe even 10.0.0) and try again. Thanks for looking into this.

[1to9only]

I switched to mingw-w64-gcc 10.3.1, then 12.1.1, with the same result (different minlexes)!

I then changed the #if 1 at line 31 to #if 0 to use the previous code for left_most_bit() function:

mbit left_most_bit(mbit v) {
  mbit vt = 0;
  while (v) {
    vt = v;
    v ^= v & (-v);
  }
  return vt;
}

Recompiled and retested, and BINGO! This works good, and I now get:

.......12.....13.4..5....6...3..71...2..6....8..4.......7..9.3..4..2....6..8.....
.......12.....13.4..5....6...3..71...2..6....8..4.......7..9.3..4..2....6..8.....

My earlier problem may have been due to use of intrinsics on Windows. Something to bear in mind if someone is building this project for Windows.

[kaityo256]

Hi @1to9only

Thank you for your reporting that the built-in function __builtin_clzl is the cause of the bug in mingw. I have reflected the corrections you have made on my repository. Thanks!