For centuries, scholars have analyzed a collection of problems that, nowadays, has been defined as NP-complete. Currently, NP-complete problems have no known efficient solutions. The Clay Mathematics Institute has offered a reward of one million dollars for a solution. The problem of finding Hamilton paths and cycles has been shown to be in this category. Knight’s tours, where the knight must visit every square of a chessboard exactly once, are examples of Hamilton paths and cycles.
This research revolves around the creation of a new branch of the tour problems, through a new piece: the Archbishop. Chess Grandmaster Jose Capablanca created this piece, giving it the ability to move as either a Knight or a Bishop, to increase the complexity of Chess. Some of the questions investigated are: does the Archbishop have Hamilton cycles and paths on various size boards (not only 8x8 but 3x3, 4x4, ...)?, and, how many edges are there in the movement graphs of these boards?
One result used different counting arguments. The Archbishop, unlike the Knight, is not forced to “switch colors” on the checkered chess board, as it has the ability to move diagonally to a square of the same color. Therefore, it has the ability to tour a board with an odd number of squares. A second result was the equation for the number of edges the Archbishop movement graph has in relation to the size of the board: 6n2 – 16n + 10. With this finding also came the equation of a Bishop’s number of edges: 2n2 – 4n + 2. Third, using graph theory, it was found that an Archbishop cannot complete a cycle on a 4x4 chess board. And fourth, using a cyclic solution of a 3x3 board, a solution for all 3nx3n boards was found by connecting the smaller solutions together. These findings suggest many new problems and present new opportunities for people to investigate.
The Archbishop's Odyssey.
Undergraduate Review, 10, 143-148.
Available at: http://vc.bridgew.edu/undergrad_rev/vol10/iss1/28
Articles published in The Undergraduate Review are the property of the individual contributors and may not be reprinted, reformatted, repurposed or duplicated, without the contributor’s consent.