4 ms·

> 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

> 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 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...

tedmiston 9y ago
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.
kybernetikos 9y ago
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/ 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.
- fenomas 9y ago
  > 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.

tedmiston 9y ago

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.

kybernetikos 9y ago

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/ 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.

fenomas 9y ago
> 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.