Как использовать рекурсивный backtracking для решения 8 королев?

Question

ОБНОВЛЕННЫЙ КОД: Мой последний вопрос: как мне получить его, чтобы моя программа печатала все 92 решения платы 8x8, без каких-либо угроз? Пока мой код печатает только 1 решение. Например, когда я меняю его на плату 4x4, у меня есть только одно решение, когда должно быть 2, я считаю.

public class Queen{ 

    public static void display(int[] board){ 
     int n = board.length; 
     for(int column = 0; column < n; column++){ 
     for(int row = 0; row < n; row++){ 
      if(board[column] == row) 
       System.out.print('Q'); 
     else 
     System.out.print('x'); 



     } 
     System.out.print('\n'); 
     } 
    } 

    public static int[] solveQueens(int n){ 
     int board[] = new int[n]; 
     placeQueen(board,0); 
     return board; 
    } 
    private static boolean placeQueen(int[] board, int column){ 
     int n = board.length; 
     if (n == column){ 
      return true; 
     }else{ 
      for (int row = 0; row < n; row++){ 
       int i; //remove 
       for (i = 0; i < column; i++){ //for (int i) 
        if (board[i] == row || i - column == board[i] - row || column - i == board[i] - row){ 
         break; 
        } 
       } 
       if (i == column){ 
        board[column] = row; 
        if (placeQueen(board, column + 1)) 
         return true; 
       } 
      } 
     } 
     return false; 
    } 
    public static void main(String args[]){ 
     int finished[] = solveQueens(8); 
     display(finished); 
     } 
    } 

Теперь мои программы возвращение:

Qxxxxxxx 
xxxxQxxx 
xxxxxxxQ 
xxxxxQxx 
xxQxxxxx 
xxxxxxQx 
xQxxxxxx 
xxxQxxxx 

СТАРОГО КОД: мне нужно использовать рекурсивные откаты, чтобы решить эту проблему 8 ферзей. Проблема n-queens - головоломка, которая требует размещения n шахматных королевов на n × n доске, чтобы ни один из ферзей не атаковал друг друга.

Мне нужно написать метод public solveQueens(int n), чтобы решить эту проблему для доски NxN

мне также нужно написать частный метод рекурсивной placeQueen(board, column) попытаться разместить ферзь в указанном столбце.

Это мой код до сих пор:

public class Queen{ 

    public static int[] solveQueens(int n){ 
     int board[] = new int[n]; 
     int finished[] = placeQueen(board,0); 
     return finished; 

    } 
    private static int[] placeQueen(int[] board, int column){ 
     int n = board.length; 
     int row = column; 
     if (n == column){ 
      return board; 
     }else{ 
      for (row = n; row < n; row++){ 
      board[column] = row; 
      if (board[n] == 0 && board[n-1] == 0 && board[n+1] == 0){ 
       board[n] = 1; 
       placeQueen(board, column+1); 
      } 
      } 
     for (row = n; row < n; row++){ 
      board[row] = column; 
      if (board[n] == 0 && board[n-1] == 0 && board[n+1] == 0){ 
       board[n] = 1; 
       placeQueen(board, column+1); 
      } 
      } 
     } 
     return board; 
    } 
    public static void main(String args[]){ 
     int finished[] = solveQueens(8); 
     for (int item: finished){ 
      System.out.print(item); 
     } 
    } 
} 

Всякий раз, когда я запускаю свою программу, она возвращает это

----jGRASP exec: java Queen 
00000000 

Есть ли объяснение о том, как настроить мой 8x8 борту, и как поместите королевы, чтобы они не нападали друг на друга?

Answer 1

Я сделал некоторые изменения в solveQueens и placeQueen:

public class Queen{ 

    public static int[] solveQueens(int n){ 
     int board[] = new int[n]; 
     placeQueen(board,0); //it fills the board 
     return board; 
    } 
    private static boolean placeQueen(int[] board, int column){ 
     int n = board.length; 
     int row; 
     if (n == column){ 
      return true; 
     }else{ 
      for (row = 0; row < n; row++){ 
       int c; 
       for (c=0; c<column; c++){ 
        if (board[c]==row || c-column==board[c]-row || column-c==board[c]-row){ 
         //check if it is safe position (we know 2 queens couldn't place in a same column or row or diameter 
         break; 
        } 
       } 
       if (c==column){ //if previous loop didn't break...=> it is safe position 
        board[column]=row; 
        if (placeQueen(board, column+1)) //if it is possible to fill the rest of board //else: test the next row 
         return true; 
       } 
      } 
     } 
     return false; 
    } 
    public static void main(String args[]){ 
     int finished[] = solveQueens(8); 
     for (int item: finished){ 
      System.out.print(item); 
     } 
    } 
}