/**
 * 
 */
package algorithm;

/**
 *
 */
public class ChessHorse {

    /**
     * use buffer printer instead of System.out can enhance IO performance
     *
     */
    private class BufferPrinter {
        private static final int BUFFER_SIZE = 10240;
        private StringBuffer sb;
        
        public BufferPrinter() {
            sb = new StringBuffer();
        }
        
        public void close() {
            System.out.print(sb.toString());
            sb = null;
        }
        
        public void print(String s) {
            sb.append(s);
            if (sb.length() > BUFFER_SIZE) {
                System.out.print(sb.toString());
                sb = new StringBuffer();
            }
        }
        
        public void println() {
            print("\n");
        }

        public void println(String s) {
            print(s + "\n");
        }
        
    }
    
    /**
     * a simple stack class to store track information of the horse
     * it can print itself using bufferprinter
     *
     */
    private class Track {
        private int p = -1;
        private BufferPrinter printer;
        
        private int[][] track = new int[boardLength*boardHeight][2];
        
        public Track() {
            init();
        }
        
        public void init() {
            // init track
            for (int i = 0; i < boardLength*boardHeight; i ++) {
                for (int j = 0; j < 2; j ++) {
                    track[i][j] = -1;
                }
            }
            
            // init pointer
            p = -1;
        }
        
        public boolean isFull() {
            return p == boardLength*boardHeight - 1;
        }
        
        public void pop() {
            track[p][0] = -1;
            track[p][1] = -1;
            p --;
        }
        
        public void print() {
            if (printer == null) {
                printer = new BufferPrinter();
            }
            
            int[][] sequence = new int[boardLength][boardHeight];
            for (int i = 0; i < boardLength*boardHeight; i ++) {
                sequence[track[i][0]][track[i][1]] = i;
            }
            printer.println("------------------------------------------------------------------");
            for (int i = 0; i < boardLength; i ++) {
                for (int j = 0; j < boardHeight; j ++) {
                    printer.print(sequence[i][j] + "\t");
                }
                printer.println();
            }
        }
        
        public void push(int x, int y) {
            p ++;
            track[p][0] = x;
            track[p][1] = y;
        }
        
        public void setBufferPrinter(BufferPrinter printer) {
            this.printer = printer;
        }
        
        public int size() {
            return p + 1;
        }
        
    }
    
    
    
    /**
     * the array to store adjacent situation
     * when no track is on the 8*8 chess board, the situation like this
     * 2　3　4　4　4　4　3　2   
     * 3　4　6　6　6　6　4　3   
     * 4　6　8　8　8　8　6　4   
     * 4　6　8　8　8　8　6　4   
     * 4　6　8　8　8　8　6　4   
     * 4　6　8　8　8　8　6　4   
     * 3　4　6　6　6　6　4　3   
     * 2　3　4　4　4　4　3　2 
     * 
     * for example
     * there are two point{(1, 2), (2, 1)} [not visited] that can jump to (0, 0)
     */
    private int[][] adjacency = null;
    
    /** 
     * the height of the chessboard, default value is 8
     */
    private int boardHeight = 8;
    
    /**
     * the length of the chessboard, default value is 8
     */
    private int boardLength = 8;
    
    /**
     * constant offset array of x-axis
     */
    private final int[] offsetx = {-2, -1, 1, 2, 2, 1, -1, -2};
    
    /**
     * constant offset array of y-axis
     */
    private final int[] offsety = {-1, -2, -2, -1, 1, 2, 2, 1};
    
    /**
     * the buffer printer can enhance print performance
     */
    private BufferPrinter printer = null;
    
    /**
     * the track is a stack object which keeps track information of the horse.
     */
    private Track track = null;
    
    /**
     * the bool 2D array to store visit situation
     */
    private boolean[][] visited = null;
    
    /**
     * current position in x-axis
     */
    private int x = 0;

    /**
     * current position in y-axis
     */
    private int y = 0;
    
    public ChessHorse() {
        printer = new BufferPrinter();
        track = new Track();
        track.setBufferPrinter(printer);
    }
    
    /**
     * generate a best visit path on greedy perspective
     * @return int[] an array of int ,is index of offsetx and offsety.
     */
    private int[] getGreedyPath() {
        int[] index = {0, 1, 2, 3, 4, 5, 6, 7};
        int[] indexAdj = new int[8];
        
        for (int i = 0; i < 8; i ++) {
            if (isLegalJump(x, y, offsetx[i], offsety[i])) {
                indexAdj[i] = adjacency[x + offsetx[i]][y + offsety[i]];
            } else {
                indexAdj[i] = -1;
            }
        }
        
        // sort indexAdj couple index with bubble
        for (int i = 0; i < 8; i ++) {
            for (int j = i + 1; j < 8; j ++) {
                if (indexAdj[i] > indexAdj[j]) {
                    int temp = indexAdj[j];
                    indexAdj[j] = indexAdj[i];
                    indexAdj[i] = temp;
                    
                    temp = index[j];
                    index[j] = index[i];
                    index[i] = temp;
                }
            }
        }
        
        // generate result array
        int si;
        for (si = 0; si < 8 && indexAdj[si] == -1; si ++);
        int[] result = new int[8 - si];
        for (int i = 0; i < 8 - si; i ++) {
            result[i] = index[si + i];
        }
        
        return result;
    }
    
    /**
     * init the game
     * @param startx start position of x
     * @param starty start position of y
     */
    private void init(int startx, int starty) {
        
        visited = new boolean[boardLength][boardHeight];
        adjacency = new int[boardLength][boardHeight];
        track.init();
        
        // init visited and adjacency
        for (int i = 0; i < boardLength; i ++) {
            for (int j = 0; j < boardHeight; j ++) {
                visited[i][j] = false;
                adjacency[i][j] = 0;
                for (int k = 0; k < 8; k ++) {
                    if (isLegalJump(i, j, offsetx[k], offsety[k])) {
                        adjacency[i][j] ++;
                    }
                }
            }
        }
        
        // start point (startx,starty)
        x = startx;
        y = starty;
        
        // start point is initially visited
        visited[x][y] = true;
        
        // decrease adjacency by 1
        updateAdjacency(-1);
        
        track.push(x, y);
        
    }
    
    /**
     * test is it able to jump from (x, y) to (x + offsetx, y + offsety)
     * @param x
     * @param y
     * @param offsetx
     * @param offsety
     * @return
     */
    private boolean isLegalJump(int x, int y, int offsetx, int offsety) {
        int newx = x + offsetx;
        int newy = y + offsety;
        return (newx >= 0 && newx < boardLength) 
                && (newy >= 0 && newy < boardHeight) 
                && !visited[newx][newy];
    }
    
    /**
     * recursive jump
     * @param offx
     * @param offy
     */
    private void jump(int offx, int offy) {
        x = x + offx;
        y = y + offy;
        
        // visited
        visited[x][y] = true;
        
        // decrease adjacency by 1
        updateAdjacency(-1);
        
        // register track
        track.push(x, y);
        
        // all is visited
        if (track.isFull()) {
            track.print();
            return;
        }
        
        // best path
        int[] path = getGreedyPath();
        for (int i = 0; i < path.length; i ++) {
            jump(offsetx[path[i]], offsety[path[i]]);
            reverseJump(offsetx[path[i]], offsety[path[i]]);
        }
    }
    
    /**
     * reverse the jump
     * @param offsetx
     * @param offsety
     */
    private void reverseJump(int offsetx, int offsety) {
        // restore board status
        visited[x][y] = false;
        
        // increase adjcency by 1
        updateAdjacency(1);
        
        track.pop();
        
        // restore position
        x = x - offsetx;
        y = y - offsety;
    }
    
    /**
     * set the height of chess board
     * @param boardHeight
     */
    public void setBoardHeight(int boardHeight) {
        this.boardHeight = boardHeight;
    }

    /**
     * set the length of chess board
     * @param boardLength
     */
    public void setBoardLength(int boardLength) {
        this.boardLength = boardLength;
    }

    /**
     * start game
     *
     */
    public void start() {
        printer.println("program start...");
        
        // try all possible start point
        for (int i = 0; i < boardLength; i ++) {
            for (int j = 0; j < boardHeight; j ++) {
                printer.println("start point (" + i + ", " + j + ")");
                init(i, j);
                
                int[] path = getGreedyPath();
                for (int k = 0; k < 8; k ++) {
                    jump(offsetx[path[k]], offsety[path[k]]);
                    reverseJump(offsetx[path[k]], offsety[path[k]]);
                }
                
                printer.println();
            }
        }
        
        printer.println("program stop...");
        printer.close();
    }

    /**
     * update the adjacency information stores in the array
     * @param delta the value to change
     */
    private void updateAdjacency(int delta) {
        for (int i = 0; i < 8; i ++) {
            int newx = x + offsetx[i];
            int newy = y + offsety[i];
            if (newx >= 0 && newx < boardLength 
                    && newy >= 0 && newy < boardHeight) {
                adjacency[newx][newy] += delta;
            }
        }
    }
    
    public static void main(String[] args) {
        ChessHorse ch = new ChessHorse();
        ch.setBoardLength(8);
        ch.setBoardHeight(8);
        ch.start();
    }
}