Solo Chess Reductions

Solo-Chess is a single-player variant of chess in which the player must clear all but one piece from the board via a sequence captures while ensuring that the number of captures performed by each piece does not exceed the piece's budget.

The paper "Uniform-Budget Solo Chess with Only Rooks or Only Knights is Hard" shows that the problem is NP-Hard even when all pieces are rooks with budget exactly 2, or knights with budget exactly 11. This pages implements the NP-Hardness reduction for rooks and contains a playable instance resulting from our reduction for knights.

The reduction is from the vertex cover problem: given a graph G = (V,E) and a positive integer k, is there a subset V' containing at most k vertices from V such that each vertex in E has at least one endvertex in V'?

In this variant of the game, the last remaining rook must be placed in the highlighted target position on the top right of the board. See the paper for a discussion on how this assumption can be removed.

The reduction is from the problem of finding a Hamiltonian path in a graph G. The following board results from applying our reduction to the graph in the figure (a). As part of the reduction the graph is embedded on a grid, and then on the chessboard. The embedding of the graph on a grid is shown in figure (b).