Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Lösungsversuch » codezuaufgabe4
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); } } } } } }