Post date: Feb 28, 2010 1:00:15 PM
Back in 2006 I was very fond of logic puzzles of the style of Einstein's one.
As an example, this is one version of the puzzle in question:
In fact I found that I could focus my attention better to some classes while I was doing puzzles like that, as I didn't get bored and just disconnect. However, I began automatizing the process in my head to the point I tried to create an algorithm inspired in my way of solving them. That's how this little personal project was born.
The project is presented as an interactive tool that allows the user to define the problem attributes, make assertions, introduce some constraints, query data (including all current possibilities of the requeste data) and, of course, solve it. It has its own simple syntax and commands written using Bison and Flex.
This little tool is completely based on the concept of logical relation matrices. It defines attributes (nationality, favourite drink, pet...) with the same number of entries (norwegian, coffe, cats...) and creates a relation matrix for each pair of different attributes. All elements of the matrix are set to undetermined (internally, 2 or any other value greater than 1) and user assertions set zeros (false) or ones (true) to positions in those matrices, which are directly associated with specific entry relations (for example, 'The swedish doesn't live in the blue house').
True assertions need special handling, as per-attribute exclusion is assumed in all of these puzzles. When the user introduces a true assertion, many entries are set to false and the relation matrix is checked for possible completition (most times the remaining true relations are found by elimination). This can lead to contradictions if the input data is not logically consistent.
In any case, the real interesting point is the propagation of the entry relationship information. It is performed by means of a simple matrix product and a later unification step. With zero set to false, one to true and more than one to indeterminate, the algebraic matrix-matrix product leaves a combined matrix with logical consistency. For example, the product of the nationality-drink matrix with the drink-pet matrix (matrix transposes may be used to revert the attributes) leaves the derived nationalty-pet relation matrix. However, this new matrix has to be combined with the existing nationality-pet relation matrix. This unification step consists of replacing indeterminate values with new true or false ones. Any other replacing of different values leads to a logical contradiction in the problem.
To control the relation dependencies an internal list is creater together with a update queue. Every time the user asserts new data and its corresponding relation is modified an update is triggered in the relation matrices related to it, inserting them in the update queue (only once, of course). In the same way, if the unification step produces any change new updates are triggered propagating this way the logical consequencies until the queue is empty. This process is triggered with the solve command.
Though this should be enough for some problems, some rules like 'The british lives two houses away of the one who owns a dog' cannot be correctly handled. For solving this problem, support was included for simple constraints based on the entry index rather than the entry value. Now it is possible to add constraints of the type 'more than', 'less than', 'x positions to the left', 'x positions to the right' and 'x positions away'. With those, the program was able to solve the popular Einstein's puzzle among many others. Some other constraints could be added, like mutual exclusion groups to avoid the user to introduce combinatorial false assertions, or forcing the logical equivalence of two non-related entries (yes, there are puzzles which use this and provide less data).
Some parts of the program can be a bit messy, and the program itself is not completely documented. It is neither the puzzle syntax and commands though it should be quite obvious after looking some of the included examples even if they are in spanish (to try one of them, just redirect it through standard input to the tool). I would like to finish the documentation and include extra constraints someday when I have enough free time.
By the way, I got tired of those logic puzzles as they didn't were a challenge anymore. I moved to nonograms (or paint-by-numbers puzzles), which I find a lot more entertaining. If you like them I have a pair of suggestions for you. First, if you have a Nintendo DS you cannot miss Picross DS. Its touchscreen user interface is quite convenient for this kind of puzzles. Second but not less important, check Griddlers.net. There you can find lots of not only the classical monochrome puzzles but also multicolor puzzles with their own rules, and even triangular (and triangular multicolor!) nonograms that any fan of these puzzles should not miss. Maybe in the future I build a nonongram solver algorithm too.