Hacker News Reader

Comment by tome | Hacker News Reader

I wonder how one creates puzzles like this (or indeed creates Sudoku puzzles). I can think of a few strategies

1. Lovingly hand craft them. Extremely labour intensive!

2. Generate random grids and repeatedly remove elements. If that leads to a puzzle with more than one solution, backtrack.

3. Add random elements to an empty grid. Eventually the grid will have one or zero solutions. If zero, backtrack. If one, stop.

Finally, classify the difficulty using some heuristic.

Does anyone have a better strategy? Is there some "analytic" property that guarantees uniqueness of solutions without resorting to some black box solver?

View on HN

> 3. Add random elements to an empty grid. Eventually the grid will have one or zero solutions. If zero, backtrack. If one, stop.

You can use that approach to make a multiplayer version of Sudoku. Start with an empty grid, and the players take turns filling in numbers. If a player on their turn is unable to fill in a number without making an on-the-board violation of the non-duplicate requirements for rows, columns, and sub-squares that player is eliminated.

Note that this can be played without a computer, because elimination happens when there is forced to be a duplicate actually on the grid.

If playing on a computer a more difficult multiplayer Sudoku is possible. After every move the computer checks to see if it is still possible to complete the grid according to Sudoku rules. If it is not, the player who made the last move is eliminated, and their move is erased.

Note that a similar approach can be used with many other single-person puzzles. For example, the 8 queens puzzle as a two-player game becomes the players take turns placing queens on a chess board, and the first player who places a queen that is attacked by an already placed queen loses.

As with Sudoku, two-player 8 queens could be done without a computer with the game terminating when a queen is placed on the board that is attacked, or it could be played with a computer with the game terminating when someone places a queen that makes it impossible for the game to end in a draw.

In early 2011 at work we were brainstorming mobile app ideas, and I suggested both of the above but there was not much interest. They have been on my "todo" list for whenever I get around to learning iOS and/or Android programming...but I've had "learn iOS programming" on my list since 2008, so I doubt I'm ever going to get around to it.

The source code to Simon Tatham's Puzzles is open-source, so you could see how at least one person does it.

https://www.chiark.greenend.org.uk/~sgtatham/puzzles/devel/ https://git.tartarus.org/?p=simon/puzzles.git;a=summary

I came to the conclusion that in any _decent_ puzzle there is unlikely to be an analytic short-cut that lets you create the puzzles. I've written a maths/maze game called Numplussed and wrote a level generator for it that was essentially random puzzle + brute force with a few optimisations. The level generator means that game has over 300,000 levels.

http://numplussed.com (free on iOS and Android)

The random+brute force approach turned out to be very interesting - the algorithm came up with puzzles that I never would have thought of if I was hand-crafting the levels. Or, say, if I had written a level generator with a specific sort of problem/solution in mind.

e.g. here's one of the hard levels that got generated: http://imgur.com/bqIvDCw . See here for the rules: https://www.youtube.com/watch?v=7D0i2Ce9Ujo

Sudoku puzzles are created both automatically and semi-automically / modified by hand to make them more elegant or enjoyable. I've bought a few sudoku puzzle books that usually discuss it like an art in the preface.

Oh and about designing for difficulty level — I think it's sort of reverse engineered from the fully solved state by continually removing numbers until it's more sparse / harder. I believe some of the apps do it by incubating puzzles then gathering aggregate statistics about how long it took people to solve then bucket < 5 min --> easy, 5-10 min --> medium, 10-15 --> hard, 15+ min --> evil, etc.

I've done this for Sudoku, cross sums and similar. Generally, I used a backtracking algorithm to fill an empty grid until a valid grid was found.

Assuming you want to control the level of difficulty of the puzzle generated, you want to incorporate the difficulty heuristics into the step-by-step filling-in algorithm (rather than just use them to score the puzzle after the fact).

Also, this probably should have been obvious, but at first I didn't do this: you get better control of the difficulty by basing your heuristics directly on the actual solving methods that people use. (If you don't somehow know already, you can, e.g., get a good book on solving sudoku which will enumerate the techniques and classify the difficulty as well. Once you understand the specific solving strategies for sudoku, you can probably generalize them to other logic puzzles.)

> Is there some "analytic" property that guarantees uniqueness of solutions without resorting to some black box solver?

Check out Knuth's Algorithm X. It's an elegant way of analyzing constraint-satisfaction sorts of problems (of which both Sudoku and the linked puzzle are examples).

https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X

edit: at least I think the linked puzzle is a constraint problem that could be modeled this way. But now that I consider it it's not so obvious...

From the page:

> "Algorithm X" is the name Donald Knuth used in his paper "Dancing Links" to refer to "the most obvious trial-and-error approach" for finding all solutions to the exact cover problem. Technically, Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm. While Algorithm X is generally useful as a succinct explanation of how the exact cover problem may be solved, Knuth's intent in presenting it was merely to demonstrate the utility of the dancing links technique via an efficient implementation he called DLX.

Algorithm X can 'solve' puzzles with multiple solutions, so it doesn't guarantee a unique solution.

Here's my implementation: http://dancing-links.herokuapp.com/ It's happy enough solving an empty sudoku grid (you can try it near the bottom of that page).

And yes, I think I could model this game as an exact cover problem (and therefore suitable for algorithm X) - you have a choice for each square to put a 1 in it or a 0 in it, you have the constraints that the rules tell you that you have. (e.g. col 1 must not be equal to col 2, and so on for all possible column pairings, and the same for rows, and col 1 has the same number of 1s as 0s for all columns, and col 1 does not contain more than 2 1s next to each other, etc...) It shouldn't be all that hard to modify my code above to solve it.

> Algorithm X can 'solve' puzzles with multiple solutions, so it doesn't guarantee a unique solution.

It can be used in a straightforward way to count how many solutions are possible for a given layout.

So for generating games, you could add numbers to an empty board until there are less than n solutions, then pick one of the solutions and add numbers from it until the solution is unique, then add a few more until it's overspecified to be a bit easier, etc.

I've been searching for this myself for some time, but either I don't know the proper search terms, or the knowledge is scattered such that the terminology isn't fixed.

This would be some sort of "constraint satisfaction" algorithm (ie, the same basic approach as used in Computer Algebra Systems(CAS) ). There are various approaches to these kinds of problems: someone above mentioned a backtracking algorithm.

Reply on news.ycombinator.com