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;
    	}
    

Log in to reply