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.