During the spring of 2020 my family became obsessed with the board game Genius Square. The game consists of a 6 x 6 grid on which are placed nine polyominoes. At the beginning of each round the players roll seven dice that correspond with seven places on the grid. Pegs are then placed on those spaces and the polyominoes must be placed around them, creating an exact cover of the remaining board space. 

​

As we played this game I grew curious as to how many solutions there were for each configuration and created a Genius Square solver. This project finds the total number of solutions for a given setup, and then randomly displays ten of them.

​

This project involved researching different algorithms (brute force was quickly shown to be infeasible) and applying it to this problem. I chose Donald Knuth's 'Algorithm X' and its 'Dancing Links' implementation (https://en.wikipedia.org/wiki/Dancing_Links).  Thank you to Github user Alex Grubb for this implementation of 'Dancing Links'.

​

This program was a good exercise in researching and applying algorithms. In order for my family to use it I decided to put it up on Heroku, which gave me a chance to learn a little about Django (which I used for the back end).  Currently the server will timeout if the solution requires more than 30 seconds to solve. In the future I would like to use Celery so that I can run the solver as a background task and not simply calculate the problem as part of a post request.

​

View project      View code on GitHub

​