Solving Every Sudoku Puzzle (2006)

Then check out perhaps the worst sudoku solver, which works by translating the puzzle to a series of Python package requirements and then asking the package manager to resolve them: https://github.com/konstin/sudoku-in-python-packaging

That is an interesting post. However, a much more interesting challenge is solving larger Sudoku puzzles, as 9x9 is (as evidenced in the pos) a trivial problem to solve. 16x16 starts to get somewhat interesting, but at 25x25 it gets really interesting. Most solvers are trivially extensible to larger sizes, making it quite easy to benchmark.

In my testing, 25x25 Sudokus are algorithmically challenging. Solving times for a naive but well-tuned algorithm with reasonable heuristics can easily be on the order of an hour for a single puzzle. A smart system with advanced reasoning can be many orders of magnitude faster.

    const randomNumbers = random ? [1, 2, 3, 4, 5, 6, 7, 8, 9].sort(() => Math.random() - 0.5).sort(() => Math.random() - 0.5) : null

This guy under Common Lisp would shine.

> As computer security expert Ben Laurie has stated, Sudoku is "a denial of service attack on human intellect". […] I thought maybe this would demonstrate that [my wife doesn’t] need to spend any more time on Sudoku.

The same could be said about every logic puzzle, or other types of puzzles.

People don't do them so actually solve any sort of new problem, or achieve some sort of productivity.

The same reason people don’t jog to get from point A to point B, or to learn how to get around more quickly.

Logic puzzles are exercising parts of our brain that don’t get exercised regularly.

It was a denial of service attack, not in the sense of soaking up my brain cells solving puzzles, but in causing me to devise and program my own solver. (In Java, text console only.) Once I wrote a solver, I felt as if I had solved all puzzles.

Then I got interested in devising puzzles with multiple solutions. Not too difficult. But making a few puzzles with two solutions was fun.

Experiment_203(

   " 1 . . | 2 . 8 | . . 9 "+
   " . 8 . | . . . | . 3 . "+
   " . . 7 | . 1 . | 2 . . "+
   //------+-------+--------
   " 4 . . | 1 2 3 | . . 6 "+
   " . . 2 | 4 5 6 | 9 . . "+
   " 6 . . | 7 8 9 | . . 4 "+
   //------+-------+--------
   " . . 6 | . 4 . | 8 . . "+
   " . 2 . | . . . | . 7 . "+
   " 9 . . | 8 . 2 | . . 1 "
  ),

// Solution #1. Found in 0 days 00:00:00.004.

// 245 boards examined so far.

   1 6 5 | 2 3 8 | 7 4 9
   2 8 4 | 6 9 7 | 1 3 5
   3 9 7 | 5 1 4 | 2 6 8
   ------+-------+------
   4 7 9 | 1 2 3 | 5 8 6
   8 3 2 | 4 5 6 | 9 1 7
   6 5 1 | 7 8 9 | 3 2 4
   ------+-------+------
   7 1 6 | 3 4 5 | 8 9 2
   5 2 8 | 9 6 1 | 4 7 3
   9 4 3 | 8 7 2 | 6 5 1

// Solution #2. Found in 0 days 00:00:00.001.

// 287 boards examined so far.

   1 6 5 | 2 3 8 | 7 4 9
   2 8 4 | 9 6 7 | 1 3 5  // <-- 9 6 7 instead of 6 9 7
   3 9 7 | 5 1 4 | 2 6 8
   ------+-------+------
   4 7 9 | 1 2 3 | 5 8 6
   8 3 2 | 4 5 6 | 9 1 7
   6 5 1 | 7 8 9 | 3 2 4
   ------+-------+------
   7 1 6 | 3 4 5 | 8 9 2
   5 2 8 | 6 9 1 | 4 7 3  // <-- 6 9 1 instead of 9 6 1
   9 4 3 | 8 7 2 | 6 5 1


   2 total solutions found.
   304 total boards examined.
   Total time 0 days 00:00:00.041.

Then I got to looking at difficult puzzles on the web. Apparently AI escargot is the world's most difficult. (And the site http://www.aisudoku.com/index_en.html says I can't publish the board). So I'll only publish the stats of applying my solver to it.

  Solution #1.  Found in 0 days 00:00:00.029.
  3,906 boards examined so far.

  1 total solutions found.
  7,832 total boards examined.
  Total time 0 days 00:00:00.085.

Crossword puzzles were the big fad puzzle in the 1920s.

>denial of service attack on human intellect

Sounds like social media feeds these days

You'd appreciate "Every 5x5 Nonogram": https://news.ycombinator.com/item?id=44140918