Domino Tiling an N-Queens Chessboard

QED 2022 Computer Science

In this project, the n-queens puzzle solutions and the corresponding 1x2 tiling arrangements are observed and calculation of the number of domino tiling arrangements of solutions to the n-queens puzzle are performed. Based on results presented for n ≤ 15, it is hypothesized that as long as the necessary condition of having equal white and black squares left in a given n-queen solution, the remaining chessboard will be tileable. This is not always true for other mutilated chessboards, as the mutilations could split the board in disjoint groups. In the example of n-queens, the queens, or mutilations, are spread out so far apart that the entire board is connected. The number of black and white squares being equal seems to sometimes occur when n ≡ 0, 1 (mod 4). On the other hand, for n ≡ 2, 3 (mod 4), none of the placements of queens in the n-queens solutions satisfies this property of equivalence.