search

kaityo256 / minlex

Show the minlex canonical order form of the given Sudoku grid.
MIT License
4 stars 2 forks source link

Problem minlexing solved or nearly solved sudokus #3

Open 1to9only opened 1 year ago

1to9only commented 1 year ago

I tried the minlex tool with these sudokus

..9......5...8.2..4...2..9..1.3...6..8.6....7.5....9..6.873.......1.65......4.7.. sudoku
829461375567983241431527698714359862983612457256874913648735129372196584195248736 solution
...461375567983241431527698714359862983612457256874913648735129372196584195248736
..9461375567983241431527698714359862983612457256874913648735129372196584195248736
.29461375567983241431527698714359862983612457256874913648735129372196584195248736

On Windows I get these results

........1.....2.3..14.5.2........4673...48...7..2.......3......1.6....9398..75...
999999999999999999999999999999999999999999999999999999999999999999999999999999999
...123456124567389563489721251846937376295814489731265618972543745318692932654178
999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999

Another minlexer I also use is from https://github.com/dclamage/SudokuClassicMinLex which gives these results

........1.....2.3..14.5.2........4673...48...7..2.......3......1.6....9398..75...
123456789457189236698237541245713968386594127719862354531948672862371495974625813
...123456124567389563489721251846937376295814489731265618972543745318692932654178
..1234567253678491647159832195483276732516984864927153316892745429765318578341629
.12345678346728159587961342169457823423186795758293416231879564674532981895614237
kaityo256 commented 1 year ago

Hi @1to9only

Thank you for your report. But I cannot reproduce it.

Here are the results on Ubuntu (on WSL2) and Mac.

$ cat test.txt
..9......5...8.2..4...2..9..1.3...6..8.6....7.5....9..6.873.......1.65......4.7..
........1.....2.3..14.5.2........4673...48...7..2.......3......1.6....9398..75...

$ ./minlex test.txt
000000001000002030014050200000000467300048000700200000003000000106000093980075000
000000001000002030014050200000000467300048000700200000003000000106000093980075000

It shows the identical result.

Can you tell us about your execution environment, especially your compiler and compile options?

P.S. I have modified the code to accept periods instead of zeros.

1to9only commented 1 year ago

Hello @kaityo256 Have you tried minlexing:

$ cat test.txt
..9......5...8.2..4...2..9..1.3...6..8.6....7.5....9..6.873.......1.65......4.7..
829461375567983241431527698714359862983612457256874913648735129372196584195248736
...461375567983241431527698714359862983612457256874913648735129372196584195248736
..9461375567983241431527698714359862983612457256874913648735129372196584195248736
.29461375567983241431527698714359862983612457256874913648735129372196584195248736

I run minlex.exe on Windows 10 64-bit. I dont have g++ installed at the moment, but my notes show the program was built as follows:

g++.exe -c -static-libgcc -static-libstdc++ -Ofast -std=c++11 -march=native -Wall -Wextra minlex.cpp
g++.exe -flto -Ofast -s -static -static-libgcc -static-libstdc++ -Wall -Wextra -o minlex.exe minlex.o

Thanks for taking the time to look into this.

kaityo256 commented 1 year ago

Hello @1to9only

I have tried the following and reproduced the problem you reported on Windows, Linux, and Mac.

$ cat test.txt
..9......5...8.2..4...2..9..1.3...6..8.6....7.5....9..6.873.......1.65......4.7..
829461375567983241431527698714359862983612457256874913648735129372196584195248736
...461375567983241431527698714359862983612457256874913648735129372196584195248736
..9461375567983241431527698714359862983612457256874913648735129372196584195248736
.29461375567983241431527698714359862983612457256874913648735129372196584195248736

$ ./minlex test.txt
000000001000002030014050200000000467300048000700200000003000000106000093980075000
999999999999999999999999999999999999999999999999999999999999999999999999999999999
000123456124567389563489721251846937376295814489731265618972543745318692932654178
999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999

This is obviously a bug. Thanks for reporting it. The code was written so long ago that I have completely forgotten its contents and it may take some time to fix it.

Stay tuned.

1to9only commented 1 year ago

Here is another puzzle (already in minlex format) which shows the minlex bug.

$ cat test.txt
..1..2..3.2..3..4.3..5..2....2.5...4.6.7..8..9....8.5...8.1...9.9.6...7.1....93..
$ ./minlex test.txt
999999999999999999999999999999999999999999999999999999999999999999999999999999999

The puzzle is already in minlex format, so the output should be same as the puzzle.

kaityo256 commented 1 year ago

Hi @1to9only

Thank you for your report and sorry for my late reply. I confirmed that the output is not correct. It is obviously a bug of my code. I will find time to fix it.