News for hackers. Stuff that matters.
Re:Current draft of The Art of Computer Programming pre-fasc... by ufo on Friday July 03, 2015 @10:52PM (#9828954)
One neat example that comes to my mind is how some package managers use SAT solvers to resolve package conversioning conflicts.

I would say that SAT solvers (or SMT solvers, depending on the problem domain) are applicable to almost any kind of problem where the first thing that comes to your mind is implementing a brute-force search using backtracking. SAT solvers implement lots of tricks that are likely to leave naive backtracking algorithms in the dirt (knuth's chapter covers lots of them)

One silly example I like is the time I used a SAT solver to find the solutions for a little Flash puzzle game.

https://github.com/hugomg/hexiom

My favorite part is how I could add some symmetry-breaking predicates to greatly speed up the solver on highly symmetrical problem instances. Those instances are very hard for hand-written algorithms and a SAT solver let me work around the symmetry problems in a highly declarative manner.

There are no comments on this comment yet.