Combinatorial Problems on the Chessboard

Abstract

Positional chess problems concern the placement of chess pieces, on a given board, that satisfy certain criteria. Classic examples are the independence and domination problems. The former asks for a maximal placement of a given chess piece such that no piece in the placement can move to the position of another in a single chess move. The latter asks for a minimum placement of a given chess piece such that: every square of the board is either occupied by a piece in the placement, or at least one piece in the placement is positioned such that it could move to that square in a single chess move. In practice the cardinality of these placements is the primary concern of each problem.

This thesis explores the independence and domination problems for the bishop piece on a variety of abstractions of the traditional 8 x 8 chessboard. By identifying edges of the generalised n x m rectangular board, chess problems can be posed on a variety of topologies. Those topologies discussed in this thesis are the cylinder, MÖbius strip, torus, Klein bottle and real projective plane. This thesis also explores the independence and domination problems on the surface of the n x m x l cuboid. Results for the domination and independence problems for the bishop are given for the n x n x n cube and n x n x m square prism. Having considered a number of surfaces composed of square cells, consideration is given to an entirely new grid structure consisting of hexagonal cells. The final results of this thesis pertain to a tight bound on the independence problem for the bishop piece on the regular hexagonal grid.

In the conclusion to this thesis, the scope of the results presented are collated with current results from the literature regarding the bishop piece. Problems that are still to be addressed for the bishop are highlighted and the connection between positional chess problems for the bishop and for the queen is discussed. Consideration is then given to applications of the work in this thesis to these areas.

Date of Award	2019
Original language	English
Supervisor	Stephanie Perkins (Supervisor), Paul Roach (Supervisor) & Sian K. Jones (Supervisor)