Knight's Tour : 5x5 = 1728 : written in Java

HourseJumpMap.java

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package nj.app.ai;

import static java.lang.System.out;

import java.util.*;

/**
 *
 * @author neojou
 */
public class HourseJumpMap {

    class ChessMap {
        protected int[][] map;
        protected int size;
        
        ChessMap(int size) {
            this.size = size;
            map = new int[size][size];

            for (int i=0; i<size; i++)
                for (int j=0; j<size; j++)
                    map[i][j] = 0;            
        }

        ChessMap(ChessMap cm) {
            this.size = cm.getSize();
            map = copyMap(cm.getMap());
        }

        ChessMap(int[][] m) {
            this.size = m.length;
            map = copyMap(m);
        }
        
        public int[][] getMap() {
            return map;
        }
        
        public int[][] copyMap(int[][] m) {
            int[][] r = new int[size][size];

            for (int i=0; i<size; i++)
                for (int j=0; j<size; j++)
                    r[i][j] = m[i][j];            
            
            return r;
        }

        public int getSize() {
            return this.size;
        }
        
        public void setValue(int x, int y, int v) {
            map[y][x] = v;
        }
        
        public int getValue(int x, int y) {
            return map[y][x];
        }
        
        public void show() {
        
            for (int i=0; i<size; i++) {
                for (int j=0; j<size; j++) {
                    out.printf(" %d", map[i][j]);
                }
                out.println(" ");
            }
            
        }
    }

    protected int size;
    protected ChessMap chess_map;
    ArrayList<ChessMap> result;
    
    
    HourseJumpMap(int size) {
        this.size = size;
        chess_map = new ChessMap(size);
        
        result = new ArrayList<ChessMap>();
    }
    
    public void show() {
        show(chess_map);
    }
            
    public void show(ChessMap m) {
        m.show();
    }
    
    public int think(int start_x, int start_y) {
        
        result = new ArrayList<ChessMap>();
        
        think_next(chess_map, start_x, start_y, 1);
        
        int result_num = result.size();
        if ( result_num > 0  ) {
            out.printf("Found %d %n", result_num);
            for (int i=0; i<result_num; i++) {
                ChessMap m = (ChessMap)result.get(i);
                out.printf("Solution [%d] %n", i+1);
                show(m);
            }
            
        } else {
            out.println("Not found");
        }
        
        return result_num;
    }
    
    public int think_next(ChessMap cm, int cx, int cy, int steps) {
        int ret;
        
        if ( cx < 0 || cx >= size ) return 0;
        if ( cy < 0 || cy >= size ) return 0;
        if ( cm.getValue(cx, cy) != 0 ) { // already set
            return 0;
        }

        //ChessMap cm1 = new ChessMap(cm);        
        cm.setValue(cx, cy, steps);
        if ( steps == size*size ) {
            out.println("think_next found");
            cm.show();
            result.add(new ChessMap(cm));
            cm.setValue(cx, cy, 0);
            return 1;
        }
        
        // upper right
        ret = 0;
        ret += think_next(cm, cx+2, cy-1, steps+1);    
        ret += think_next(cm, cx+2, cy+1, steps+1);        
        ret += think_next(cm, cx+1, cy-2, steps+1);       
        ret += think_next(cm, cx+1, cy+2, steps+1);        
        ret += think_next(cm, cx-2, cy-1, steps+1);       
        ret += think_next(cm, cx-2, cy+1, steps+1);       
        ret += think_next(cm, cx-1, cy-2, steps+1);        
        ret += think_next(cm, cx-1, cy+2, steps+1);
        
        cm.setValue(cx, cy, 0);
        if ( ret == 0 ) return 0;
        else return 1;
    }
            
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        HourseJumpMap hjm = new HourseJumpMap(5);
        hjm.show();
        int result_num = 0;
        for (int i=0; i<5; i++) {
            for (int j=0; j<5; j++) {
                result_num += hjm.think(i, j);
            }
        }
        out.printf("total solutions: %d %n", result_num);
    }
    
}