Mutilated chessboard problem

The mutilated chessboard problem is an instance of domino tiling of grids and polyominoes, also known as "dimer models", a general class of problems whose study in statistical mechanics dates to the work of Ralph H. Fowler and George Stanley Rushbrooke in 1937.

[1] Domino tilings also have a long history of practical use in pavement design and the arrangement of tatami flooring.

[2] The mutilated chessboard problem itself was proposed by philosopher Max Black in his book Critical Thinking (1946), with a hint at the coloring-based solution to its impossibility.

[3][4] It was popularized in the 1950s through later discussions by Solomon W. Golomb (1954),[5] George Gamow and Marvin Stern (1958),[6] Claude Berge (1958),[4][7] and Martin Gardner in his Scientific American column "Mathematical Games" (1957).

[8] The use of the mutilated chessboard problem in automated reasoning stems from a proposal for its use by John McCarthy in 1964.

[9][10] It has also been studied in cognitive science as a test case for creative insight,[11][12][13] Black's original motivation for the problem.

[8] The same idea shows that no domino tiling can exist whenever any two squares of the same color (not just the opposite corners) are removed from the chessboard.

[18][20] Gomory's theorem can be proven using a Hamiltonian cycle of the grid graph formed by the chessboard squares.

As in the coloring-based proof of the impossibility of the mutilated chessboard problem, the fact that this graph has more vertices of one color than the other implies that it fails the necessary conditions of Hall's marriage theorem, so no matching exists.

The wazir is a fairy chess piece that can move only one square vertically or horizontally (not diagonally).

Using similar reasoning to the mutilated chessboard problem's classic solution, this wazir's tour does not exist.