Pencilmark Sudoku

Programs which generate, solve, and analyze Sudoku puzzles

Pencilmark Clue Counting

Postby Mathimagics » Tue Nov 19, 2019 8:24 am

tdillon wrote:One way to understand what's different is to look at how many propositional variables are known to the solver at the start after elimination in visible cells and propagation of singles. For the hardest Sudoku this is usually in the vicinity of 500 out of 729, with 425 as the lowest I've seen. For pencilmark Sudoku Mladen has shown this can be at least as low as 92 out of 729.


Let's label the number of clues (eliminated candidates) in the base puzzle as NC, the number after singles propagation NC(1), and the number of clues after both pairs and singles propagation NC(2).

Note that I don't include locked candidates here, just basic naked/hidden singles and pairs.

I tested Mladen's impressive list of 144,242 puzzles with NC = 92, and found:

  • 14,654 puzzles with NC(1) = 92
  • 3,616 puzzles with NC(2) = 92
User avatar
Mathimagics
2017 Supporter
 
Posts: 1495
Joined: 27 May 2015
Location: Canberra

90 and 91 clue Pencilmark Sudoku

Postby tdillon » Thu Dec 26, 2019 5:05 am

Hi all,

I haven't seen any recent discussion of low clue Pencilmark Sudoku following Mladen's 92-clue puzzles, so maybe these are new records?

Look here (https://github.com/t-dillon/pencilmark_sudoku) for 20 90-clue puzzles (639 candidates) and 365 91-clue puzzles (638 candidates).

Some of these puzzles are "close" to each other, but I haven't tried to group them in distinct islands or exhaustively explore what else is close by.

Tom
tdillon
 
Posts: 42
Joined: 14 June 2019

Re: Pencilmark Sudoku

Postby dobrichev » Thu Dec 26, 2019 8:57 am

Hi Tom,

Congratulations for the new record!

I confirm the published 20 90-clue pencilmark-only puzzles are valid and essentially different.

I see most of them have different solution grids.
Here is the distribution by solution. #puzzles, minlex grid
Hidden Text: Show
Code: Select all
      1 123456789456789123789132546234897651695314278817265394348571962561928437972643815
      1 123456789456789123789132564248591637537864291691327845374618952812945376965273418
      1 123456789456789123798132546237615894584397261961824375312948657645271938879563412
      1 123456789456789123798132546271943658385267914649815372534621897867594231912378465
      1 123456789456789123798132546279564831534821697681397254312975468867243915945618372
      1 123456789456789123798132564217948635384615297569273418631597842872364951945821376
      1 123456789456789123798213564264597318387162945915834672542971836679328451831645297
      1 123456789456789123798213654231894576564327891987561342349178265672935418815642937
      4 123456789456789123897231645234567918561892437978314562349678251615923874782145396
      1 123456789456789132789213456248675391615394827937128564372561948591842673864937215
      1 123456789456789132789213456275168394394527861861934527518642973637891245942375618
      2 123456789456789132789213645237561498564892371891347256315924867678135924942678513
      2 123456789456789132789213645261345978834971526975628314347592861512867493698134257
      1 123456789456789132789213645297564813561328974834971256318695427642837591975142368
      1 123456789456789132789213654261348975534971826978625341347192568695834217812567493
dobrichev
2016 Supporter
 
Posts: 1779
Joined: 24 May 2010

Re: 90 and 91 clue Pencilmark Sudoku

Postby tarek » Thu Dec 26, 2019 9:37 am

tdillon wrote:Look here (https://github.com/t-dillon/pencilmark_sudoku) for 20 90-clue puzzles (639 candidates) and 365 91-clue puzzles (638 candidates)


Well done on a fantastic effort. I attempted a while ago with a basic strategy and limited resources to attempt 630+ candidates. the attempts were short lived as the results were disappointing. Here are my best attempts in case somebody has any use for them. (Note: Each 729 character line puzzle ends with a ",0xxx" that represents the number of candidates in each line)

625 to 628 candidates: Show
12345.78912345.78912345.78912345678912345678912345678912....7..123.567891234567.912345.78912345..89123456789123456789123456.8.1234567891234567.91234567891234567891..4..7.912345.789..3...7.912345678912345.7891234567.91.....7...23456789.234.67.9123456789123456789123456789.2345678912345678.123456789123456789123456789123456789123456789123456789..3456.8912.45678912345678912345678912.4567.9.23456.89123456789123456789123456789..34567891234567891234567891.3456789123.56789123.56789123456789123456789123.5..8...3..6...123456789123.56.8.123.56.891.3......123.56.89123..6..9123456789.2345678...345678912345678912345678912345678912.45678912.4567891.3456789123456789123456789..3..678912345678912345678912345678912....789123.567891.3.56789,0625
12345.78912345.78912345.78912345678912345678912345678912....7..1234567891234567.912345.78912.4...8912345678912345678912345678.123456789123456789.2345678.1234567891..4..7.912345.789........9123456789.2345.7891234567.91.....7.9123456789.234.67.91234567891234567891234567891234567891234567891234567891234567891234567891234567.912345678912.456789..3456.89123456789123456789123456.8912.4567.9.23456.89123456789123456789123456789..34567891234567891234567891.3456789123456789123456789123456789123456789123.56.8.1.3..6.89123456789123.56.8.123.56.891........123.56.891.3..6..912345678912345678...3456789123456789.2345678912345678912345678912.456.891234567891.3456789123456789.....678912345678912345678912345678912....789123456789123.56789,0628
12345.78912345.789123.....912345.78912345678912345678912....7..123.567891234567.912345.78912345.789123456789123456789123456.8.1234567891234567.91234567891234567891..4..7.912345.789......7.912345678912345.789123456789......7...23456789.234.67.9123456789123456789123456.89.2345678912345678.1234567891234567891234567891234567.91234567891234567891.3456.89123456789123456789123456.8912.4567.9.23456.89123456789123456789123456789123456789123456789123456789123456789123456789123.567891234567891.34..7..123.5.78...3..6..9123456789123.5678.123.567891.3...7..123.56789123..67.9123456789.2345678.1.3456789123456789.2345678912345678912.45678912.4567891.34567891234567891234567891.3..67891234567891234567891234.678912....789123.567891.3.56789,0625
12345.78912345.78912345.789123.56789123456789123.5678912....7..123.56789123.567.912345.78912345.78912345678912345678912345678.1234567.91234567.91234567891234567891..4..7.912345.789..3.....9123456789.2345.7891234567.91.....7.9.23456789.234.67.912345678912345678912345678912345678912345678912345678912345678912345678912345678912345678912.456789..3456.8912345678912345678912345678912.4567.9.23456.89123456789123456789123456789..3456789123456789123456789123456789123.56789123.56789123456789123456789123.5..8.1.3..6...123456789123456.8.123.56.891........123.56.89123..6..912345678912345678...3456789123456789.2.45678912345678912.4567891234567891.3456789123456789123456789..3..67891234567891234567891234.678912....789123.567891.3.56789,0625
12345.78912345.789123.....9123.5678912345678912345678912....7..1234567891234567.912345.78912.4...89123456789123456789123456789123456789123456789.234.678.1234567891..4..7.912345.789..3.....9123456789.2345.789.234567.91.....7.9123456789.234.67.912345678912345678912345678912345678912345678912.45678912345678912345678912345678912345678912.4567891.3456.89123456789123456789123456.891234567.9.23456.891234567891234567891234567891.3456789123456789123456789123456789123.567891234567891.34567891.34..7..12345.78.1.3..6...12345678912345678.1234567891........123456789123..67.912345678912345678.1.3456789123456789.2.45678912345678912345678912.456.891234567891.345.7891.345.7891.3..67891234567891234567891234.678912....789123456789123.56789,0625
123456789123456789123.....912345.78912345678912345678912....7..1234567891234567.912345678912.4...89123456.89123456789123456.8.123456789123456789.2345678.1234567891..4..7.912345.789........912345678912345.7891234567891.....7.9123456789.234.67.912345678912345678912345..89.2345678912345678912345678912345678912345678912345678912345678912.45678.1.345..8912345678912345678912345678912.4567.9123456.89123456789123456789123456789123456789123456789123456789123456789123.56789123456789123456789123456789123.56.8...3.....9123456789123.56.8.123.56.891.3......123.56.891.3..6..9123456789.2345678.1.3456789123456789.2345678912345678912.45678912.4567891234567891234567891234567891.3...7891234567891234567891234.678912....7891234567891.3.56789,0625
12345.78912345.789123.....912345678912345678912345678912....7..123.567891234567.912345.78912345.78912345678912345678912345678.1234567.91234567.91234567891234567891..4..7.912345.789..3.....912345678912345.7891234567.9......7.9.23456789.234.67.912345678912345.789123456.89.2345678912345678912345678912345678912345678912345678912345678912.45678.1.3456.89123456789123456789123456.8912.4567.9123456.891234567891234567891234567891234567891234567891234567891.345678912..56789123.56789123456789123456789123.5..8...3..6...123456789123.56.8.123.56.891.3...7..123.56.89123..6..91234567891234567891.3456789123456789.2345678912345678912.45678912.4567891.34567891234567891234567891.3..678912345678912345678912345678912....789123.567891.3.56789,0625
12345.789123456789123.....912345.78912345678912345678912....7..1234567891234567.912345.78912.4...89123456.8912345678912345678.1234567891234567891234567891234567891..4..7.912.45.789..3.....9123456789.2345.789.234567891.....7.9123456789.234567.912345678912345678912345678912345678912345678.12.4567891234567891234567891234567891234567891234567891.3456.891234567891234567891234567891234567.9.23456.891234567891234567891234567891.34567891234567891234567891.3456789123.56789123.567891234567891.34..7..12345.78...3......123456789123.5678.1234567891.3......123.56789123..67.912345678912345678.1.3456789123456789.2.45678912345678912.45678912.4567891.34567891.345.7891.345.7891.3..678912345678912345678912345678912....789123456789123.56789,0625
12345.789123456789123.....912345678912345678912345678912....7..1234567891234567.912345678912.4...89123456789123456789123456.8.123456789123456789.2345678.1234567891..4..7.912345.789......7.9123456789.2345.7891234567.9......7..123456789.234.67.912345678912345678912345678912345678912345678912345678912345678912345678912345678912345678912.45678.1.345..8912.45678912345678912345678912.4567.91234567891234567891.3456789123456789123456789123456789.2345678912345678912..567891234567891234567891.34..7..123.5678.1.3.....9123456789123.5678.123.567891.....7..123.567891.3..67.9123456789.2345678.1.345678912345678912345678912345678912.45678912.4567891234567891234567891234567891.3...7891234567891234567891234.678912....7891234567891.3.56789,0625
12345.789123456789123.....912345678912345678912345678912....7..12345678912345678912345.78912.4...89123456.89123456789123456.8.123456789123456789.2345678.1234567891..4..7.912345.789......7.91234567.9.2345.7891234567.91.....7...23456789.234.67.9123456789123456789123456789123456789123456789123456789123.5.7.912345678912345678912345678912.45678.1.3456.891234567891234567891234567891234567.9123456789123456789123456789123456789123456789123456789.23456789123456789123.56789123456789123456789123456789123.56.8.1.3.....9123456789123.56.8.123.56.891........123.56.891.3..6..912345678912345678.1.3456789123456789.2345678912345678912.45678912.4567891234567891234567891234567891.3..67891234567891234567891234.678912....789123456789123.56789,0626
123456789123456789123.....912345.78912345678912345678912....7..1234567891234567.912345678912.4...89123456.89123456789123456.8.123456789123456789.234567891234567891..4..7.912345.789......7.912345678912345.7891234567891.....7..123456789.234.67.912345678912345678912345..89.2345678912345678912345678912345678912345678912345678912345678912.45678.1.345..8912.45678912345678912345678912.4567.9123456.891234567891234567891234567891234567891234567891234567891.3456789123.567891234567891234567891.34..7..123.5678.1.3.....9123456789123.5678.123.567891........123.567891.3..67.9123456789.2345678.1.345678912345678912345678912345678912.45678912.4567891.34567891234567891234567891.3...78912345678912345678912345678912....7891234567891.3.56789,0625
12345.78912345.789123.....9123.56789123456789123.5678912....7..123.56789123.5678912345.78912.4...891234567891234567891234567891234567891234567891234567891234567891..4..7.912.45.789......7.9123456789.2345.789.234567.91.....7...23456789.234567.9123456789123456789123456.8912345678912345678912.4567891234567891234567891234567.912345678912..5678.1.3456.89123456789123456789123456.891234567.9123456.891234567891234567891234567891234567891234567891234567891.3456789123456789123.567891234567891.34..7..123.5.78.1.3..6..912345678912345678.1234567891........1234567891234.67.912345678912345678.1.3456789123.56789.2.45678912345678912.45678912.4567891.345678912345.78912345.7891.3..678912345678912345678912345678912....789123456789123456789,0625
123456789123456789123.....912345678912345678912345678912....7..1234567891234567.912345678912.4...8912345678912345678912345678.123456789123456789.2345678.1234567891..4..7.912345.789..3...7.9123456789.2345.7891234567.91.....7..123456789.234.67.912345678912345678912345.78912345678912345678912345678912345678912345678912345678912345678912.45678.1.345..8912.45678912345678912345678912.4567.912345678912345678912345678912345678912345.789123456789.234567891.345678912..567891234567891234567891.34..7..123.5678...3......12345678.123.5678.1234567891.3......123.567891.3..67.912345678912345678.1.3456789123456789.234567891234567891234567891234567891234567891.34.67891234567891.3...78912.45678912345678912345678912....789123456789123.56789,0626
123456789123456789123.....912345678912345678912345678912....7..1234567891234567.912345678912.4...8912345678912345678912345678.123456789123456789.234.678.1234567891..4..7.912345.789..3...7.9123456789.2345.7891234567.91.....7..123456789.234.67.912345678912345678912345.78912345678912345678912345678912345678912345678912345678912345678912.45678.1.345..8912.45678912345678912345678912.4567.912345678912345678912345678912345678912345.789123456789.234567891.345678912..567891234567891234567891.34..7..123.5678...3......12345678.123.5678.1234567891.3......1234567891.3..67.912345678912345678.1.3456789123456789.234567891234567891234567891234567891234567891.34.67891234567891.3...78912.45678912345678912345678912....789123456789123.56789,0626
123456789123456789123.....912345678912345678912345678912....7..1234567891234567.912345678912.4...8912345678912345678912345678.123456789123456789.2345678.1234567891..4..7.912345.789..3...7.9123456789.2345.7891234567.91.....7..123456789.234.67.912345678912345678912345.78912345678912345678912345678912345678912345678912345678912345678912.45678.1.345..8912.45678912345678912345678912.4567.912345678912345678912345678912345678912345.789123456789.234567891.345678912..567891234567891234567891.34..7..123.5678...3......12345678.123.5678.1234567891.3......123.567891.3..67.912345678912345678.1.3456789123456789.2345678912345678912.4567891234567891234567891.34.67891234567891.3...78912.45678912345678912345678912....789123456789123456789,0626
123456789123456789123.....912345678912345678912345678912....7..1234567891234567.912345678912.4...8912345678912345678912345678.123456789123456789.234.678.1234567891..4..7.912345.789..3...7.9123456789.2345.7891234567.91.....7..123456789.234.67.912345678912345678912345.78912345678912345678912345678912345678912345678912345678912345678912.45678.1.345..8912.45678912345678912345678912.4567.912345678912345678912345678912345678912345.789123456789.234567891.345678912..567891234567891234567891.34..7..123.5678...3......12345678.123.5678.1234567891.3......1234567891.3..67.912345678912345678.1.3456789123456789.2345678912345678912.4567891234567891234567891.34.67891234567891.3...78912.45678912345678912345678912....789123456789123456789,0626
1234567891234567891234567.912345678912.4567891234567891234567..12345678912345678912345678912.456.89.2345...91234567891234567891234567.91...567...23.5678.12345678912345.789.2..5...9........9123456789123456789123.56789.2....7.9.2..56789.23.567.91234567891234567891234567.9123456789123456789123456789123456789123.5678912345678912345678912345678912345678912345678912345678912345678912345678912345678912345.789123456789123456789..345.78912345678.1234567891234567891..456789123.5678912345678912345678...3.5......3.....9123456789123456789123.567891.3.5.7..1.3.5..8.123.56.89123456789.2345678...345...9..34567891234567891.34567891..45678.12.456.89123456789123456789123456789..34567891234567891234567891234567891..456789123456789123456789,0625
....56.8912.45678912..5678912.4567.9...4567.9123456789123456789.2.4567891..45.789123456.89123456.891234567891234567.91234567.9123..67.912345678912345678.1234567...23.56.891234.6.8912345.7891234567.91234567.91234567.912345678912345678912345678.123456.8912345.78912345.78912345678912345678.123456789123.56789123.56789123456789.23.5...912345.78.12345.789123456789123456789123.56789123.56789123.5678912..5.7..12345678912345.78912345.789123456789123456789123456789123.56789.23.5678912.456789.234567.91234567891234567891.34.67891.34567891.34.678912345678912.45678912.4567...23456789.234567891234567891.34567891.34567891.345678912345678912.45678912.456789123.56...123456.8.12345678.12345678.1.3456...123456789123456.8912345678912.4.....,0625
123456789123456789123456.8912345678912.4567891234567891234567..12345678912345678912345678912.456.89.23456.891234567891234567891234567891...567...23.5678.123456789123456789.2..5.7.9..3...7.91234567.9123456789.23.567.9......7...2..5.789.23.567.91234567891234567891234567.9123456789123456789123456789123456789123.5678912345678912345678912345678912345678912345678912345678912345678912345678912345678912345.78912345678912345.78.1234567891234567891234567891234567891.3456789123.56.8912345678912345.789..3.5......3......12345.789123456789123.56.891.3.5.7..1.3.5..8.123.56.89123456789.2345678...345...91.34567891234567891.34567891..45678.12.456.89123456789123456789123456789..34567891234567891234567.91234567891..456789123456789123456789,0625
....56.8912.45678912.45678912.4567.9...4.67.9123456789123456789.2.4567891..456789123456.89123456.891234567891234567.91234567.9123..67.912345678912345678.1234567....3.56.891234.6.8912345.7891234567.91234567.91234567.912345678912345678912345678.123456.8912345.78912345.78912345678912345678.123456789123.56789123.56789123456789.23.5...912345.78.12345.789123456789123456789123.56789123.56789123.5678912..5.7..12345678912345.78912345.789123456789123456789123456789123.56789.23.5678912.456789.234567.91234567891234567891.34.67891.34567891.34.678912345678912.45678912.4567...23456789.234567891234567891.34567891.34567891.345678912345678912.45678912.456789.23.56...123456.8.12345678.12345678.1.3456...123456789123456.8912345678912.45....,0625
....56.8912.45678912.45678912.4567.9...4.67.9123456789123456789.2.4567891..456789123456.89123456.891234567891234567.91234567.9123..67.912345678912345678.1234567....3.56.891234.6.8912345.7891234567.91234567.91234567.912345678912345678912345678.123456.8912345.78912345.78912345678912345678.123456789123.56789123.56789123456789.23.5...912345.78.12345.789123456789123456789123.56789123.56789123.5678912..5.7..12345678912345.78912345.789123456789123456789123456789123.56789.23.5678912.456789.234567.91234567891234567891.34.67891.34567891.34.678912345678912.45678912.4567...23456789.234567891234567891.34567891.34567891.345678912345678912.45678912.456789123.56...123456.8.12345678.12345678.1.3456...123456789123456.8912345678912.4.....,0625
....56.8912.45678912.45678912.4567.9...4567.9123456789123456789.2.4567891..45.789123456.89123456.891234567891234567.91234567.9123..67.912345678912345678.123456....23.56.891234.6.8912345.7891234567.91234567.91234567.912345678912345678912345678.123456.8912345.78912345.78912345678912345678.123456789123.56789123.56789123456789.23.5...912345.78.12345.789123456789123456789123.56789123.56789123.5678912..5.7..12345678912345.78912345.789123456789123456789123456789123.56789.23.5678912.456789.234567.91234567891234567891.34.67891.34567891.34.678912345678912.45678912.4567...23456789.234567891234567891.34567891.34567891.345678912345678912.45678912.456789.23.56...123456.8.12345678.12345678.1.3456...123456789123456.8912345678912.45....,0625
....56.8912.45678912.45678912.4567.9...4567.9123456789123456789.2.4567891..45.789123456.89123456.891234567891234567.91234567.9123..67.912345678912345678.1234567....3.56.891234.6.8912345.7891234567.91234567.91234567.912345678912345678912345678.123456.8912345.78912345.78912345678912345678.123456789123.56789123.56789123456789.23.5...912345.78.12345.789123456789123456789123.56789123.56789123.5678912..5.7..12345678912345.78912345.789123456789123456789123456789123.56789.23.5678912.456789.234567.91234567891234567891.34.67891.34567891.34.678912345678912.45678912.4567...23456789.234567891234567891.34567891.34567891.345678912345678912.45678912.456789123.56...123456.8.12345678.12345678.1.3456...123456789123456.8912345678912.4.....,0625
....56.8912.45678912.45678912.4567.9...4567.9123456789123456789.2.4567891..45.789123456.89123456.891234567891234567.91234567.9123..67.912345678912345678.123456....23.56.891234.6.8912345.7891234567.91234567.91234567.912345678912345678912345678.123456.8912345.78912345.78912345678912345678.123456789123.56789123.56789123456789.23.5...912345.78.12345.789123456789123456789123.56789123.56789123.5678912..5.7..12345678912345.78912345.789123456789123456789123456789123.56789.23.5678912.456789.234567.91234567891234567891.34.67891.34567891.34.678912345678912.45678912.4567...23456789.234567891234567891.34567891.34567891.345678912345678912.45678912.456789123.56...123456.8.12345678.12345678.1.3456...123456789123456.8912345678912.4.....,0625
....56.8912.45678912...678912.4567.9...4.67.9123456789123456789.2.45678912.456789123456.89123456.891234567891234567.91234567.9123..67.912345678912345678.1234567...23.56.891234.6.8912345.7891234567.91234567.91234567.912345678912345678912345678.123456.8912345.78912345.78912345678912345678.123456789123.56789123.56789123456789.23.5...912345.78.12345.789123456789123456789123.56789123.56789123.5678912..5.7..12345678912345.78912345.789123456789123456789123456789123.56789.23.5678912.456789.234567.91234567891234567891.34.67891.34567891.34.678912345678912.45678912.4567...23456789.234567891234567891.34567891.34567891.345678912345678912.45678912.456789123.56...123456.8.12345678.12345678.1.3456...123456789123456.8912345678912.4.....,0625
User avatar
tarek
 
Posts: 3537
Joined: 05 January 2006

Re: Pencilmark Sudoku

Postby m_b_metcalf » Thu Dec 26, 2019 10:04 am

I processed all of these (Tom's). Most are fairly easy. In the first batch of 20 there are a couple that aspire to hidden triplet, nothing more. However, in the second batch there are 42 that are above an SE rating of 5, and three, 59, 280 and 281, that might be as high as 9+.

Regards,

Mike

P.S. I looked at tarek's too, and only the third exceeds SE 5.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10786
Joined: 15 May 2006
Location: Berlin

Re: Pencilmark Sudoku

Postby tdillon » Thu Dec 26, 2019 8:28 pm

m_b_metcalf wrote:I processed all of these (Tom's). Most are fairly easy.

Indeed ... I haven't looked at them from the perspective of human-centric rating, but even with the simple techniques implemented in the solvers below many of the 90 clue puzzles are solved without any guessing:

Code: Select all
|low_clue/90_clue       | puzzles/sec|  usec/puzzle|   %no_guess|guesses/puzzle|
|-----------------------|-----------:|------------:|-----------:|-------------:|
|minisat_augmented_01   |    1,091.8 |       915.9 |       0.0% |       100.98 |
|_tdev_dpll_triad_scc_i |      847.9 |     1,179.4 |      38.1% |        12.69 |
|fsss2_locked           |    2,168.9 |       461.1 |       0.0% |       619.49 |
|tdoku                  |  137,498.8 |         7.3 |      15.0% |         4.83 |

I think it's almost axiomatic that puzzles approaching minimal cluefulness also tend to be easy. In such puzzles each clue needs to pull its weight by ruling out a large independent swath of the space, and this is at odds with the complex clue interactions that contribute to puzzle hardness.

Of course, "easy" depends on having the right tool kit. Vanilla 17 clue Sudoku are easy if a solver can exploit hidden singles, but hard if it can't. Something similar is operating with Mladen's previously posted list of low clue killers. They are easy for Minisat, but hard and extremely sensitive to heuristics for other solvers that can't quite connect the dots:

Code: Select all
|dobrichev_93_clue_hard | puzzles/sec|  usec/puzzle|   %no_guess|guesses/puzzle|
|-----------------------|-----------:|------------:|-----------:|-------------:|
|minisat_augmented_01   |      755.0 |     1,324.5 |       0.0% |       129.26 |
|_tdev_dpll_triad_scc_i |        0.0 |99,114,673.8 |       0.0% | 1,560,519.33 |
|fsss2_locked           |        0.5 | 1,898,407.2 |       0.0% | 1,815,772.12 |
|tdoku                  |        0.1 |17,486,087.6 |       0.0% |34,116,990.40 |

The 90 and 91 clue puzzles I found were the result of 60 processes running for 24 hours on a Threadripper 2990WX. I just finished another 24 hour search, but this time looking for hard puzzles instead of low-clue ones, where "hard" is defined as "causing lots of backtracking for Minisat averaged over 10 random permutations of the puzzle".

The resulting puzzles are pretty hard for all the solvers I've tested:

Code: Select all
|hard.gt35              | puzzles/sec|  usec/puzzle|   %no_guess|guesses/puzzle|
|-----------------------|-----------:|------------:|-----------:|-------------:|
|minisat_augmented_01   |        0.6 | 1,798,868.2 |       0.0% |    37,195.21 |
|_tdev_dpll_triad_scc_i |        0.0 |27,714,685.4 |       0.0% |   255,830.55 |
|fsss2_locked           |        1.8 |   553,853.5 |       0.0% |   320,814.63 |
|tdoku                  |        3.7 |   267,548.8 |       0.0% |   293,757.68 |

I'm curious what their SE ratings might be.
Last edited by tdillon on Thu Dec 26, 2019 9:20 pm, edited 1 time in total.
tdillon
 
Posts: 42
Joined: 14 June 2019

Re: Pencilmark Sudoku

Postby m_b_metcalf » Thu Dec 26, 2019 9:15 pm

tdillon wrote:I'm curious what their SE ratings might be.

Very impressive. It takes my humble program 2s on average to process each one, assuming uniqueness so stopping as soon as the solution is found. The indication is that they are all SE 10+.

Regards,

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10786
Joined: 15 May 2006
Location: Berlin

Re: Pencilmark Sudoku

Postby tarek » Thu Dec 26, 2019 9:45 pm

tdillon wrote:I just finished another 24 hour search, but this time looking for hard puzzles instead of low-clue ones, where "hard" is defined as "causing lots of backtracking for Minisat averaged over 10 random permutations of the puzzle".
The description is just terrifying :lol:. If Mini-sat struggled with these then I suspect they would be very difficult. The way tdillon describes the process reminds me of dukosu's Suexrat9.
User avatar
tarek
 
Posts: 3537
Joined: 05 January 2006

Re: Pencilmark Sudoku

Postby tdillon » Fri Dec 27, 2019 9:38 am

Kicked this off again for low clue, and have added a bunch more, including some newly discovered 89 clue puzzles.
Last edited by tdillon on Wed Jan 15, 2020 9:05 pm, edited 1 time in total.
tdillon
 
Posts: 42
Joined: 14 June 2019

Re: Pencilmark Sudoku

Postby tarek » Fri Dec 27, 2019 9:51 am

tdillon wrote:Kicked this off again for low clue, and have added a bunch more, including some newly discovered 89 clue puzzles.
Well done. We are now in the territory of "less than 10 naked singles equivalent" or the 640+ candidates, amazing!
User avatar
tarek
 
Posts: 3537
Joined: 05 January 2006

Re: Pencilmark Sudoku

Postby m_b_metcalf » Fri Dec 27, 2019 9:56 am

tdillon wrote:Kicked this off again for low clue, and have added a bunch more, including some newly discovered 89 clue puzzles.

Wow! Solved all in a trice (0.08s) and only the first two are harder than basic techniques.

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10786
Joined: 15 May 2006
Location: Berlin

Aaaand 88 ... do I hear 87?

Postby tdillon » Fri Dec 27, 2019 7:41 pm

After running overnight I've added a bunch more, including some 88 clue puzzles!!
Last edited by tdillon on Wed Jan 15, 2020 9:06 pm, edited 1 time in total.
tdillon
 
Posts: 42
Joined: 14 June 2019

Re: Pencilmark Sudoku

Postby dobrichev » Fri Dec 27, 2019 7:57 pm

10 88's from 7 different grids, that is amazing!

Is it possible that you are digging in a new local minimum or your method performs sufficiently wide (say, deep and randomized) search?

Surely your approach is extremely effective and now I am curious how far from the absolute minimum you are.
dobrichev
2016 Supporter
 
Posts: 1779
Joined: 24 May 2010

Re: Pencilmark Sudoku

Postby tdillon » Fri Dec 27, 2019 8:48 pm

dobrichev wrote:I am curious how far from the absolute minimum you are.

I'm curious as well. But to have an empirically grounded conjecture about the minimum we'd surely require a much greater investment of computing time.

It's definitely possible that I'm digging in local minima. The procedure started with 60 processes, with each keeping a pool of its 200 best puzzles. Within a process each iteration involved randomly drawing a puzzle, relaxing some clues, re-completing, minimizing, scoring, adding to the pool, and then ejecting the worst puzzle from the pool to keep a fixed size.

Given the way things were initialized, each process effectively had ~100 independent random seed puzzles. After running for a while most processes started finding at least a few 91 clue puzzles. Once I had a few hundred 91 clue puzzles I gathered these together and restarted the 60 processes using this group of puzzles as seeds. This helped accelerate the discovery of more low clue puzzles, but it also increased the likelihood that I'd be exploring a small number of local minima.

I'll check in the code so you can play around with it after I've had a chance to make it a little more presentable.
tdillon
 
Posts: 42
Joined: 14 June 2019

Re: Pencilmark Sudoku

Postby tarek » Fri Jan 10, 2020 8:18 pm

Does the software minimize (or shall I say maximize) puzzles?

I was wondering what would happen if we put our current hardest vanilla sudokus through that?

They can only get more difficult, correct?

Every added candidate to a given cell in vanilla would also add 20 candidates to the shared cells.

tarek
User avatar
tarek
 
Posts: 3537
Joined: 05 January 2006

PreviousNext

Return to Software

cron