Section 10.12 Building the Knight’s Tour Graph
To represent the knight’s tour problem as a graph we will use the following two ideas: each square on the chessboard can be represented as a node in the graph and each legal move by the knight can be represented as an edge in the graph. Figure 10.12.1 illustrates the legal moves by a knight and the corresponding edges in a graph.
To build the full graph for an n-by-n board, we can use the Kotlin function shown in Listing 10.12.2. The
buildKnightGraph function makes one pass over the entire board. At each square on the board the buildKnightGraph function calls a helper, generateLegalMoves, to create a list of legal moves for that position on the board. All legal moves are then converted into edges in the graph. Each location on the board is converted into a linear vertex number similar to the vertex numbers shown in Figure 10.12.1.
fun buildKnightGraph(boardSize: Int): GraphADT<Int> {
val knightGraph = AdjListGraph<Int>(directed = false)
for (row in 0..<boardSize) {
for (col in 0..<boardSize) {
val nodeId = row * boardSize + col
val newPositions = genLegalMoves(row, col, boardSize)
for ((row2, col2) in newPositions) {
val otherNodeId = row2 * boardSize + col2
knightGraph.addEdge(nodeId, otherNodeId)
}
}
}
return knightGraph
}
The
genLegalMoves function (Listing 10.12.3) takes the position of the knight on the board and generates each of the eight possible moves, making sure those moves are still within the board. We use a data class to represent an x-y pairing.
data class XYPair(val x: Int, val y: Int)
fun genLegalMoves(row: Int, col: Int, boardSize: Int): List<XYPair> {
val newMoves = mutableListOf<XYPair>()
val offsets = listOf(
XYPair(-1, -2), // left-down-down
XYPair(-1, 2), // left-up-up
XYPair(-2, -1), // left-left-down
XYPair(-2, 1), // left-left-up
XYPair(1, -2), // right-down-down
XYPair(1, 2), // right-up-up
XYPair(2, -1), // right-right-down
XYPair(2, 1) // right-right-up
)
for ((rowOffset, colOffset) in offsets) {
val newRow = row + rowOffset
val newCol = col + colOffset
if (newRow in 0 ..< boardSize && newCol in 0 ..< boardSize) {
newMoves.add(XYPair(newRow, newCol))
}
}
return newMoves
}
Figure 10.12.4 shows the complete graph of possible moves on an \(8 \times 8\) board. There are exactly 336 edges in the graph. Notice that the vertices corresponding to the edges of the board have fewer connections (legal moves) than the vertices in the middle of the board. Once again we can see how sparse the graph is. If the graph was fully connected there would be 4,096 edges. Since there are only 336 edges, the adjacency matrix would be only 8.2 percent full.
You have attempted of activities on this page.
