New answers tagged

-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