Algorithmus des N-queens

Algorithm NQueens ( k, n) //Prints all Solution to the n-queens problem
{
    for i := 1 to n do
    {
        if Place (k, i) then
        {
            x[k] := i;
            if ( k = n) then write ( x [1 : n]
            else NQueens ( k+1, n);
        }
    }
}

Algorithm Place (k, i)
{
    for j := 1 to k-1 do
        if (( x[ j ] = //in the same column
           or (Abs( x [ j ] - i) =Abs ( j – k ))) //or in the same diagonal
        then return false;
        return true;
}

Dem obigen code ist für die Lösung des N-Damen-problem mit backtracking.Ich denke, dass es kann legen die ersten 2 queens von zwei Zeilen in den jeweiligen Spalten und dann, wenn es um die 3. Zeile Königin kann es nicht aufgestellt werden, da keine Königin muss angreifen, und es wird einfach die Ausfahrt vom Algorithmus N queens...Also, wie ist dieser Algorithmus implementiert backtracking?

InformationsquelleAutor user2967440 | 2013-11-15

  1. 5

    Das Geheimnis hier ist die Rekursion.

    Lassen Sie jedes level der Einrückung unten deuten auf eine Ebene der Rekursion.

    (nicht das, was tatsächlich geschieht, als der Dritte Königin kann leicht platziert werden, aber es wäre einfach genommen haben, schon ein bisschen mehr schreiben und/oder denken zu bekommen, zu einem Fall, der tatsächlich nicht)

    try to place first queen
success
   try to place second queen
   success
      try to place third queen
      fail
   try to place second queen in another position
   success
      try to place third queen
      success
         try to place fourth queen

    Etwas mehr im Einklang mit dem, was der code tatsächlich tut: (immer noch nicht, was tatsächlich geschieht)

    first queen
i = 1
Can place? Yes. Cool, recurse.
   second queen
   i = 1
   Can place? No.
   i = 2
   Can place? No.
   i = 3
   Can place? Yes. Cool, recurse.
      third queen
      i = 1
      Can place? No.
      i = 2
      Can place? No.
      ... (can be placed at no position)
      fail
      back to second queen
   i = 4
   Can place? Yes. Cool, recurse.
      third queen
      i = 1
      Can place? No.
      ...

    Ich hoffe, das hilft.

    diese Komplexität O_o

    InformationsquelleAutor Dukeling

  2. 0
    public class Problem {

  public static boolean isSafe(int board[][], int row, int col) {
    int n = board.length;

    //check vertical line
    for(int i=0; i < board.length; i++) {
      if(i == row) continue;
      if(board[i][col] == 1) return false;
    }

    //check horizontal line
    for(int j=0; j < n; j++) {
      if(j == col) continue;
      if(board[row][j] == 1) return false;
    }

    //check north east
    for(int i=row-1, j=col+1; i >=0  && j < n; i--, j++) {
      if(board[i][j] == 1) return false;
    }

    //check south east
    for(int i=row+1, j=col+1; i < n && j < n; i++, j++) {
      if(board[i][j] == 1) return false;
    }

    //check north west
    for(int i=row-1, j=col-1; i >=0 && j >=0; i--,j--) {
      if(board[i][j] == 1) return false;
    }

    //check south west
    for(int i=row+1, j=col-1; i<n && j >=0; i++,j--) {
      if(board[i][j] == 1) return false;
    }

    return true;
  }

  public static boolean nQueen(int board[][], int row) {
    if(row == board.length) return true;

    for(int j=0; j < board.length; j++) {
      if(isSafe(board, row, j)) {
        board[row][j] = 1;

        boolean nextPlacement = nQueen(board, row + 1);
        if(nextPlacement) return true;
        board[row][j] = 0;
      }
    }
    return false;
  }

  public static void displayResult(int board[][]) {
    int n = board.length;
    for(int i=0; i < n; i++) {
      for(int j=0; j < n; j++) {
        System.out.print(board[i][j] + " ");
      }
      System.out.println();
    }
  }

  public static void util(int board[][]) {
    int n = board.length;
    boolean result = nQueen(board, 0);
    if(result) {
      System.out.println(n + " queens can be placed in following arragement");
      displayResult(board);
    }
    else {
      System.out.println("Not possible to place " + n + " queens in " + n + " X " + n + " board");
    }
    System.out.println();
  }

  public static void main(String[] args) {
    util(new int[3][3]);
    util(new int[4][4]);
    util(new int[2][2]);
    util(new int[5][5]);
    util(new int[8][8]);
    util(new int[16][16]);
  }

}

    InformationsquelleAutor Juvenik

  3. -1

    Habe ich code für diese ohne Verwendung von backtracking, aber das schöne ist, es ist mit Zeit-Komplexität von big-oh(n).

    //when n is even...
for(j=1;j<=n/2;j++)
{
    x[j]=2*j;
};
i=1;
for(j=n/2 +1 ;j<=n;j++)
{
    x[j] =i;
    i=(2*i)+1;
}

//when n is odd..
i=0;
for(j=1;j<=(n/2+1);j++)
{
    x[i] = (2*i)+1;
    i++;
}
i=1;
for(j=(n/2+2);j<=n;j++)
{
    x[j] = 2*i;
    i++;
}

    Dieser code funktioniert gut und gibt eine Lösung, aber jetzt bin ich auf der Suche immer alle möglichen Lösungen mit diesem Algorithmus.

    InformationsquelleAutor Rachna Raj

Schreibe einen Kommentar