Solving n-queens on non-squares

Abstract

Chess is a hugely popular game, and has been for ages. But it is not just the game itself. Chess has also give rise to many related games, problems and puzzles. One of the most famous is the n-queens problem. This classic puzzle tries to find the number of different arrangement of n queens on an n × n board, such that no queen attacks any other queen. On an 8 × 8 board, 8 queens can be placed in 12 different ways, extended to 92 different placings when counting each rotation and reflection separately. This thesis has a similar goal, but without the restriction of having a square board. Guided by a hexagonal board and a three-player board, the n-queens problem is tackled by reducing it to the maximum independent set problem. This, in turn, is solved by computing the number of maximum cliques in the complement graph. The algorithm at the core of the accompanying computer program is the Bron–Kerbosch algorithm.