5 ms·

That looks interesting. Sudoku is a fairly useful constraint satisfaction problem/testbed to test neural networks architectures on, since the most general versi

That looks interesting. Sudoku is a fairly useful constraint satisfaction problem/testbed to test neural networks architectures on, since the most general version of sudoku is NP-complete. There was some interesting work a while ago that solved sudoku using spiking neural networks too [1] (Fig. 5) with some nice associated theory. [1] http://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.1003311 http://journals.plos.org/ploscompbiol/article?id=10.1371/jou...

bhaavan 9y ago
I thought Sudoku can be solved in constant time. It would be a O(9! * 9! ) or something, which is just a O(1), isn't it?
- dahart 9y ago
  A constant time solution in years or eons isn't very helpful. There are around 6.7e21 complete sudoku boards if you want to brute force enumerate them. https://en.m.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerating_all_possible_Sudoku_solutions https://en.m.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumer...
  - tom_mellior 9y ago
    > if you want to brute force enumerate them But you don't. Even what you might call "brute force" Sudoku solvers start from the given hints in the puzzle, which reduce the search space considerably. Given a set of Sudoku hints with a unique solution, you won't need "years or eons" with even a very simple solver.
    - dahart 9y ago
      Yes, of course you don't, I think you misunderstood my comment. The comment I replied to was asking about true brute force enumeration of all boards -- not a solver that uses inferences based on the hints -- he guessed that you only need 9! * 9! total attempts which implies enumerating all boards and picking the one that matches the initial hints. This is in fact a constant time solution like he guessed, but it is also intractable. A normal "very simple" solver of the kind you're talking about will solve the solution very quickly, in seconds or less, and it will also not be a constant time algorithm.
      - mamon 9y ago
        9!*9! is just little over 131 billion dashboards. checking correctnes (no number is repeated in row or column) is as simple as counting a sum in all boxes, rows and columns. Generation of all possible boards is little more complex but I can hardly see how it could take "eons" - with proper implementation (Apache Spark :P ) and reasonably powerful hardware (1000 CPU core cluster, ha! ha! ha!) it should run under 1 day and take just little over 13 TB of disk/RAM space :).
        dahart 9y ago
        9! * 9! is not the number of boards, that is a bad estimate. If you don't account for symmetries, rotations, re-numberings and other things, the number of boards is 6.7e21. Even if you could check a full board in a nanosecond (which you can't) enumerating that number would take more than 200,000 cpu-years. The paper linked to in the OP's article says: "Due to the sheer number of sudoku solution grids a brute force search would have been infeasible, but we found a better approach to make this project possible. Our software for exhaustively searching through a completed sudoku grid, named checker, was originally released in 2006. However, this first version was rather slow. Indeed, the paper [1] estimates that our original checker of late 2006 would take over 300,000 processor-years in order to search every sudoku grid." https://arxiv.org/pdf/1201.0749.pdf https://arxiv.org/pdf/1201.0749.pdf The estimate in the comment (9!*9!) seems to be implying a simple enumeration, not a complex strategy of symmetry-folding. But even if you do reduce the enumeration, the authors of that paper say their software requires 800 CPU years. I'm not making any claims about whether getting that down to a day might be possible, but I wish you good luck. By all means, show everyone how to do it with a proper implementation and a large cluster! ;)
      - tom_mellior 9y ago
        O(1) means bounded by a constant upper bound, not that every actual run of the program takes the exact same amount of time. Just like "simple quick sort is O(n^2)" does not mean that every invocation will take a quadratic amount of time. The parent's "can be solved in constant time" means the same thing, informally. Anyway, we are in agreement that enumerating all boards would be quite inefficient.
- daxfohl 9y ago
  "For the most general version of Sudoku" -- post doesn't detail what "general" means, but if the variable is board size, then it's O(N! * N!).
- trextrex 9y ago
  That's not really constant time is it? Constant time implies that the time taken to solve the problem is not a function of the input size (input in this case being the sudoku board). For a board size of 9x9 it's O(9!x9!). The paper which showed that the general case of Sudoku is NP-complete was apparently this one [1] (Linked from wikipedia) [1] http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf
- std_throwaway 9y ago
  Can we say that the number of possible states that the universe can assume is finite? Can we further conclude that everything that is possible must fit within the boundaries of the universe and therefore everything is either O(1) or unrealistic?

bhaavan 9y ago

I thought Sudoku can be solved in constant time. It would be a O(9! * 9! ) or something, which is just a O(1), isn't it?

dahart 9y ago
A constant time solution in years or eons isn't very helpful. There are around 6.7e21 complete sudoku boards if you want to brute force enumerate them. https://en.m.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerating_all_possible_Sudoku_solutions https://en.m.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumer...
- tom_mellior 9y ago
  > if you want to brute force enumerate them But you don't. Even what you might call "brute force" Sudoku solvers start from the given hints in the puzzle, which reduce the search space considerably. Given a set of Sudoku hints with a unique solution, you won't need "years or eons" with even a very simple solver.
  - dahart 9y ago
    Yes, of course you don't, I think you misunderstood my comment. The comment I replied to was asking about true brute force enumeration of all boards -- not a solver that uses inferences based on the hints -- he guessed that you only need 9! * 9! total attempts which implies enumerating all boards and picking the one that matches the initial hints. This is in fact a constant time solution like he guessed, but it is also intractable. A normal "very simple" solver of the kind you're talking about will solve the solution very quickly, in seconds or less, and it will also not be a constant time algorithm.
    - mamon 9y ago
      9!*9! is just little over 131 billion dashboards. checking correctnes (no number is repeated in row or column) is as simple as counting a sum in all boxes, rows and columns. Generation of all possible boards is little more complex but I can hardly see how it could take "eons" - with proper implementation (Apache Spark :P ) and reasonably powerful hardware (1000 CPU core cluster, ha! ha! ha!) it should run under 1 day and take just little over 13 TB of disk/RAM space :).
      - dahart 9y ago
        9! * 9! is not the number of boards, that is a bad estimate. If you don't account for symmetries, rotations, re-numberings and other things, the number of boards is 6.7e21. Even if you could check a full board in a nanosecond (which you can't) enumerating that number would take more than 200,000 cpu-years. The paper linked to in the OP's article says: "Due to the sheer number of sudoku solution grids a brute force search would have been infeasible, but we found a better approach to make this project possible. Our software for exhaustively searching through a completed sudoku grid, named checker, was originally released in 2006. However, this first version was rather slow. Indeed, the paper [1] estimates that our original checker of late 2006 would take over 300,000 processor-years in order to search every sudoku grid." https://arxiv.org/pdf/1201.0749.pdf https://arxiv.org/pdf/1201.0749.pdf The estimate in the comment (9!*9!) seems to be implying a simple enumeration, not a complex strategy of symmetry-folding. But even if you do reduce the enumeration, the authors of that paper say their software requires 800 CPU years. I'm not making any claims about whether getting that down to a day might be possible, but I wish you good luck. By all means, show everyone how to do it with a proper implementation and a large cluster! ;)
    - tom_mellior 9y ago
      O(1) means bounded by a constant upper bound, not that every actual run of the program takes the exact same amount of time. Just like "simple quick sort is O(n^2)" does not mean that every invocation will take a quadratic amount of time. The parent's "can be solved in constant time" means the same thing, informally. Anyway, we are in agreement that enumerating all boards would be quite inefficient.
daxfohl 9y ago
"For the most general version of Sudoku" -- post doesn't detail what "general" means, but if the variable is board size, then it's O(N! * N!).
trextrex 9y ago
That's not really constant time is it? Constant time implies that the time taken to solve the problem is not a function of the input size (input in this case being the sudoku board). For a board size of 9x9 it's O(9!x9!). The paper which showed that the general case of Sudoku is NP-complete was apparently this one [1] (Linked from wikipedia) [1] http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf
std_throwaway 9y ago
Can we say that the number of possible states that the universe can assume is finite? Can we further conclude that everything that is possible must fit within the boundaries of the universe and therefore everything is either O(1) or unrealistic?