

public class Jul14_Backtrack {
	public static void main(String[] args) {
		boolean[][] brd = new boolean[][] { { true, true, true }, { true, true, true, false, true },
				{ true, true, true }, { true, false, true, true } };

		int[][] sol = new int[][] { { 4, 13, 6, -1, -1 }, { 7, 10, 3, -1, 1 }, { 12, 5, 8, -1, -1 },
				{ 9, -1, 11, 2, -1 }, };

		testExists(brd, 0, 3, false);
		testExists(brd, 2, 4, false);
		testExists(brd, 3, 4, false);
		testExists(brd, 3, 3, true);
		testExists(brd, 0, 0, true);
		testExists(brd, 2, 2, true);

		int[][] t = allocateSolutionArray(brd, 5);
		testallocateSolutionArray(brd, 5, sol);

		int[][] solTest = allocateSolutionArray(brd, 5);
		solve(brd, solTest, 13, 1, 4, 1);
		print(solTest);
		org.junit.Assert.assertArrayEquals(sol, solTest);

		System.out.println("Test OK");
	}

	public static boolean exists(boolean[][] brd, int r, int c) {

		if (r < 0 || c < 0 || r >= brd.length || (brd[r] == null || c >= brd[r].length))
			return false;

		return true;
	}

	public static int[][] allocateSolutionArray(boolean[][] brd, int mrl) {
		int[][] sol = null;

		sol = new int[brd.length][mrl];
		for (int y = 0; y < brd.length; y++) {
			for (int x = 0; x < mrl; x++) {

				if (x < brd[y].length && !brd[y][x]) {
					sol[y][x] = -1;

				} else if (x >= brd[y].length) {
					sol[y][x] = -1;
				}
			}
		}

		return sol;
	}

	public static boolean solve(boolean[][] brd, int[][] sol, int tf, int r, int c, int n) {
		int[][] jumps = { { r + 2, c - 1 }, { r + 1, c - 2 }, { r - 1, c - 2 }, { r - 2, c - 1 }, { r - 2, c + 1 },
				{ r - 1, c + 2 }, { r + 1, c + 2 }, { r + 2, c + 1 } };
		
		
		if (n == tf) {
			sol[r][c] = n; // Letze Möglichkeit z.B. Start ist einzigste Möglichkeit			
			return true;
		}

		for (int[] jump : jumps) {
			if (exists(brd, jump[0], jump[1]) && sol[jump[0]][jump[1]] == 0) {
				sol[r][c] = n;

				boolean res = solve(brd, sol, tf, jump[0], jump[1], n + 1);
				if (res) {
					return true;
				}

				sol[r][c] = 0;
			}

		}

		return false;
	}

	private static void print(int[][] solTest) {
		for (int[] s : solTest) {
			for (int i = 0; i < s.length; i++) {
				if (s[i] == -1) {
					System.out.print("| x ");
				} else if (s[i] < 10) {
					System.out.print("| " + s[i] + " ");
				} else {
					System.out.print("|" + s[i] + " ");
				}
			}
			System.out.println("|");
		}
	}

	private static void testExists(boolean[][] brd, int r, int c, boolean expect) {
		org.junit.Assert.assertTrue(exists(brd, r, c) == expect);
	}

	private static void testallocateSolutionArray(boolean[][] brd, int mrl, int[][] sol) {
		int[][] test = allocateSolutionArray(brd, mrl);

		for (int i = 0; i < brd.length; i++) {
			for (int j = 0; j < brd[i].length; j++) {
				for (int k = j; k < sol.length; k++) {

					if (brd[i][j]) {
						org.junit.Assert.assertTrue(sol[i][j] >= 0);
					} else {
						org.junit.Assert.assertTrue(sol[i][j] < 0);

					}

					if (k == brd[i].length) {
						org.junit.Assert.assertTrue(sol[i][k] < 0);
					}

				}
			}
		}

	}

}