Näherungsverfahren 1 SS10

<eval id="1249529jksdf9"> private static final int nx[] = { -2, -2, -1, -1, 1, 1, 2, 2 }; private static final int ny[] = { -1, 1, -2, 2, -2, 2, -1, 1 };</eval>

private static boolean imSchachbrett(int x, int y, int m, int n) { return ((0 <= x && x < m) && (0 <= y && y < n)); }

private static int möglicheSchritte(int a[][], int m, int n, int x, int y) { int anzahl = 0; int xn, yn; for (int i = 0; i < 8; i++) { xn = x + nx[i]; yn = y + ny[i]; if (imSchachbrett(xn, yn, m, n) && a[xn][yn] == 0) anzahl++; } return anzahl; }

static boolean findeBestenWeg(int a[][], int m, int n, int xy[]) { int aux = Integer.MAX_VALUE; int xn, yn, xx = 0, yy = 0; for (int i = 0; i < 8; i++) { xn = xy[0] + nx[i]; yn = xy[1] + ny[i]; if (imSchachbrett(xn, yn, m, n) && a[xn][yn] == 0) { int schritte = möglicheSchritte(a, m, n, xn, yn); if (schritte < aux) { aux = schritte; xx = xn; yy = yn; } } } if (aux < Integer.MAX_VALUE) { xy[0] = xx; xy[1] = yy; return true; } return false; }

int m = 0; int n = 0; int l = 0; int c = 0; n=Integer.parseInt(JOptionPane.showInputDialog(null, "Geben Sie 'n' eines n*m Schachbretts an : ","6")); m=Integer.parseInt(JOptionPane.showInputDialog(null, "Geben Sie 'm' eines n*m Schachbretts an : ","6")); l=Integer.parseInt(JOptionPane.showInputDialog(null, "Geben Sie die x-Koordinate des Springers an: ","2")); c=Integer.parseInt(JOptionPane.showInputDialog(null, "Geben Sie die y-Koordinate des Springers an: ","2")); l--; c--; int[][] a = new int[m][n]; a[l][c] = 1; int ctr = 1; int xy[] = new int[2]; xy[0] = 1; xy[1] = c; while (findeBestenWeg(a, m, n, xy)) { a[xy[0]][xy[1]] = ++ctr; }

if (ctr == m * n) { for (int i = 0; i < n; i++) { System.out.println(); System.out.println(); for (int j = 0; j < n; j++) { System.out.print("\t"+a[i][j] + "\t"); } } }else System.out.println("keine Lösung !!"); }