Sudoku Solver and Generator | Hacker News Reader

Sudoku Solver and Generator

blog.ryanlevick.com

23 pointsitchyankles7 comments

If the goal is puzzle generation, a backtracking solver is the wrong tool. When it comes to logic puzzles of this sort (Sudoku, Nonograms, etc) people don't like backtracking. There's often even an explicit promise that the puzzles can be solved with "just logic, no guessing needed".

So what you want is a solver that uses only the kinds of (usually local) reasoning that a human would use. I don't have examples handy for Sudoku, but for Nonograms it would be things like this: https://webpbn.com/solving.html

An added benefit is that this allows you to figure out how difficult the puzzle is to solve. What forms of reasoning are needed? How many squares are solvable at any one time? A backtracking solver, especially one that doesn't use any sort of heuristics, can't give that.

Unless the problem space allows you to keep searching after a solution and discard it if a second one is found.

Heuristics are fast and natural, but hard to get right. They're handy to constrain the problem space though, but I would still apply backtracking just in case there's a valid single solution.

For my site I use a backtracker to find a large number of single solution puzzles (rather fast). Those are used as a test base for my "human" solver (pretty slow), which are used for scoring and difficulty levels. I find that it's a nice balance.

I love this.

Writing a sudoku solver is my go to for learning new programming languages. I just write the most basic algorithm: solve obvious squares with only one answer, then guess and repeat. Backtrack your guess if you end up in an unsolvable case.

It forces you to touch on enough different language features to really get comfortable. Arrays/basic data structures, calling recursive functions, deep copying stuff, fork/join style parallelization (and cancelation if you want).

It's just tricky enough to make you taste some of the code management features like classes and interfaces and the like too.

If you're trying to learn OOP vs. functional programming I think it's a great way to really feel the strength and pain points of both.

My first effort was the same but without backtracking. I would make a random guess at each step and propogate constraints on the board. If it ever got stuck as unsolvable, I would just start it over again. Most solved very quickly, the highest number of tries I had was something like 2100.

Peter Norvig, "Solving Every Sudoku Puzzle"[1] by constraint propagation.

[1] http://norvig.com/sudoku.html

No disrespect intended, but, uh... Prolog?

https://swish.swi-prolog.org/p/Boring%20Sudoku.swinb

/* Boring Prolog Sudoku. */ :- use_module(library(clpfd)).

puzzle(Vars) :-

    Vars = [
        A11, A12, A13, A14, A15, A16, A17, A18, A19,
        A21, A22, A23, A24, A25, A26, A27, A28, A29,
        A31, A32, A33, A34, A35, A36, A37, A38, A39,
        A41, A42, A43, A44, A45, A46, A47, A48, A49,
        A51, A52, A53, A54, A55, A56, A57, A58, A59,
        A61, A62, A63, A64, A65, A66, A67, A68, A69,
        A71, A72, A73, A74, A75, A76, A77, A78, A79,
        A81, A82, A83, A84, A85, A86, A87, A88, A89,
        A91, A92, A93, A94, A95, A96, A97, A98, A99],

    Vars ins 1..9,

    all_distinct([A11, A12, A13, A14, A15, A16, A17, A18, A19]),
    all_distinct([A21, A22, A23, A24, A25, A26, A27, A28, A29]),
    all_distinct([A31, A32, A33, A34, A35, A36, A37, A38, A39]),
    all_distinct([A41, A42, A43, A44, A45, A46, A47, A48, A49]),
    all_distinct([A51, A52, A53, A54, A55, A56, A57, A58, A59]),
    all_distinct([A61, A62, A63, A64, A65, A66, A67, A68, A69]),
    all_distinct([A71, A72, A73, A74, A75, A76, A77, A78, A79]),
    all_distinct([A81, A82, A83, A84, A85, A86, A87, A88, A89]),
    all_distinct([A91, A92, A93, A94, A95, A96, A97, A98, A99]),

    all_distinct([A11, A21, A31, A41, A51, A61, A71, A81, A91]),
    all_distinct([A12, A22, A32, A42, A52, A62, A72, A82, A92]),
    all_distinct([A13, A23, A33, A43, A53, A63, A73, A83, A93]),
    all_distinct([A14, A24, A34, A44, A54, A64, A74, A84, A94]),
    all_distinct([A15, A25, A35, A45, A55, A65, A75, A85, A95]),
    all_distinct([A16, A26, A36, A46, A56, A66, A76, A86, A96]),
    all_distinct([A17, A27, A37, A47, A57, A67, A77, A87, A97]),
    all_distinct([A18, A28, A38, A48, A58, A68, A78, A88, A98]),
    all_distinct([A19, A29, A39, A49, A59, A69, A79, A89, A99]),

    all_distinct([A11, A21, A31, A12, A22, A32, A13, A23, A33]),
    all_distinct([A41, A51, A61, A42, A52, A62, A43, A53, A63]),
    all_distinct([A71, A81, A91, A72, A82, A92, A73, A83, A93]),
    all_distinct([A14, A24, A34, A15, A25, A35, A16, A26, A36]),
    all_distinct([A44, A54, A64, A45, A55, A65, A46, A56, A66]),
    all_distinct([A74, A84, A94, A75, A85, A95, A76, A86, A96]),
    all_distinct([A17, A27, A37, A18, A28, A38, A19, A29, A39]),
    all_distinct([A47, A57, A67, A48, A58, A68, A49, A59, A69]),
    all_distinct([A77, A87, A97, A78, A88, A98, A79, A89, A99]).

That is the complete source code. It says: there are eighty-one numbers, all between one and nine inclusive, and they obey these twenty-seven applications of the Pigeonhole Principle. It will solve, validate, and generate Sudoku puzzles.

https://en.wikipedia.org/wiki/Constraint_logic_programming

http://pathwayslms.com/swipltuts/clpfd/clpfd.html

https://www.metalevel.at/prolog/clpfd

Reply on news.ycombinator.com