8格骑士巡游的不完全回溯法
.import java.util.Scanner;public class KnightSeemsRight {public static final int MAX_EXITS = 8;public static final int SIDE_LENGTH = 8;static int[][] board = new int[SIDE_LENGTH][SIDE_LENGTH];static int[] nexti = new int[MAX_EXITS];static int[] nextj = new int[MAX_EXITS];static int npos;static int kti, ktj;static int[] ktmove1 = { -2, -1, 1, 2, 2, 1, -1, -2 };static int[] ktmove2 = { 1, 2, 2, 1, -1, -2, -2, -1 };static int[] exits = new int[MAX_EXITS];public static void main(String args[]) { Scanner input = new Scanner(System.in);System.out.printf("骑士巡游问题\n");boolean flag=false;while(true){while (true) {System.out.printf("输入骑士的开始位置:\n");kti = input.nextInt();ktj = input.nextInt();kti--;ktj--;// 从0开始，所以只到7而已if (!((kti >= 0) && (kti < MAX_EXITS)) || // 超出边界出错!((ktj >= 0) && (ktj < MAX_EXITS))) {System.out.printf("输入错误\n");continue;}break;}knight_tour();} }public static void knight_tour() {int i, j, k, l, m, min;int starti, startj;for (i = 0; i < SIDE_LENGTH; i++)for (j = 0; j < SIDE_LENGTH; j++)board[i][j] = 0;board[kti][ktj] = 1;starti = kti;startj = ktj;for (m = 1; m <= 63; m++) {npos = 0;for (k = 0; k < MAX_EXITS; k++) { // 试各个方向i = kti + ktmove1[k];j = ktj + ktmove2[k];if (i >= 0 && i < MAX_EXITS && j >= 0 && j < MAX_EXITS&& board[i][j]==0) { // 可行nexti[npos] = i;nextj[npos] = j;npos++;}}if (npos == 0) {System.out.printf("Knight tour failed at m = %d.\n", m);break;} else if (npos == 1)min = 0;else {for (l = 0; l < npos; l++)exits[l] = 0;min = 0;for (l = 0; l < npos; l++) {for (k = 0; k < MAX_EXITS; k++) {i = nexti[l] + ktmove1[k];j = nextj[l] + ktmove2[k];if (i >= 0 && i < MAX_EXITS && j >= 0 && j < MAX_EXITS&& board[i][j]==0) {exits[l]++;}}if (exits[l] < exits[min])min = l;}}kti = nexti[min];ktj = nextj[min];board[kti][ktj] = m;}//输出for (i = 0; i < SIDE_LENGTH; i++) {for (j = 0; j < SIDE_LENGTH; j++)if (i == starti && j == startj)System.out.printf("%4s", "K");elseSystem.out.printf("%4d", board[i][j]);System.out.printf("\n");}//输出}}