New answers tagged polynomial-time
-3
Solving a Sudoku puzzle is equivalent to deciding whether there is a valid graph vertex coloring using $k$ colors, where $k = 9$ in your $3 \times 3$ Sudoku instance. The graph coloring problem is known to be NP-complete for values of $k > 2$, so a non-trivial, non-backtracking algorithm for $3 \times 3$ Sudoku would be very surprising.
Top 50 recent answers are included
