NP-hard just speaks about the algorithm complexity. The input size of a typical sudoku puzzles so small that even the most naive algorithm can do it quickly.
Incorrect. I tried the most naive algorithm when I was about 9. It generated every 9x9 grid of digits, checked if it was a Sudoku solution, and then it it matched the puzzle. I gave up while every row but the first was still full of 0s.
Technically, Sudoku as normally defined can't be in any complexity class because there are only a finite number of 3x3 Sudoku. People say "Sudoku is NP-hard" to mean a generalized NxN Sudoku would be NP-hard. But no one would expect that to be easy.
Another interesting NP-complete problem is minesweeper and closer to true since minesweeper problems can have variable size by their definition.
What is the "n that goes to infinity" for Sudoku? I thought that you could iterate through all possible 9x9 grids and find the ones that satisfy the rules AND are consistent with the "known" numbers. That would make it O(1), not NP-hard.
NP-hard just speaks about the algorithm complexity. The input size of a typical sudoku puzzles so small that even the most naive algorithm can do it quickly.
Incorrect. I tried the most naive algorithm when I was about 9. It generated every 9x9 grid of digits, checked if it was a Sudoku solution, and then it it matched the puzzle. I gave up while every row but the first was still full of 0s.
Ok yes. I suppose it is possible to do worse than brute force, haha
Technically, Sudoku as normally defined can't be in any complexity class because there are only a finite number of 3x3 Sudoku. People say "Sudoku is NP-hard" to mean a generalized NxN Sudoku would be NP-hard. But no one would expect that to be easy.
Another interesting NP-complete problem is minesweeper and closer to true since minesweeper problems can have variable size by their definition.
> It's NP-hard
What is the "n that goes to infinity" for Sudoku? I thought that you could iterate through all possible 9x9 grids and find the ones that satisfy the rules AND are consistent with the "known" numbers. That would make it O(1), not NP-hard.
I think "n" would be the grid size.