Problem Name: Turn the Lights Off
UVa ID: 10309
Keywords: brute force
I find this problem interesting for a number of reasons, but the first that comes to mind is that it involves a game with simple rules which anyone can pick up quickly, but its mathematical analysis is not trivial at all —and games of this kind are just fantastic, aren’t they?
Let’s start by mentioning that the solution I implemented can be classified as “brute force”, but if you think that it’s a naive brute–force (\(2^{100}\)), then we’re not on the same page, yet.
Actually, the first thing I did when I first read this problem was thinking about all the types of “blind” strategies and possible pruning that could be performed while looking for the solution through a breadth–first search. The results were not very encouraging. As you may have noticed, the space of possibilities is insanely large (\(2^{100}\)) and a BFS could end up using equally lunatic amounts of memory. The problem boils down to the simple fact that representing a “state” for this problem is not cheap: a boolean matrix of size \(10 \times 10\) is simply too much for any simple–minded approach.
Now, fortunately for us, some pretty smart people have worked hard on analysing this game in the past, and we can read about their findings through the magic of the Web :). First of all, as far as I know, the original game that implemented these mechanics is called Lights Out and was developed by a company called Tiger Toys in 1995, in case you want to do some research by yourself. If you do, one of the first website you’ll probably come across is this: Jaap’s Puzzle Page, which has a lot of information about it. There’s a related page dedicated exclusively to the mathematics behind Lights Out, which are fascinating to read about, but I won’t mention here mainly because my solution didn’t involve any sophisticated math analysis.
What I do want to mention though, is that there exists an heuristic that can be used to solve these puzzles, which can be summarised like this: press some buttons (i.e. switch some lights) from the top row, then “chase the lights” from the second row to the bottom. What this means is, starting with the second row, press a button only if the light to the north of the current position is on. Go on like this row–by–row until you reach the bottom. If in the end you haven’t cleared the grid, then go to the beginning, pressing some buttons from the top row, and repeating the process until you have solved it. Interesting, right?
But it gets better. In a paper —referenced in Jaap’s page— called “Turning Lights Out with Linear Algebra” we can find the following good news:
Lights Out can be generalized to an \(n \times n\) array of lights. (…) Of course if the dimension of the null space is zero, every configuration is winnable and the solution is unique (if no buttons are pressed more than once).
And then there’s a table where we find that the dimension of the null space for games of size \(10 \times 10\) is zero. In other words, for this problem, every configuration has a solution, and if we find it by “pressing a switch” no more than once, then it’s guaranteed to be the best solution.
Now we’re ready to formulate our solution: if we try pressing every combination of lights from the top row and then “chase the lights” downwards, we have to check only \(2^{10}\) alternatives, which are guaranteed to be enough to find our answer. I was truly amazed by how nicely this idea translates into elegant code, and it has a complexity of \(O(2^n n^2)\) (where \(n=10\) for this problem).
By the way, if you have some time to spare, maybe you’d like to give the heuristic explained here a try, on a game of “Lights Out” where the size of the grid increases at each level: here’s the game of Tacoyaki+. Have fun :).
References
- Turning Lights Out with Linear Algebra by M. Anderson and T. Feil (1998). Math Magazine, vol. 71, no. 4, October 1998, pp. 300-303.
http://www.math.ksu.edu/~dmaldona/math551/lights_out.pdf
No comments:
Post a Comment