Jezdcova 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

/**
 * 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

Knight's Tour -- from Wolfram MathWorld [online]. 1999-2009 [cit. 2009-09-14]. Dostupný z WWW: <http://mathworld.wolfram.com/KnightsTour.html>.
LÖBBING , Martin, WEGENER, Ingo. The Number of Knight's Tours Equals 33,439,123,484,294 - Counting with Binary Decision Diagrams. [s.l.] : [s.n.], 1996. 14 s. Dostupný z WWW: <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8394>.

Strojové řešení problému

Počet řešení problému

Kód

Literatura

Doporučujeme