knighttrip.java

骑士漫游的源程序

/**
 * Copyright 2007 Shanghai cjy.
 * @author cjy 
 */

import java.util.*;

/** 
 * class NumberException
 * when get a number I don't want
 * throw NumberException
 */
class NumberException extends Exception {
	NumberException () {};
}

/**
 * class KnightTrip 
 */
public class KnightTrip {
	/** Packet counters */
	static int currentRow = 0;
	static int currentColumn = 0;
	static final int[] horizontal = {2, 2, 1, -1, -2, -2, -1, 1,}; //骑士共有8种走法，表示每种走法一步在横向上的移动
	static final int[] vertical = {-1, 1, 2, 2, 1, -1, -2, -2,};   //每中走法在纵列上的移动
	static int[][] currentPace = new int[8][8];
	static int row = 0;
	static int col = 0;	
	
	/** Set the packet counters */
	//每走一步，预测后来的两步，以加快程序的速度。
	static boolean check (int[][] currentPace, int[][] pace, int row, int col, int i1) {
		int x = 1;
		int row1, row2;
		int col1, col2;
		for (int a = 0; a < 8; a++) {
			if(row + vertical[a] < 8 && col + horizontal[a] < 8 
					&&  row + vertical[a] >= 0 && col + horizontal[a] >= 0){
				currentPace[row + vertical[a]][col + horizontal[a]]--;	
			}
		}		
		if (i1 == 61 || i1 == 62 || i1 == 60)
			return true;
		for (int a = 0; a < 8; a++) {
			row1 = row + vertical[a];
			col1 = col + horizontal[a];
			if(row1 < 8 && col1 < 8 &&  row1 >= 0 && col1 >= 0){
				if (currentPace[row1][col1] == 0 && pace[row1][col1] == 0){
					return false;
				}
					else if (currentPace[row1][col1] == 1 && pace[row1][col1] == 0) {
					for (int b = 0; b < 8; b++) {
						row2 = row1 + vertical[b];
						col2 = col1 + horizontal[b];
						if (row2 < 8 && col2 < 8 &&	row2 >= 0 && col2 >= 0) {
							if (currentPace[row2][col2] == 1 && pace[row2][col2] == 0) {					
								return false;		
							}							
						} 
					}
				}
			}
		}	
		return true;
	}
	//清除走错的步骤留下的痕迹：
	static void clean (int[][] currentPace, int row, int col) {
		for (int a = 0; a < 8; a++) {
			if(row + vertical[a] < 8 && col + horizontal[a] < 8 
					&&  row + vertical[a] >= 0 && col + horizontal[a] >= 0){
				currentPace[row + vertical[a]][col + horizontal[a]]++;	
			}
		}		
	}
	//打印最后的程序结果：
	static void print (int[][] pace, int row, int col) {
		System.out.println("When start from row: " + row + " column" + col + " The problem have the solution:");
		for (int i3 = 0; i3 < 8; i3++){
			for (int i4 = 0; i4 < 8; i4++){
				if (pace[i3][i4] < 10) 
					System.out.print(pace[i3][i4] + "  ");
				else
					System.out.print(pace[i3][i4] + " ");
			}	
			System.out.println("");
		}
	}
	
	public static void main(String[] args) {
		System.out.println("*******************************************");
		System.out.println("*recommendation: start from row: 5, col: 4*");
		System.out.println("*  if you don't start form row: 5, col: 4 *");
		System.out.println("*     you should waiter a longer time     *");
		System.out.println("*******************************************");
		boolean right = true;
		// 输入的异常处理：
		while(true) {
			try {
				System.out.println("please imput the start row (0-7): ");
				Scanner stdin1 = new Scanner(System.in);
				row = stdin1.nextInt();
				right = true;
				if (row < 0 || row > 7) {
					throw new NumberException();
				}
			}catch (java.util.InputMismatchException e) {			
				right = false;
				System.out.println("Error:You should input a number from 0 to 7");
			}catch(NumberException s) {
				right = false;
				System.out.println("Error:You should input a number from 0 to 7");
			}finally {
				if (right == true) 
					break;
			}
		}				
		while(true) {
			try {
				System.out.println("please imput the start column (0-7): ");
				Scanner stdin1 = new Scanner(System.in);
				col = stdin1.nextInt();
				right = true;
				if (col < 0 || col > 7) {
					throw new NumberException();
				}
			}catch (java.util.InputMismatchException e) {			
				right = false;
				System.out.println("Error:You should input a number from 0 to 7");
			}catch(NumberException s) {
				right = false;
				System.out.println("Error:You should input a number from 0 to 7");
			}finally {
				if (right == true) 
					break;
			}
		}		
		//用于记录每个格子的入度：
		currentPace = new int[][] {{2,3,4,4,4,4,3,2},
				                   {3,4,6,6,6,6,4,3},
				                   {4,6,8,8,8,8,6,4},
				                   {4,6,8,8,8,8,6,4},
				                   {4,6,8,8,8,8,6,4},
				                   {4,6,8,8,8,8,6,4},
				                   {3,4,6,6,6,6,4,3},
				                   {2,3,4,4,4,4,3,2}};;
		for (int a = 0; a < 8; a++) {
			if(row + vertical[a] < 8 && col + horizontal[a] < 8 
					&&  row + vertical[a] >= 0 && col + horizontal[a] >= 0){
				currentPace[row + vertical[a]][col + horizontal[a]]--;	
			}
		}		
		int[][] pace = new int[8][8];   //用于记录在棋盘上走的步数，1标志起始位，2表示第一步，3表示第二步，以此类推。
		int[][] start = new int[63][2]; //用于记录每走一步的所到达的位置，作为下一步的起始位置。
		int[] count = new int[63];      //用于记录每一步是用哪一种走法。
		int i1 = 0;
		int i2 = 0;
		int much = 0;
		boolean bool = true;
		currentRow = row; currentColumn = col;
		pace[currentRow][currentColumn] = 1;

		for (; i1 < 63;) {
			for (; i2 < 8; i2++){       //共有8种走法，依次执行，每次执行一种走法，不可行的话再执行下一种。
				//走出界的情况：
				if (currentRow + vertical[i2] < 8 && currentColumn + horizontal[i2] < 8 
						&&  currentRow + vertical[i2] >= 0 && currentColumn + horizontal[i2] >= 0) {
					//重复走到同一方格的情况：
					if(pace[currentRow + vertical[i2]][currentColumn + horizontal[i2]] == 0)
					{   
						break;}
				}
			}
			//若第i1步的8中走法都不能执行（出界或重复），则退到上一步，为上一步换一种走法。
			if (!bool  || i2 == 8) {
				bool = true;
				i1 = i1 - 1;  //退到上一步。
				for(;i1 > 0 && count[i1] + 1 >= 8 ; i1--) {
					pace[start[i1][0] - 2][start[i1][1] + 1] = 0;
					clean (currentPace, start[i1][0] - 2, start[i1][1] + 1);
				}
				if(i1 < 0) { //不能漫游整个棋盘，退出循环，换一个起始漫游的位置。
					break;	
				}
				i2 = count[i1] + 1;  //count[i1]为上一步所使用的走法
				currentRow = start[i1][0];    //上一步的起始行。
				currentColumn = start[i1][1]; //上一步的起始列。
				clean (currentPace, currentRow + vertical[count[i1]], currentColumn + horizontal[count[i1]]);
				pace[currentRow + vertical[count[i1]]][currentColumn + horizontal[count[i1]]] = 0;//清除这一步在棋盘上的标记。
			}
			else {    
				start[i1][0] = currentRow;    //这一部的起始行。
				start[i1][1] = currentColumn; //这一步的起始列。
				count[i1] = i2;               //这一步用了哪种走法。
				currentRow = currentRow + vertical[i2];  //下一步开始的起始行。
				currentColumn = currentColumn + horizontal[i2];  //下一步开始的起始列。
				pace[currentRow][currentColumn] = i1 + 2;
				bool = check (currentPace, pace, currentRow, currentColumn, i1);
				i2 = 0;
				i1++;
				much++;
				if(i1 > 62) {
					System.out.println ("total pace: " + much);
					print (pace, row, col);
				}
			}
		}	
		if (much == 0) 
			System.out.println("When start: row " + row + ", column " + col + " there is no solution");
	}
}