I was watching a stream of The 7th Guest the other day, and the bishops puzzle caught my eye. The idea is simple: on a 4x5 chess board, place 4 white bishops on the leftmost column, and 4 black bishops on the rightmost column. Then, make normal diagonal bishop moves–with the restriction that you can’t put a bishop in an attacked square–until the bishops have switched places.

W---B        B---W
W---B  ---\  B---W
W---B  ---/  B---W
W---B        B---W

I thought it might be fun to solve the problem with a program, and ended up writing programs in both python and scala. Since the problem space wasn’t too large, and I wanted the shortest solution, I just wrote a basic breadth-first search.

The programs are in my 2018 small programs repo.

If you just want to know: the game’s 4x5 puzzle can be solved in 36 moves, and I wrote the scala version to play arbitrary sizes. A 4x7 puzzle can be solved in just 24 moves!

Some Observations

The hardest part of the program was working out all the squares a bishop can touch efficiently. I know real chess programs use bitboards, but I wanted something more straightforward. With a few minutes of thought, I worked out geometrically what the two diagonal lines would be for any position on the board.

I had an idea early to create a higher-order function that calls a supplied action for every square that a given bishop can touch. It turned out to be very useful–I used it both to determine which squares are attacked, and also for generating prospective moves to try.

The scala version is about 7 to 10 times faster than the python one, even including the JVM startup/warmup time. But, the python one was faster to write, and slightly shorter. So, for a problem of this size, which I only plan to run a handful of times, I think python is a great choice. I only did the scala version for comparison.

The scala version makes nice use of implicit parameters for the game context (size of board, which positions we’ve already encountered, etc.). In python, I just put these in globally accessible objects. So, even though I don’t need to do things like concurrently solve multiple boards or whatever, the scala code is ready for all of that by design.