The Puzzle
3-SAT is a puzzle game. You're presented with a finite number of
letter triplets. Some letters are red, and some letters are black. You
must pick one letter of each triplet, with the rule that a choice is
only valid if you've never picked that particular letter in a different
color. So, once you choose a black "A" in a triplet, you are never
allowed to choose a red "A" in any other triplet.
Why
3-SAT turns out to be important to computer science because it's
perhaps the simplest example of a type of problem called an
NP-Complete problem. Generally first or second year computer
science majors will learn about these problems in a basic complexity
theory class.
Briefly, an NP-Complete problem is both NP and
NP-Hard. Being NP means that given a guess solution,
you can quickly verify whether or not the guess is correct. In this
case, you can just make sure that each triplet has a letter selected,
and there are no copies of the same letters in different colors. Being
NP-Hard means you can translate any NP problem into a
3-SAT problem.
I thought it would be a fun exercise to code up browser based "puzzle
game" versions of classic CS problems like this, and create tools to
translate puzzles from one to another. The project is also an excuse to
learn about different single page application frameworks.
The Code
available on
GitHub.
I used the "ember.js" framework for the UI, and coded everything in
CoffeeScript.
My main goal in writing this was to learn a bit about the ember.js
framework. Frankly, I wasn't a big fan of ember, as it had the sort of
leaky-abstraction "magic" that I've come to deeply fear. By this I mean
there are some features where the implementation is not covered in the
documentation, but you have to know how everything works to use the
framework correctly.