算法相关，跳棋有关问题

算法相关，跳棋问题
http://img.bbs.csdn.net/upload/201404/22/1398133565_611244.jpg
一共21个洞，20颗棋子（1-20编号）每个棋子跳过另一个棋子进入洞中，就可把另一个棋子拿走。
比如棋子3跳过棋子1进入东中，棋子1被拿走，每一步的规则都是必须跳过一个棋子一走，而且必须
跳进洞中。最后的目标是跳刀只剩一粒棋子。
求遍历出所有可行的跳法。
------解决方案--------------------
我算出来有400多亿种走法（43419942138）。
有2个优化方法：
1、可以先把棋盘的状态（有多少棋子，和这些棋子的坐标）缓存起来。下次如果状态一样，就直接从缓存取
2、如果某个时刻棋盘上的棋子是左右对称的，那么也可以跳过一半的计算

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.TimeUnit;

public class Main {

	private int width, height;
	private int[][] array;
	private Point[] point;
	private int[][] result;
	private Map<Key, Long> cache = new HashMap<Key, Long>();
	/* 跳的方向
	 *  6 1
	 * 5 0 2
	 *  4 3
	 */
	private int[][] direction = {{1, -1}, {2, 0}, {1, 1}, {-1, 1}, {-2, 0}, {-1, -1}};

	private static class Point {

		public int x, y, value;

		public Point(int x, int y, int value) {
			this.x = x;
			this.y = y;
			this.value = value;
		}
	}

	private static class Key {

		public int[][] point;

		@Override
		public int hashCode() {
			int hash = 5;
			hash = 23 * hash + Arrays.deepHashCode(this.point);
			return hash;
		}

		@Override
		public boolean equals(Object obj) {
			if (obj == null) {
				return false;
			}
			if (getClass() != obj.getClass()) {
				return false;
			}
			final Key other = (Key) obj;
			if (!Arrays.deepEquals(this.point, other.point)) {
				return false;
			}
			return true;
		}
	}

	public Main(int n) {
		int maxValue = (1 + n) * n / 2 - 1;
		width = n * 2 - 1;
		height = n;
		array = new int[height][width];
		point = new Point[maxValue];
		result = new int[maxValue][2];
		int k = 0;
		for (int y = 0; y < n; y++) {
			Arrays.fill(array[y], -1);
			int s = n - y - 1;
			for (int i = 0; i <= 2 * y; i++) {
				if (i % 2 != 0) {
					array[y][s + i] = 0;
					continue;
				}
				if (k == 0) {
					array[y][s + i] = 0;
				} else {
					array[y][s + i] = k;
					point[k - 1] = new Point(s + i, y, k);
				}
				k++;
			}
		}
		printArray();
	}

	private void printArray() {
		for (int y = 0; y < height; y++) {
			for (int i = 0; i < array[y].length; i++) {
				System.out.format("%2d ", array[y][i]);
			}
			System.out.println();
		}
	}

	public long g() {
		return g(point.length);
	}

	/**
	 * 此时棋盘的形态(依次记录有棋子的格子的坐标)
	 * @param n
	 * @return 
	 */
	private Key buildKey(int n) {
		Key key = new Key();
		key.point = new int[n][2];
		int k = 0;
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				if (array[i][j] > 0) {
					key.point[k++] = new int[]{i, j};
				}
			}
		}
		return key;
	}

	private long g(int n) {
		if (n == 1) {
			for (int i = result.length; i > 1; i--) {
				System.out.format("%2d->%2d ", result[i - 1][0], result[i - 1][1]);
			}
			System.out.println("");
			return 1;
		}
		/* 不使用缓存 */
//		if (1 > 0) {
//			return g2(n);
//		}
		Key key = buildKey(n);
		Long total = cache.get(key);
		if (total != null) {
			//System.out.println("hit:" + total);
			return total;
		}
		long s = g2(n);
		cache.put(key, s);
		return s;
	}

	/**
	 * 此时，棋盘是否对称
	 * @return 
	 */
	private boolean isSymmetrical() {
		int center = width / 2;
		for (int y = 0; y < array.length; y++) {
			for (int i = 1; i <= y; i++) {
				int k = 0;
				k += (array[y][center + i] == 0 ? 0 : 1);