5 ms·

Sudoku is only NP-complete if you generalize to arbitrary NxN boards. The standard 9x9 Sudoku gives a finite class of problem instances, so you could pre-genera

by Twisol 7y ago

Sudoku is only NP-complete if you generalize to arbitrary NxN boards. The standard 9x9 Sudoku gives a finite class of problem instances, so you could pre-generate a finite lookup table and get an O(1) algorithm on that class. It sounds like I'm nitpicking, but restrictions of any NP-Complete problem to a finite class automatically reduces the strength of the problem. To the point, an SQL statement on "small enough" SAT instances will probably also be rather fast.

chx 7y ago
> you could pre-generate a finite lookup table and get an O(1) algorithm on that class. If I remember my numbers right there are ~6.67 * 10 ^ 21 valid puzzles so if you want to generate and store that table, I am afraid your Amazon S3 bill will be a bit on the higher side. According to https://www.bernardmarr.com/default.asp?contentID=1846 https://www.bernardmarr.com/default.asp?contentID=1846 , the ‘Global Datasphere’ in 2018 reached 18 zettabytes. IOW, your little lookup table would consume all the storage in the world. So yes in theory you are right of course, it's doable but in practice it's not.
- hinkley 7y ago
  I'm not sure that's the finite lookup table he's talking about. Within the last year we talked about Peter Norvig's sudoku solver: https://norvig.com/sudoku.html https://norvig.com/sudoku.html He starts by generating a table where each cell is represented by a data structure that enumerates all of the legal values in that cell. The options. Then there is code that can find all the peers of a cell (same row, same column, same square). Turns out that most 'easy' and many 'moderate' puzzles can be solved by starting with a list of all cells with one option. For each cell: * solve the cell * for all peers, eliminate that value from their options * for all peers with one remaining option, recurse I believe that's quadratic time, and intuition tells me breadth-first converges faster. After that, Norvig reaches for brute force, under the theory that this has already gotten you so close to the solution that it's not worth implementing and debugging more complex constaint logic. But I think that despite his claims that Sudoku is a disease, I think this is a taunt; it simply encourages you to go into a more sophisticated process of elimination. Single elimination: Any option that only has one cell in a row, column or square: solved. Double elimination: If a pair of peers have only the same two options, then eliminate that option from all of their common peers. Solves nothing, but may solve other cells. Triple and Quadruple elimination: same thing, but progressively rarer. Quintuple elimination: I don't recall why, but it was asserted that since this is more than half of 9, any time this happens a simpler constraint is also true. I believe that covers all of the moderate difficulty puzzles and the occasional hard ones. From there there's a whole array of other constraints you can implement. You can either do it yourself as an exercise, or there are whole websites dedicated to these rules.
  - Twisol 7y ago
    This is fascinating in its own right, of course, but I was indeed referring to a literal finite lookup table, by appeal to the finitude of the 9x9 problem class only. You give a useful strategy for compacting the size of the lookup table though! (And really, isn't a function just a compressed lookup table? Often trading time for size.) Another theoretically interesting way to shrink the lookup table is to reduce all grids to the set of essentially different grids -- see Wikipedia for the details [0]. The upshot is a reduction in size to "only" 5,472,730,538 grids. You can then scan the set for a grid matching your input clues -- though, as noted, this trades time for size. [0] https://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerating_essentially_different_Sudoku_solutions https://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerat...
- Twisol 7y ago
  Sure. NP-completeness is utterly a matter of theory, I make no claims otherwise. SAT solving is such a powerful tool precisely because you can do so well on "small" (and often "average") solutions that it's an attractive target for practical instances of other problems -- despite its theoretical NP-completness. The poster I originally responded to was curious about the speed with which 9x9 Sudoku can be solved despite "its" NP-completeness, and my point was that it's because of the small restriction of the general, truly NP-complete problem, and not because of anything inherently special about the SQL-based solver.
- Retric 7y ago
  There are 9! × 722 × 27 × 27,704,267,971 valid puzzles but you can drop that to a 722 × 27 × 27,704,267,971 constant look up table by using a strict ordering rather than storing equivalent solutions in different cells. Basically there is only one unique solution to the top row under a different strict ordering. But, you can do a related mapping for a given problem to reduce the table by 9!.

by Twisol 7y ago

chx 7y ago

> you could pre-generate a finite lookup table and get an O(1) algorithm on that class. If I remember my numbers right there are ~6.67 * 10 ^ 21 valid puzzles so if you want to generate and store that table, I am afraid your Amazon S3 bill will be a bit on the higher side. According to https://www.bernardmarr.com/default.asp?contentID=1846 https://www.bernardmarr.com/default.asp?contentID=1846 , the ‘Global Datasphere’ in 2018 reached 18 zettabytes. IOW, your little lookup table would consume all the storage in the world. So yes in theory you are right of course, it's doable but in practice it's not.

hinkley 7y ago
I'm not sure that's the finite lookup table he's talking about. Within the last year we talked about Peter Norvig's sudoku solver: https://norvig.com/sudoku.html https://norvig.com/sudoku.html He starts by generating a table where each cell is represented by a data structure that enumerates all of the legal values in that cell. The options. Then there is code that can find all the peers of a cell (same row, same column, same square). Turns out that most 'easy' and many 'moderate' puzzles can be solved by starting with a list of all cells with one option. For each cell: * solve the cell * for all peers, eliminate that value from their options * for all peers with one remaining option, recurse I believe that's quadratic time, and intuition tells me breadth-first converges faster. After that, Norvig reaches for brute force, under the theory that this has already gotten you so close to the solution that it's not worth implementing and debugging more complex constaint logic. But I think that despite his claims that Sudoku is a disease, I think this is a taunt; it simply encourages you to go into a more sophisticated process of elimination. Single elimination: Any option that only has one cell in a row, column or square: solved. Double elimination: If a pair of peers have only the same two options, then eliminate that option from all of their common peers. Solves nothing, but may solve other cells. Triple and Quadruple elimination: same thing, but progressively rarer. Quintuple elimination: I don't recall why, but it was asserted that since this is more than half of 9, any time this happens a simpler constraint is also true. I believe that covers all of the moderate difficulty puzzles and the occasional hard ones. From there there's a whole array of other constraints you can implement. You can either do it yourself as an exercise, or there are whole websites dedicated to these rules.
- Twisol 7y ago
  This is fascinating in its own right, of course, but I was indeed referring to a literal finite lookup table, by appeal to the finitude of the 9x9 problem class only. You give a useful strategy for compacting the size of the lookup table though! (And really, isn't a function just a compressed lookup table? Often trading time for size.) Another theoretically interesting way to shrink the lookup table is to reduce all grids to the set of essentially different grids -- see Wikipedia for the details [0]. The upshot is a reduction in size to "only" 5,472,730,538 grids. You can then scan the set for a grid matching your input clues -- though, as noted, this trades time for size. [0] https://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerating_essentially_different_Sudoku_solutions https://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerat...
Twisol 7y ago
Sure. NP-completeness is utterly a matter of theory, I make no claims otherwise. SAT solving is such a powerful tool precisely because you can do so well on "small" (and often "average") solutions that it's an attractive target for practical instances of other problems -- despite its theoretical NP-completness. The poster I originally responded to was curious about the speed with which 9x9 Sudoku can be solved despite "its" NP-completeness, and my point was that it's because of the small restriction of the general, truly NP-complete problem, and not because of anything inherently special about the SQL-based solver.
Retric 7y ago
There are 9! × 722 × 27 × 27,704,267,971 valid puzzles but you can drop that to a 722 × 27 × 27,704,267,971 constant look up table by using a strict ordering rather than storing equivalent solutions in different cells. Basically there is only one unique solution to the top row under a different strict ordering. But, you can do a related mapping for a given problem to reduce the table by 9!.