There is a nice game called Enlight from FeejoSoft. I have it on my PocketPC phone and for the life of me I just couldn't get past level 33. So yesterday I finally sat down and implemented an algorithm to solve this game automatically.
Of course, I used C# and Visual Studio (as a tester, I used our latest internal build of Visual Studio 2010, although it will run just as fine on 2008 as well).
The game
The rules are really simple. There is a boolean matrix 10x10, and you can invert cells. When you invert a cell, all its neighbors (usually four) are inverted with it. Given this operation, you are required to nullify the matrix (turn off all the lights):
The game is freeware and you can use your favorite search engine to find and download it (e.g. from freewareppc.com, no responsibility for links). If you'd like to run it in an emulator, here are the steps:
The algorithm
The idea I used is commonly used for such problems (e.g. eight queens puzzle (http://en.wikipedia.org/wiki/8_queens) is usually solved using depth-first search with backtracking). I encourage you to visit this wikipedia article, it is very interesting read.
We'll visit every cell column by column. Every cell will have it's next cell which is down in the next row, or the first cell of the next column to the right. For brute force, you would recurse to visit the next cell, then come back, toggle the cell and recurse again. This way every cell will be tried in both combinations. However this will yield 2^100 iterations. We can considerably trim down the search if we don't recurse for knowingly invalid boards. This way we prune the "phase space" of the problem significantly. Here's the complete code for the solver:
namespace MatrixGame { public class Solver { private Field sourceField; private Field solution = new Field(); private Field currentSolution = new Field(); private Solver(Field field) { this.sourceField = new Field(field); } public static Field FindSolution(Field field) { Solver solver = new Solver(field); solver.Search(FieldCoordinates.StartingPoint); return solver.solution; } private int steps = 0; /// <summary> /// Main algorithm /// </summary> void Search(FieldCoordinates current) { steps++; // we traverse the cells column by column, // left to right, top to bottom var next = current.GetNextCell(sourceField); // we've reached the end of the field if (next.Column == sourceField.Width) { if (LeftCellIsEmpty(current)) { CheckSolutionCandidate(); } return; } // pruning - only continue searching if this is a plausible board so far if (current.Column == 0 || LeftCellIsEmpty(current)) { Search(next); } // let's invert the current cell and search again currentSolution.InvertCell(current); sourceField.Invert5Cross(current); if (current.Column == 0 || LeftCellIsEmpty(current)) { Search(next); } } /// <summary> /// If the cell to the left from current is not empty, /// the current board cannot be a solution - /// no point to continue down this branch. /// Prune this and backtrack to another branch. /// </summary> bool LeftCellIsEmpty(FieldCoordinates current) { return !sourceField[current.Row, current.Column - 1]; } /// <summary> /// We've traversed all elements - /// let's check if what we've come up with is actually a solution /// we checked almost all cells in LeftCellIsEmpty /// let's just check the last (rightmost) column /// </summary> void CheckSolutionCandidate() { if (sourceField.GetColumn(sourceField.Width - 1).IsNull()) { SolutionFound(); } } /// <summary> /// We got it! Do something with the solution! /// </summary> void SolutionFound() { solution = new Field(currentSolution); } } }
The solution program
Here's what I came up with. On the left board, you set up the level like you see in the game (the picture shows The Notorious Level 33!). Left-click to toggle a cell, drag the mouse to "draw" adjacent cells.
On the right, you have a chance to play this level, however, the orange dots show which cells you need to click to turn off the lights. If you feel honest, you can turn off the orange dots using the checkbox.
You can download the full source code here:
http://code.msdn.microsoft.com/EnlightGameSolver
The research
First of all, I was amazed how efficient the pruning is. The fact that we don't check for knowingly invalid boards brings us down from 2^100 to just 93183 times the Search method is executed. On my machine this is so fast, that I manage to recalculate the hint solution in real time, as the user clicks in the left board.
Also, building this project raised more questions than it answered. I'm sure there is a whole science behind this seemingly simple domain - Conway's Game of Life is just around the corner, not to mention MineSweeper, cellular automata, even-odd-logic, 0,1-matrices, constraint programming, etc. etc. It is fascinating how complex solutions exist to invert a single pixel on the board:
What is the pattern here? Is the solution always unique? Why is there no solution for some configurations? What if you apply the solution to the solution? What about unlimited two-dimensional plane? Which single-cell source board have a solution? Which don't? What is special about a board consisting of such cells? What is the ratio of yellow cells for such boards? All these are interesting questions I'd love to think about, if only someone would do my main job for me :)
The challenge
As usual, better/faster/shorter solutions are welcome. I'd be especially curious to see a solution in F# or Prolog. Feel free to reuse my UI code.
Finally I had time again to continue working on my Live Geometry project on CodePlex. While I was busy with other stuff, Silverlight 2 has officially released and the rest of the world has already upgraded from Beta 2 to the release version. Now I'm catching up: I've updated the source code for both Silverlight (online) and WPF (desktop) editions, so it should build fine. As usual, you can preview the Silverlight (online) edition at:
http://geometry.osenkov.com
As you can see, I started implementing the coordinate grid and axes. I'm thinking to implement pan/zoom functionality by dragging the coordinate system and using the mouse wheel. Also I need to have a toggle button to show/hide the grid/axes, and numbers (-2, -1, 0, 1, 2, ...) to show up along the coordinate axes. Then I can start working on plotting function graphs and charts.
I've also updated the desktop (WPF) version, although I didn't have time to make it look beautiful:
The beauty of WPF is composability. The toolbar icons use the same logic for drawing points/lines/circles as the main canvas. This way the icons are vector graphics and can be scaled if I want to make the toolbar buttons larger in the future. Also, the buttons in the toolbar are generated automatically using Reflection and data-binding, so when I add a class for a new tool, I don't need to do anything else - reflection will pick it up and create a toolbar button for it using WPF databinding.
Also the good news is that the WPF edition shares the same source code with the Silverlight version. Only at two or three places in code I had to use the #if SILVERLIGHT compiler directives, mostly because WPF VisualTreeHelper.HitTest is called VisualTreeHelper.FindElementsInHostCoordinates in Silverlight (because of slightly different semantics). Andy Beaulieu blogs about this breaking change here: http://www.andybeaulieu.com/Default.aspx?tabid=67&EntryID=95
I decided to compile a small list of Visual Studio features that I use a lot.
Code Editor
Navigation
Refactoring
Code generation
Debugging
Solution Explorer
Macros and automation:
P.S. Sara Ford has much much more in her famous Did you know series.