i've always loved logic puzzles, and i just finished a class in linear algebra. unfortunately, this question didn't enter my mind until about a week after the class was over.
anyway, what i'm wondering is, is there a way to solve logic puzzles (i'm talking about the kind with a few grids, and you have a few facts, and you need to figure out who did what when, or some variation on that) using linear algebra? i would imagine that that's how computers would solve them. but i'm wondering if all the matrices are related, and if i could, i don't know, take a transpose of one matrix, or find an inverse and use that? i tried to do a little research on my own, but there are way too many results for me to go through. thanks!

It seems unlikely that linear algebra will help very much, because the properties of grids arising in logic puzzles are difficult to capture using linear algebra alone. (Many statements you might want to make about a grid arising in a logic puzzle— e.g. that it have at most one nonzero entry in every row and in every column, or that it have fewer than a specified given number of nonzero entries in a particular set of rows or columns— are simply more easily expressed in terms of logical conditions (not in terms of matrix and vector arithmetic). In this sense, the extra structure these grids have is not very 'linear algebraic' in nature; to describe it using linear algebra would be confusing rather than enlightening.

One distinguishing feature of logic puzzles is that the entries of the grids often come, not from an infinite set of 'scalars' that can be added and multiplied, but from a finite set (often just 'empty' or 'x') which might or might not have its own arithmetic.

There are things called "finite fields" over which one can do most of linear algebra. If you take your scalars to be only 0 and 1, with arithmetic modulo 2, much of what you learned in linear algebra goes through for this field, and the arithmetic in this field very much mimics logical operations (with 0 as 'false' and '1' as 'true', say, addition modulo 2 corresponds to the logical 'xor', and multiplication modulo 2 is logical 'and'). But even then, there are a lot of things you want to do with logical operations— not just 'xor' and 'and', but 'or' and 'not'— which is not quite in the realm of linear algebra, for the reason that the some of these operations are _not_ linear maps. You may find web searches on Boolean algebra useful, though; computers are great with it, and from a programming point of view it is often more fundamental than the basic operations of linear algebra (most computers, even those that are decades old, have the ability to do Boolean calculations _in hardware_; the same cannot be said of matrix multiplication).

I am reminded of another puzzle type that is somewhat related to linear algebra: Sudoku puzzles. They contain grids of numbers, and could conceivably be dealt with using linear algebra, but the restrictions that give Sudoku games their unique flavor are not easily dealt with in 'matrix arithmetic' form. If you wanted to program a computer to solve Sudokus in a 'logical' fashion, you would be better off working just at the level of logical operations. (The technique of "backtracking" is probably the simplest way to get a computer to solve these and other puzzles. See the link below.)

Another puzzle type that comes to mind is one where an empty square grid is given, along with the sums of the entries in each row and column (and sometimes diagonal), and the goal is to fill in the blanks with numbers (understood to be positive integers, often in some fixed range, and often, with no number used more than once) so that the totals come out right. This is a problem that _can_ almost be solved in terms of linear algebra (since such an empty grid is equivalent to a system of linear equations in a certain number of unknowns), but the conditions that make the solution unique (having integer entries; having positive entries; using no integer more than once) are not easily expressed in terms of linear algebra. Ditto the problem of finding "Latin squares" of various orders: the conditions required to make a Latin square a Latin square are more easily expressed without the language of linear algebra.

I have included some links that will hopefully be of some use in your study.

One Response to “logic puzzles and linear algebra?”