8 Queen Problem ohne Backtracking
-
Hi,
wie findet ihr diese Loesung. Echt hammer oder. Meines Erachtens benutzt er nicht mal backtracking. Dabei ist doch das 8 Damen Problem fuer Backtracking gerade praedestiniert.
Er benutzt auch kein 2D Array. Er gibt alle Loesungen des 8 Damen Problems aus. Also 92 Stueck.
Die meisten Programmierer brauchen da schon mal die doppelte Zeilen Anzahl..public class NQueens { private static int[] b = new int[8]; private static int s = 0; static boolean unsafe(int y) { int x = b[y]; for (int i = 1; i <= y; i++) { int t = b[y - i]; if (t == x || t == x - i || t == x + i) { return true; } } return false; } public static void putboard() { System.out.println("\n\nSolution " + (++s)); for (int y = 0; y < 8; y++) { for (int x = 0; x < 8; x++) { System.out.print((b[y] == x) ? "|Q" : "|_"); } System.out.println("|"); } } public static void main(String[] args) { int y = 0; b[0] = -1; while (y >= 0) { do { b[y]++; } while ((b[y] < 8) && unsafe(y)); if (b[y] < 8) { if (y < 7) { b[++y] = -1; } else { putboard(); } } else { y--; } } } }
-
Das ist eigentlich straight-forward. Das Backtracking ist nicht so sichtbar, weil die Lösung nicht rekursiv ist. Und ich hoffe mal, du würdest nicht ernsthaft mit einem 2D-Array anfangen, wenn du mal 30s vorher nachdenkst.
-
Ums nochmal explizit zu sagen: Zeile 44 ist Backtracking.
-
SG1 schrieb:
Ums nochmal explizit zu sagen: Zeile 44 ist Backtracking.
OK. Das heisst Backtracking muss nicht unbedingt rekursiv bedeuten. Hm...
Klar man kann ja alles rekursive auch iterativ formulieren...ODER
-
meinen Programmierkenntnisse sagt eher diese Loesung hier zu. Hier wird auch ein 2D Array verwendet.
Zeilenanzahl ist aber schon mal das doppelte. Aber halt verstaendlicher.http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/
-
Was muss ich hier hinzufuegen damit er mir nicht nur EINE sondern ALLE Loesungen ausgibt ?
boolean solve(int y) { if(y>=dim) { printBoard(); return true; } for(int i=0;i<dim;i++) { if(isSafe(i,y)) { board[i][y] = 1; if(solve(y+1)) { return true; } else { board[i][y]=0; } } } return false; }
-
So hier die Loesung um alle Moeglichkeiten auszugeben...
boolean solve(int y) { if(y==dim) { printBoard(); return true; } for(int i=0;i<dim;i++) { if(!used[i]) { if(isSafe(i,y)) { board[i][y] = 1; used[i] = true; solve(y+1); board[i][y]=0; used[i] = false; } } } return false; }