SATisfying Solutions to Difficult Problems
11 points by abhin4v
11 points by abhin4v
Nice! I read about Sudoku in the context of graph coloring. Although I suppose that since Graph Coloring is NP-complete, everything connects together.
Yes. Looking up on my copy of Computers and Intractability, which is a catalog of NP-complete problems, I can see that graph coloring was shown to be NP-complete by reducing 3-SAT to graph coloring. These proof methods also tend to help encoding things for SAT/SMT solvers.