不同起点的八皇后算法

Question

无论起点如何，我都在努力寻找八皇后问题的解决方案。下面是我的求解器 class，但是当我将皇后放在第一行以外的一行时，由于某种原因它不起作用。

import java.util.*; 
public class Queens {
  private static int x;
  private static int y;
  private static ArrayList<Integer> rows = new ArrayList<Integer>();
  public Queens(int index, int row, int pos) {

    for (int i = 0; i<index; i++)
      rows.add(i);
    rows.remove(row);
    x = pos;
    y = row;
  }

public static boolean solve(int row, int[][] board, int N, int pos) {
    board[y][x] = 1;
    System.out.println("row: " + row);
    for(int i = 0; i < 8; i++) {
      for(int j = 0; j < 8; j++) {
        if(board[i][j]==1) System.out.print("Q ");
        else System.out.print("* ");
      }
      System.out.println();
    }
    System.out.println();    
    if(row>=N-1) return true;
    for(int position = pos; position < N; position++) {
      if(isValid(board, rows.get(row), position, N)) {
        board[rows.get(row)][position] = 1;
        if(!solve(row+1, board, N, 0)) {
          board[rows.get(row)][position] = 0;
        } else
          return true;
      }
    }
    return false;
  }

  public static boolean isValid(int[][] board, int y, int x, int N) {
    int i, j;
    for(i = 0; i < y; i++)
      if(board[i][x]==1)
        return false;
    i = y - 1;
    j = x - 1;
    while((i>=0)&&(j>=0))
      if(board[i--][j--]==1) return false;
    i = y - 1;
    j = x + 1;
    while((i>=0)&&(j<N))
      if(board[i--][j++]==1) return false;
    return true;
  }
}

例如，当我将初始女王放在棋盘[2][2]上时，这是我得到的解决方案：

Q * * * * * * * 
* * Q * * * * * 
* * Q * * * * * 
* * * * * Q * * 
* * * * * * * Q 
* Q * * * * * * 
* * * Q * * * * 
* * * * * * Q *

代码有什么问题？为什么它无视最初的作品？提前致谢。

Answer 1

isValid 中 for 循环的界限是什么？它们是否会阻止您将女王放置在下面有另一个女王的列中？

一个类似的问题也适用于 while 循环——它们能否检测到对角线上有一个皇后但低于您现在放置的皇后？

不同起点的八皇后算法

Eight Queens Algorithm for Different Starting Points

java

algorithm

recursion

backtracking