Implicit Graphs : The Knight’s Path

Section 34.10 Implicit Graphs : The Knight’s Path

Many problems can be modeled as graph problems without explicitly constructing a graph data structure. We will call these implicit graphs. In an implicit graph, the vertices and edges are not explicitly stored in a class like Graph. Instead, we have a way to generate the neighbors of a vertex on the fly. This is often more efficient than constructing an explicit graph data structure, especially if the graph is very large or infinite.

🔗

To explore this idea, we will consider the problem of finding a path for a knight on a chessboard. A knight in chess moves in an L shape: it can move two squares in one direction and then one square perpendicular to that.

🔗

A knight on an 8x8 chessboard at position (2,3) with its possible moves highlighted. The knight can move to (0,2), (0,4), (1,1), (1,5), (3,1), (3,5), (4,2), or (4,4).🔗 — Figure 34.10.1. The possible moves of a knight at (2,3).
🔗

The knight’s path problem is to find a sequence of moves for the knight to get from one square on the chessboard to another square. For instance, if we want to get from square (2,3) to square (6, 6), we might use the sequence of moves: (2,3) → (3,5) → (5,4) → (6,6).

🔗

A knight on an 8x8 chessboard at position (2,3). It then moves to (3,5), then to (5,4), and finally to (6,6).🔗 — Figure 34.10.2. The knight’s path from (2,3) to (6,6).
🔗

We would like to discover a shortest path (there are likely multiple shortest paths) for the knight to move from one given square to another square on the chessboard. Since we are interested in the shortest path, we should use a breadth-first search (BFS) algorithm to find it.

🔗

We could set up an explicit graph data structure to represent the chessboard and the knight’s moves. The vertices would be the squares on the chessboard, and there would be an edge from vertex A to vertex B if the knight can move from square A to square B in one move. However, this would require us to construct a graph with 64 vertices (for an 8x8 chessboard) and up to 8 edges per vertex (since a knight can have up to 8 possible moves).

🔗

However, we don’t really need to represent a full list of vertices and edges to solve this problem. Instead, given a vertex (square) we can generate its neighbors (the squares that the knight can move to) on the fly. This allows us to perform a search without ever making a Graph .

🔗

Below is an implementation of the knight’s path problem. We start off by defining a Position struct to represent the squares on the chessboard. It needs to support equality and hashing so that we can use it in an unordered map. We then define a function getKnightMoves that takes a Position and returns a list of valid knight moves from that position. This function is our implicit graph generator. Finally, we perform a breadth-first search using a queue and a parent map to keep track of the path we are building.

🔗

Listing 34.10.3.

🔗

#include <iostream>
#include <string>
#include <list>
#include <unordered_set>
#include <unordered_map>

using namespace std;

struct Position {
    int row;
    int col;

Position() : row(0), col(0) {}
    Position(int r, int c) : row(r), col(c) {}

// Define equality operator for Position to allow comparison in unordered_map
    bool operator==(const Position& other) const {
        return row == other.row && col == other.col;
    }
};

// Specialize std::hash for Position to allow it to be used as a key in unordered_map
namespace std {
    template<>
    struct hash<Position> {
        size_t operator()(const Position& pos) const {
            return hash<int>()(pos.row) ^ (hash<int>()(pos.col) << 1);
        }
    };
}

// generate a list of possible knight moves from a given position
list<Position> getKnightMoves(const Position& pos) {
    list<Position> moves;
    list<pair<int, int>> directions = {
        {2, 1}, {2, -1}, {-2, 1}, {-2, -1},
        {1, 2}, {1, -2}, {-1, 2}, {-1, -2}
    };

// given pos and our list of directions, generate new positions
    //  and check if they are on the board
    for (const auto& [dr, dc] : directions) {
        int newRow = pos.row + dr;
        int newCol = pos.col + dc;
        if (newRow >= 0 && newRow < 8 && newCol >= 0 && newCol < 8) {
            moves.push_back(Position(newRow, newCol));
        }
    }
    return moves;
}

int main() {
    Position start(2, 3);
    Position destination(6, 6);

// BFS
    // queue for BFS
    list<Position> queue;
    // parentMap will also serve as a visited set
    unordered_map<Position, Position> parentMap;
    queue.push_back(start);
    bool found = false;
    while (!queue.empty()) {
        Position current = queue.front();
        queue.pop_front();

if (current == destination) {
            found = true;
            break;
        }

for (const auto& neighbor : getKnightMoves(current)) {
            if (!parentMap.contains(neighbor)) {
                parentMap.insert({neighbor, current}); 
                queue.push_back(neighbor);
            }
        }
    }

// If we found the destination, reconstruct the path using parentMap
    if (found) {
        Position current = destination;
        while(current != start) {
            cout << "(" << current.row << ", " << current.col << ") <- ";
            current = parentMap[current];
        }
        cout << "(" << start.row << ", " << start.col << ")" << endl;
        cout << endl;
    } else {
        cout << "No path found." << endl;
    }
}

Checkpoint 34.10.1.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next