Jezdcova procházka

/**
 * 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 y
     * @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;
}