5 ms·

I believe that would have far-reaching implications, seeing that Sudoku has been proven to be an NP-Complete problem. http://en.wikipedia.org/wiki/List_of_NP-c

• Someone 15y ago
  Proving something about a NxN grid does not have much to do with a problem being NP-complete. For example, the fact that it is not very hard to proof that a 1x1 sudoku requires 1 clue does not prove that sudoku is not NP-complete.
  • pbhjpbhj 15y ago
    Surely a 1x1 grid requires 0 clues?!
    • ohgodthecat 15y ago
      No because then you wouldn't be able to arrive at a fixed solution there would be 9 solutions with 0 clues.
      • SatvikBeri 15y ago
        In a 1x1 grid you would only use one digit, not 9. A 1x1 grid requires 0 clues, a 2x2 requires 1 clue.
        • deleted 15y ago
          [deleted]
        • its_so_on 15y ago
          (tongue in cheek) right, a 1x1 grid requires 0 clues, it has only a single digit as its solution; that digit is -- [its_so_on looks left, cut to SatvikBeri]
          • cperciva 15y ago
            That digit is a 1, since for an NxN grid the values are 1 through N.
            • pbhjpbhj 15y ago
              I'm not sure what the "Rules of Sudoku" say but I assumed any single symbol of the solvers choosing would do.
    • Someone 15y ago
      A classic off-by-one error. That is not what I was thinking of, though. A 2x2 grid requires a single clue. A 3x3 grid requires 2 (1 and 2 across a diagonal suffices) So, we have a sequence 0,1,2,?,?,?,?,?,17,... I checked the OEIS, but it does not seem to contain this sequence. Does anybody know more values?
      • T-hawk 15y ago
        It's not really valid to treat this as a sequence, since most side lengths don't form what we think of as a Sudoku puzzle. The side length of a true Sudoku must be a perfect square in order to create the interior boxes that are (geometrical) squares. For the counterexample, think of a 7x7 puzzle (or any prime)... how can a square box contain seven cells? A 4x4 puzzle gives you four 2x2 boxes. The standard 9x9 puzzle gives nine 3x3 boxes. A 16x16 puzzle gives sixteen 4x4 boxes. Sudoku variations sometimes have rectangular boxes; a 6x6 puzzle can have six 2x3 boxes, or a 12x12 puzzle can have twelve 3x4 boxes. But that is a different form of constraint logic so we shouldn't expect that the minimum number of clues for these sizes would follow a recognizable sequence.
        • Someone 15y ago
          I had to check Wikipedia (which, as we all know, always is right :-)) to see that you are right. I have seen so many variations on sudoku's that I forgot what the original looked like. I was just thinking of Latin squares.