Partridge Puzzle

Recently I watched this video on the Partridge Puzzle. It’s a very good video, but unfortunately it’s missing something. A link to all the solutions and images of the solutions.

Random Partridge Puzzle solution. Changes on website refresh.

For whatever reason I find solving these kinds of puzzles fun, so I decided to find all the solutions by myself. The solutions are available here¹. The code for generating them is available on my GitHub.

Puzzle

The puzzle statement is very simple. You have a grid of $45\times 45$. You also have 1 tile of size $1\times 1$, 2 tiles of size $2\times 2$, all the way up to 9 tiles of size $9\times 9$. This gives you ${\Sigma }_{n=1}^{9}n=45$ tiles. The goal is to place the tiles so that they cover the whole $45\times 45$ grid.

There are 1,730,280 solutions to this puzzle. Even though there is an abundance of solutions, finding one by hand is very difficult.

Finding Solutions

The algorithm for finding solutions is also very simple. It places a tile, updates the board and available tiles and recursively calls itself on the new board with new available tiles. If it can’t find any available spots to place a tile, it backtracks to a previous state. If a solution is found, it’s written to the resulting file.

The basic function for finding solutions is very simple:

fn solve(x: u8, y: u8) {
    for card_idx in 0..SIZE {
        // Check if we have any cards of the size left
        if free_cards[card_idx] == 0 {
            continue;
        }

        // Check if card can be placed
        let card = (card_idx + 1) as u8;
        if !board.can_place(card, x, y) {
            continue;
        }

        // Place the card
        // Snip...

        // Find next empty tile
        match self.board.find_empty(y) {
            None => // Board is full -> report solution
            Some((new_x, new_y)) => solve(new_x, new_y),
        };
    }
}

The problem is, that there are a lot of options of placing down the tiles. Which means a program like this will take a lot of time to finish. I used two very obvious tricks² to get the run time down a bit.

The first trick is using integers for rows. Each bit in an integer represents a place on the board. This allows us to do bitwise operations on the rows to check if a tile can be placed. And bitwise operations are very fast.

The second trick was parallelization. Each core on the CPU can explore its own sub-state of the board, parallel to the other cores.

With these two tricks employed I got the program to find approximately a 1000 solutions per minute on my desktop linux machine. This means that expected run time is cca 28 hours, which is acceptable. Unfortunately for me, I live in a place where stable electricity is not a given. After finding 1,500,000 solutions (only 200,000 left) the power went out and I had to start over. This time I rented a server with 48 cores, which made finding all solutions a lot faster.

The final code for finding solutions and rendering them into images is available on my GitHub.

Solutions

The solutions are saved in solutions.txt file, which is in a very simple format. Each row contains a single solutions with tile sizes separated by spaces. Number $n$ represents a tile of size $n\times n$.

First tile for a solution is placed in the (x, y) = (0, 0) (top left). Next tile is placed in the same row on the next free x. If no x is available, we scan the next row from left to right until we find an available free x.

In other words, tiles are placed by scanning rows top to bottom and finding the first available spot.

Conclusion

This was a fun little puzzle to solve. One thing that I have learnt is that renting hardware is very cheap. Renting a powerful server is a lot easier, faster and reliable than running these sort of tasks on my personal machine. This is a very good lesson to keep in mind when dealing with computationally expensive programs in the future!