Jezcova procházka
Jezcova procházka

Jezdcova procházka (Knight's tour) je šachová úloha, jejímž cílem je pomocí šachové figury jezdce navštívit všechna pole šachovnice právě jednou. Tento hlavolam je znám již od středověku – byl popsán kolem roku 840 arabským učencem Al-Ádlím v díle Kitáb aš-Šatrandž (Kniha o šachu).

Jezdcova procházka má překvapivě obrovské množství řešení, pro běžnou šachovnici 8x8 polí existuje 33 439 123 484 294 neorientovaných cest, kterými se může kůň vydat.

Strojové řešení problému

Nejjednodušším způsobem řešením problému je backtracking. Naivní algoritmus má ovšem tendenci být velmi pomalý, protože se dostává snadno do do slepých uliček, v nichž musí přehodnotit velké množství rozhodnutí. Jeho optimalizací je Warnsdorffův algoritmus, ve kterém se kůň vždy vydá přednostně na to pole, ze kterého může pokračovat nejméně způsoby. V této heuristice jsou tedy přednostně obsazována špatně dostupá pole, zatímco ta snadno dostupná jsou odložena na později.

Počet řešení problému

Velikost šachovnice 3x1 3x2 3x3 3x4 3x5 3x6 3x7 3x8 3x9 3x10 3x11 3x12 3x13
Počet neorientovaných řešení 0 0 0 16 0 0 104 792 1 120 6 096 21 344 114 496 257 728

Kód

/**
 * Resicka jezdcovy prochazky backtrackingem
 * @author Pavel Micka
 */
public class KnightsTour {

    /**
     * Priznak nenavstivenosti policka
     */
    private static int NOT_VISITED = -1;
    /**
     * Velikost sachovnice na ose x
     */
    private int xSize;
    /**
     * Velikost sachovnice na ose y
     */
    private int ySize;
    /**
     * Pocet reseni
     */
    private int solutionsCount;
    /**
     * Pole pro reseni
     * 0 -> pocatecni pozice kone
     * 1 -> prvni tah
     * 2 -> druhy tah
     * .
     * .
     * .
     * n -> n-ty tah
     */
    private int[][] solutionBoard;

    public static void main(String[] args) {
        for (int i = 1; i < 20; i++) {
            KnightsTour kt = new KnightsTour(3, i);
            kt.solve();
            System.out.println("<td>"+kt.solutionsCount+"</td>");
        }
    }

    /**
     * Konstruktor resitele jezdcovy prochazky
     * @param xSize velikost sachovnice na ose x
     * @param ySize velikost sachovnice na ose y
     */
    public KnightsTour(int xSize, int ySize) {
        solutionsCount = 0;

        this.xSize = xSize;
        this.ySize = ySize;

        solutionBoard = new int[ySize][xSize];
        for (int i = 0; i < ySize; i++) {
            for (int j = 0; j < xSize; j++) {
                solutionBoard[i][j] = NOT_VISITED;
            }
        }
    }

    /**
     * Resi jezdcovu prochazku
     */
    public void solve() {
        for (int i = 0; i < ySize; i++) {
            for (int j = 0; j < xSize; j++) {
                takeTurn(j, i, 0);
                solutionBoard[i][j] = NOT_VISITED; //reset pole
            }
        }
    }

    /**
     * Vrati policka, na ktera muze kun skocit
     * @param x souradnice kone x
     * @param y souradnice kone y
     * @return souradnice, na ktere muze kun skocit
     */
    private List<Coords> getFields(int x, int y) {
        List<Coords> l = new ArrayList<Coords>();
        if (x + 2 < xSize && y - 1 >= 0)
            l.add(new Coords(x + 2, y - 1)); //doprava nahoru
        if (x + 1 < xSize && y - 2 >= 0)
            l.add(new Coords(x + 1, y - 2)); //nahoru doprava
        if (x - 1 >= 0 && y - 2 >= 0)
            l.add(new Coords(x - 1, y - 2)); //nahoru doleva
        if (x - 2 >= 0 && y - 1 >= 0)
            l.add(new Coords(x - 2, y - 1)); //doleva nahoru
        if (x - 2 >= 0 && y + 1 < ySize)
            l.add(new Coords(x - 2, y + 1)); //doleva dolu
        if (x - 1 >= 0 && y + 2 < ySize)
            l.add(new Coords(x - 1, y + 2)); //dolu doleva
        if (x + 1 < xSize && y + 2 < ySize)
            l.add(new Coords(x + 1, y + 2)); //dolu doprava
        if (x + 2 < xSize && y + 1 < ySize)
            l.add(new Coords(x + 2, y + 1)); //doprava dolu
        return l;
    }

    /**
     * Provede tah konem
     * @param x cilova souradnice x
     * @param y cilova souradnice y
     * @param turnNr cislo tahu
     */
    private void takeTurn(int x, int y, int turnNr) {
        solutionBoard[y][x] = turnNr;
        if (turnNr == (xSize * ySize) - 1) {
            solutionsCount++;
            printSolution();
            return;
        } else {
            for (Coords c : getFields(x, y)) {
                if (solutionBoard[c.getY()][c.getX()] == NOT_VISITED) {
                    takeTurn(c.getX(), c.getY(), turnNr + 1);
                    solutionBoard[c.getY()][c.getX()] = NOT_VISITED; //reset policka
                }
            }
        }
    }

    /**
     * Vypise reseni
     */
    private void printSolution() {
        System.out.println("Reseni #" + solutionsCount);
        for (int i = 0; i < solutionBoard.length; i++) {
            for (int j = 0; j < solutionBoard[i].length; j++) {
                System.out.print(solutionBoard[i][j] + " ");
            }
            System.out.println("");
        }
        System.out.println("");
    }
    
    /**
     * @return the solutionsCount
     */
    public int getSolutionsCount() {
        return solutionsCount;
    }    
    
    /**
     * Reprezentuje souradnici
     */
    private class Coords {
        private int x;
        private int y;

        public Coords(int x, int y) {
            this.x = x;
            this.y = y;
        }

        /**
         * @return the x
         */
        public int getX() {
            return x;
        }

        /**
         * @param x the x to set
         */
        public void setX(int x) {
            this.x = x;
        }

        /**
         * @return the y
         */
        public int getY() {
            return y;
        }

        /**
         * @param y the y to set
         */
        public void setY(int y) {
            this.y = y;
        }
    }
}
#include <iostream>
#include <vector>

using namespace std;
/**
 * Resicka jezdcovy prochazky backtrackingem
 * @author Pavel Micka
 */
class KnightsTour {
private:
    /**
     * Priznak nenavstivenosti policka
     */
    static const int NOT_VISITED = -1;
    /**
     * Velikost sachovnice na ose x
     */
    int xSize;
    /**
     * Velikost sachovnice na ose y
     */
    int ySize;
    /**
     * Pocet reseni
     */
    int solutionsCount;
    /**
     * Pole pro reseni
     * 0 -> pocatecni pozice kone
     * 1 -> prvni tah
     * 2 -> druhy tah
     * .
     * .
     * .
     * n -> n-ty tah
     */
    int ** solutionBoard;


    /**
     * Reprezentuje souradnici
     */
    class Coords {
    private:
        int x;
        int y;
    public:
        Coords(int x, int y) {
            this->x = x;
            this->y = y;
        }

        /**
         * @return the x
         */
        int getX() {
            return x;
        }

        /**
         * @param x the x to set
         */
        void setX(int x) {
            this->x = x;
        }

        /**
         * @return the y
         */
        int getY() {
            return y;
        }

        /**
         * @param y the y to set
         */
        void setY(int y) {
            this->y = y;
        }
    };

    /**
     * Vrati policka, na ktera muze kun skocit
     * @param x souradnice kone x
     * @param y souradnice kone y
     * @param v reference na vector, do ktereho budou ulozeny souradnice
     */
    void getFields(int x, int y, vector<Coords> &v) {
        if (x + 2 < xSize && y - 1 >= 0)
            v.push_back(Coords(x + 2, y - 1)); //doprava nahoru
        if (x + 1 < xSize && y - 2 >= 0)
            v.push_back(Coords(x + 1, y - 2)); //nahoru doprava
        if (x - 1 >= 0 && y - 2 >= 0)
            v.push_back(Coords(x - 1, y - 2)); //nahoru doleva
        if (x - 2 >= 0 && y - 1 >= 0)
            v.push_back(Coords(x - 2, y - 1)); //doleva nahoru
        if (x - 2 >= 0 && y + 1 < ySize)
            v.push_back(Coords(x - 2, y + 1)); //doleva dolu
        if (x - 1 >= 0 && y + 2 < ySize)
            v.push_back(Coords(x - 1, y + 2)); //dolu doleva
        if (x + 1 < xSize && y + 2 < ySize)
            v.push_back(Coords(x + 1, y + 2)); //dolu doprava
        if (x + 2 < xSize && y + 1 < ySize)
            v.push_back(Coords(x + 2, y + 1)); //doprava dolu
    }

    /**
     * Provede tah konem
     * @param x cilova souradnice x
     * @param y cilova souradnice y
     * @param turnNr cislo tahu
     */
    void takeTurn(int x, int y, int turnNr) {
        solutionBoard[y][x] = turnNr;
        if (turnNr == (xSize * ySize) - 1) {
            solutionsCount++;
            printSolution();
            return;
        } else {
            vector<Coords> v;
            getFields(x, y, v);
            for(unsigned i = 0; i < v.size(); i++){
                if (solutionBoard[v.at(i).getY()][v.at(i).getX()] == NOT_VISITED) {
                    takeTurn(v.at(i).getX(), v.at(i).getY(), turnNr + 1);
                    solutionBoard[v.at(i).getY()][v.at(i).getX()] = NOT_VISITED; //reset policka
                }
            }
        }
    }

    /**
     * Vypise reseni
     */
    void printSolution() {
        cout << "Reseni #" << solutionsCount << "\\n" ;
        for (int i = 0; i < ySize; i++) {
            for (int j = 0; j < xSize; j++) {
                cout << solutionBoard[i][j] << " ";
            }
            cout << "\\n";
        }
        cout << "\\n";
    }

public:
    /**
     * Konstruktor resitele jezdcovy prochazky
     * @param xSize velikost sachovnice na ose y
     * @param ySize velikost sachovnice na ose y
     */
    KnightsTour(int xSize, int ySize) {
        solutionsCount = 0;

        this->xSize = xSize;
        this->ySize = ySize;

        solutionBoard = new int*[ySize];
        for(int i = 0; i < ySize; i++){
            solutionBoard[i] = new int[xSize];
            for (int j = 0; j < xSize; j++) {
                solutionBoard[i][j] = NOT_VISITED;
            }
        }
    }
    ~KnightsTour(){
        for(int i = 0; i < ySize; i++) delete[] solutionBoard[i];
        delete[] solutionBoard;
    }

    /**
     * Resi jezdcovu prochazku
     */
    void solve() {
        for (int i = 0; i < ySize; i++) {
            for (int j = 0; j < xSize; j++) {
                takeTurn(j, i, 0);
                solutionBoard[i][j] = NOT_VISITED; //reset pole
            }
        }
    }

    /**
     * @return the solutionsCount
     */
    int getSolutionsCount() {
        return solutionsCount;
    }
};




int main(int argc, char* argv[]) {
    KnightsTour t(3, 14);
    t.solve();
    system("pause");
    return 0;
}

Literatura








Doporučujeme