算法相关，跳棋问题
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);