1. 10
  1. 4

    Pleased they got into the “human-style” strategies toward the end. One of my long-ago on-the-train projects was a sudoku solver that would use only human strategies and give you a list of moves (with their rationale) at the end. It’s a harder coding problem, but much more satisfying when it works. :)

    1. 1

      Sounds very tough. How far did you get on that? Is the code live anywhere?

      To this day, one of the most impressive uses of tech in my opinion is Wolfram|Alpha circa 2010: I used their step-by-step integration countless times, never without thinking “how in the world did they do this”?

      1. 1

        I’m too embarrassed to post unfinished 15-year-old code :), but it isn’t as tough as it sounds. Sudoku fans have names like “naked pair” for each strategy, so coding the logic for each strategy is straightforward once you understand it. The rest is deciding which order to try strategies (easiest first!) and saving each board state and the details of the move that got you there.

        I never finished but my goal was to have it solve an arbitrary puzzle, then rate the difficulty based on the maximum strategy required to solve it. I was/am 99% sure that sudoku puzzle generators have this same logic, so they can rate them as “easy”, “medium”, and so on.

        1. 1

          If you play Good Sudoku on iOS, it can give you hints by applying human strategies, like “you missed a naked single” or whatever. It’s pretty addictive.

    2. 1

      I love writing solvers like this. It’s amazing how a slight change of ordering can change the runtime. I created a solver for Kakuro/cross sums and (IIRC) it went from nearly a minute to 20ms by adding some simple ordering heuristics.

      Basically before solving the puzzle I just assigned each cell a “priority” then selected which cell should be solved next, recalculated priorities and continued. https://gitlab.com/kevincox/crosssums/-/blob/63d9c2a4085d6713bf040ecb6c69f1dace273800/src/main.rs#L223. Looking at my priority function it appears that I preferred to first solve the cells with the least “influence”, breaking ties with (an approximation for) the number of possibilities for that cell. https://gitlab.com/kevincox/crosssums/-/blob/63d9c2a4085d6713bf040ecb6c69f1dace273800/src/main.rs#L209. Basically solve the “corners” of the puzzle first then work in. Which is satisfyingly much like humans tend to solve them.

      It seems like towards the end of their article they start apply more human-style logic. They are basically evolving towards an “expert system” with a brute-force solver as a fallback.

      1. 1

        i never really got into classic sudoku, but over the last couple of years i have been really enjoying variant sudokus, thanks to the cracking the cryptic youtube channel. (they started off solving cryptic crosswords live, hence the name, but really took off once they got into novelty sudoku)