Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

The "Toy" problem is Sudoku -> 3SAT -> Solution -> Convert back. Sudoku is actually NP complete and therefore is the smallest toy example recently.

N-Queens was popular before Sudoku become a thing, and you might find some basic tutorials on N-Queens -> SAT solvers. Also an easy problem that's fun to solve on your own.

------

TSP is... very complicated to reduce to 3SAT. Try it after you understand the other examples. I did a search online, and found a good set of slides here: https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/sat.pdf

The tl;dr: TSP -> Hamiltonian Cycle -> 3SAT -> Solver.

http://www.math.uwaterloo.ca/tsp/sweden/index.html

------

Because all NP-complete problems convert into each other, its possible to convert other NP Complete problems (ie: Sudoku) into a TSP problem, then use TSP-solvers to answer the problem.

3SAT just seems to be the one NP-complete problem that everyone's reducing to. There's an implicit assumption that its easiest to convert to 3SAT.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: