knight.java

黑白棋问题 计算机博弈是一种对策性游戏,是人工智能的主要研究领域之一,它涉及人工智能中的搜索方法、推理技术和决策规划等.目前广泛研究的是确定的、二人、零和、完备信息的博弈搜索.

package algo;
/*
 * Tama问题
 */
public class Knight {
	int map[][];
	int size;
	int ans;
	
	public void Init(int m, int n){
		map = new int[m+4][n+4];
		int i,j;
		for(i=0;i<map.length;i++){
			map[i][0] = map[i][1] = map[i][map[0].length-2] = map[i][map[0].length-1] = -1;
			for(j = 2;j<map[0].length-2;j++)
				map[i][j] = 0;
		}
		
		for(i=2;i<map[0].length-2;i++)
			map[0][i] = map[1][i] = map[map.length-2][i] = map[map.length-1][i] = -1;
		
		size = m*n+1;
		ans = 0;
	}
	
	public static void main(String []args){
		Knight k = new Knight();
		k.Init(6,6);		//以6*6的棋盘为例
		k.Solve();
	}
	
	public void Solve(){
		map[2][2] = 1;
		try{
			dfs_search(4, 3, 1);
		}
		catch(Exception e){
			int i,j;
			for(i=0;i<map.length;i++){
				for(j=0;j<map[i].length;j++)
					System.out.print(map[i][j]+"\t");
				System.out.println();
			}
			e.printStackTrace();
		}
		if(ans == 0)
			System.out.println("No solution");	//无解
	}
	
	private void dfs_search(int x, int y, int depth){
		//穷举所有可能路线，只适用于较小的棋盘
		if(depth == size -1 )
			if( x == 2 && y ==2){				//找到一种路线
			ans++;
			int i,j;
			System.out.println("Solution #"+ans);
			for(i=2;i<map.length-2;i++){
				for(j=2;j<map[i].length-2;j++)
					System.out.print(map[i][j]+"\t");
				System.out.println();
			}
			return;
		}
		
		if(map[x][y] != 0)
			return;
		
		int temp = map[x][y];
		map[x][y] = depth+1;

		dfs_search(x-1, y-2, depth+1);
		dfs_search(x+1, y-2, depth+1);
		dfs_search(x-2, y-1, depth+1);
		dfs_search(x+2, y-1, depth+1);
		dfs_search(x-2, y+1, depth+1);
		dfs_search(x+2, y+1, depth+1);
		dfs_search(x-1, y+2, depth+1);
		dfs_search(x+1, y+2, depth+1);
		
		map[x][y] = temp;
	}
}