3 ms·
Algorithm X can 'solve' puzzles with multiple solutions, so it doesn't guarantee a unique solution. Here's my implementation: http://dancing-links.herokuapp.co
by 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.