[数据结构与算法]Warnsdorff‘s algorithm 完成骑兵游行（Knight tour）问题

问题描述：

在一个8x8（或者nxn）的棋盘上，一个骑兵（马）走日（对角）能否遍历整个棋盘。

http://en.wikipedia.org/wiki/Knight%27s_tour

Warnsdorff's algorithm: Heruistic?剪枝，排除不需要的回溯路

规则如下两条：

1）我们可以从棋盘上任意一处开始移动

2）我们每次移动到最近，最狭隘（周围没遍历过点最少）的点（be more greedy!）

算法的基本结构：

1.?任意选取点P为棋盘上起点

2.?标记P为1

3.?重复以下动作从2-64：

? ? ? ? 1. S?作为P能移动到的点的set

? ? ? ? 2.?标记P?为S里最小accesibility

? ? ? ? 3.?标记P?为现在的移动次数

4.?返回标记的数组

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

public class knight_tour {
	
	public static final int N = 8;
	
    //cx,cy记录可以移动的位置 8 种
	public static final int cx[] = {1, 1, 2, 2, -1, -1, -2, -2};
    public static final int cy[] = {2, -2, 1, -1, 2, -2, 1, -1};
	
    class Cell {
        int x;
        int y;
     
        public Cell(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }
    
    //判断是否在棋盘内
    boolean limits(int x, int y) {
        return ((x >= 0 && y >= 0) && (x < N && y < N));
    }
    
    //判断是否能走
    boolean isempty(int a[], int x, int y){
        return (limits(x, y)) && (a[y * N + x] < 0);
    }
    
    //找到每个点的degree 方便选择剪枝
    int getDegree(int a[], int x, int y) {
        int count = 0;
        for (int i = 0; i < N; ++i)
            if (isempty(a, (x + cx[i]),(y + cy[i])))
                count++;
        return count;
    }
    
    // 选择下一个位置
    Cell nextMove(int a[], Cell cell)
    {
        int min_deg_idx = -1, c,
            min_deg = (N + 1), nx, ny;
 
        //随机选一个开始点
        int start = ThreadLocalRandom.current().nextInt(1000) % N;
        for (int count = 0; count < N; ++count) {
            int i = (start + count) % N;
            nx = cell.x + cx[i];
            ny = cell.y + cy[i];
            if ((isempty(a, nx, ny)) && (c = getDegree(a, nx, ny)) < min_deg) {
                min_deg_idx = i;
                min_deg = c;
            }
        }
 
        if (min_deg_idx == -1)
            return null;
 
        nx = cell.x + cx[min_deg_idx];
        ny = cell.y + cy[min_deg_idx];
 
        a[ny * N + nx] = a[(cell.y) * N + (cell.x)] + 1;
        cell.x = nx;
        cell.y = ny;
 
        return cell;
    }
    
    void print(int a[]) {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j)
                System.out.printf("%d\t", a[j * N + i]);
            System.out.printf("\n");
        }
    }
    
    boolean neighbour(int x, int y, int xx, int yy) {
        for (int i = 0; i < N; ++i)
            if (((x + cx[i]) == xx) &&((y + cy[i]) == yy))
                return true;
        return false;
    }
    
    boolean findClosedTour() {
        int a[] = new int[N * N];
        for (int i = 0; i < N * N; ++i)
            a[i] = -1;
 
        int sx = 3;
        int sy = 2;

        Cell cell = new Cell(sx, sy);
 
        a[cell.y * N + cell.x] = 1;
        Cell ret = null;
        for (int i = 0; i < N * N - 1; ++i)
        {
            ret = nextMove(a, cell);
            if (ret == null)
                return false;
        }
        if (!neighbour(ret.x, ret.y, sx, sy))
            return false;
 
        print(a);
        return true;
    }
    
    public static void main(String[] args)
    {
        while (!new knight_tour().findClosedTour())
        {
            ;
        }
    }
}