Algoritmy v praxi: Knights Travails

Feb 1, 2026

Únor 2026

Úkolem bylo najít nejkratší cestu šachového koně mezi dvěma pozicemi na šachovnici. Projekt prakticky spojil grafy, frontu a BFS.

Šachovnice je v tomto modelu graf: pole jsou uzly a legální tahy koně jsou hrany.

Proč BFS (Breadth-First Search)?

Protože hledáme nejkratší cestu v neohodnoceném grafu, správná volba je BFS. Algoritmus postupuje po vrstvách a při prvním zásahu cíle vrací optimální počet tahů.

Klíčové části řešení:

• fronta (queue) pro BFS,
• množina navštívených pozic (visited),
• ukládání cesty spolu s aktuální pozicí.

Tady je srdce mého algoritmu:

findShortestPath() {
    const queue = []; // Fronta pro BFS
    const visited = new Set(); // Abychom nechodili v kruhu

    // Do fronty ukládám nejen pozici, ale i celou historii cesty
    queue.push({ position: this.start, path: [this.start] });
    visited.add(this.start.toString());

    while (queue.length) {
        const { position, path } = queue.shift(); // FIFO - vezmi prvního

        // Jsme v cíli? Vrať cestu!
        if (position.toString() === this.end.toString()) return path;

        // Generuj možné tahy koně
        new GameBoard()
            .getKnightMoves(position)
            .filter((move) => !visited.has(move.toString()))
            .forEach((move) => {
                queue.push({ position: move, path: [...path, move] });
                visited.add(move.toString());
            });
    }
}

Co jsem si odnesl

• Jistotu v použití BFS na praktickém problému.
• Lepší práci s reprezentací cesty během průchodu grafem.
• Potvrzení, že správná volba datové struktury rozhoduje o jednoduchosti řešení.

GitHub: projekt Knights Travails