Project: Lights Out
This project is a Python recreation of the classic game Lights Out using the Tkinter package for the GUI, which I built a couple of weeks ago. It was very simple and didn’t take long, but I thought it’d be a good opportunity to use Tkinter and work on a fun puzzle game that I enjoy playing.
Lights Out was originally released by Tiger Toys in 1995 as an electronic puzzle game. It features a 5-by-5 grid of buttons which can be in one of two states, lit or unlit. Pressing a button toggles the state of that button as well as the four buttons directly adjacent to it. The game begins with certain buttons lit and the player presses buttons with the goal of getting all the buttons into their unlit state, hence the name.
My implementation uses check-boxes as the buttons and includes 8 prearranged levels. From Level 9 onwards, the puzzles are generated by an algorithm and will be of varying difficulty. You can find my GitHub repository for the project, where you can also download it and play it for yourself, here.
Level Generation
I mentioned earlier that after the first 8 levels, the rest of the levels are generated by an algorithm. This was probably the part of this project that required the most thought, and so I’ll tell you a bit about that here.
When I created the first version of this project, I naively assumed that every (or at least almost every) configuration of on and off lights would be a solvable puzzle and so just implemented a method that randomly lit a random number of lights. I soon realised that actually the majority of configurations were not solvable and that I would have to do something a bit more clever, nobody likes an impossible puzzle.
After some searching, it turned out that actually there has been a surprising amount of mathematical research into the game, and so I sifted through a few of the papers written on the matter. Some of these offered ways to check for the solvability of a Lights Out puzzle, however they were much more complex and in-detail than what I was looking for.
One thing I did find out however, was that through a method called ‘light chasing’, every configuration could be reduced to a pattern existing only on the bottom row of lights, which could then be solved very easily. The details of ‘light chasing’ can be found in the Wikipedia article for the game but I will say no more of this, as it provides a systematic method for solving every level and so may be somewhat ‘game-breaking’ for those who enjoy the puzzle.
With the knowledge that every solvable puzzle could be re-arranged into one of several patterns on the bottom row, as well as the fact that every puzzle would remain solvable no matter which moves were made by the player, I was able to work backwards to a method for producing solvable configurations. Each of the solvable bottom row patterns would be stored in a list, and when a new level was generated, one of these would be chosen at random.
Now of course this would be a very easy and boring puzzle, so next the algorithm ‘scrambles’ the puzzle by performing several moves which follow the same rules as if a player was clicking the buttons. When these two actions are completed, the resulting levels are always solvable and of course of varied difficulty since the process and amount of scrambling is random. Below I have included the code for this part of the algorithm, with some comments for added clarity.