给定一个皇后固定在某一列，如何找到 NQueens 问题的所有解决方案？

Question

这就是著名的 NQueens 问题。我的程序运行良好（回溯方法）。它找到给定电路板尺寸的所有解决方案。代码如下所示。

我正在尝试修改代码，以便我可以找到第一个皇后的给定列的所有解决方案。我不想更改的位置第一位女王。例如，它将为我提供

的解决方案

  [2, 0, 3, 1, 4] and [2, 4, 1, 3, 0]

当我将第一个皇后设置为 2 时，棋盘大小为 5（第三列，索引从零开始）。

我通过为 k（以及 board[k]）设置不同的值来尝试这个，但没有完全达到目标。 如有任何提示，我们将不胜感激。

这是我的代码。删除了有关 place 方法的详细信息，因为不应更改它来实现我的新目标。

public class NQueensAllSolutions
{
    //  Board size
    static int size = 8;
    
    //  One dimensional array to store the column number for all queens.
    static int[] board = new int[size];
    
    //  This method will check the validity for a new queen. works fine.
    static boolean place(int k)
    {
        .
        .       
    }
    
    
    public static void main(String[] args) 
    {
        int k;
        
        long t=0;   //  for counting total found solutions

        k = 0;
        board[k] = -1;      

        while(k >= 0) {

            board[k]++;

            while(board[k] < size && !(place(k))) board[k]++;

            if(board[k] < size) {
                if(k == size-1) {   //  a solution is found.
                    
                    t++;                    
                    
                    //System.out.println("\n\nTotal: "+t+" --> "+Arrays.toString(board));   
                }
                else {
                    k++; board[k] = -1;
                }
            }
            else {              
                k--;    //  backtrack.              
            }
        }
        
        System.out.println("\n\nTotal: "+t);
    }
}

Answer 1

在while循环中保持k大于0：

import java.util.Arrays;

public class Queens
{
    static int size = 5;
    static int[] board = new int[size];

    static boolean isValid(int k)
    {
        int c1 = board[k];
        int c2 = board[k];
        for(int r=k-1;r>=0;r--)
        {
            c1--;
            c2++;
            if(board[r] == board[k] || board[r] == c1 || board[r] == c2)
                return false;
        }
        return true;
    }

    public static void main(String[] args) 
    {
        int t = 0;

        // Set the first queen position
        board[0] = 2;

        int k = 1;
        board[k] = -1;

        // k must stay greater than 0
        while(k >= 1) {
            board[k]++;
            while(board[k] < size && !isValid(k))
                board[k]++;
            if(board[k] < size) {
                if(k == size-1) {
                    t++;
                    System.out.println("Solution "+t+" --> "+Arrays.toString(board));
                }
                else {
                    k++;
                    board[k] = -1;
                }
            }
            else {
                k--;
            }
        }
    }
}

输出：

Solution 1 --> [2, 0, 3, 1, 4]
Solution 2 --> [2, 4, 1, 3, 0]

更新

这是一个通用版本，可以在位置 (fixedRow, fixedCol) 处强制皇后。关键变化是新的 getNextCol() 方法，用于获取皇后的下一个可能列。在行 fixedRow 上，唯一可能的列是 fixedCol。在其他行上，所有列都是可能的。

import java.util.Arrays;

public class Queens
{
    static int size = 5;
    static int fixedRow = 2;
    static int fixedCol = 0;
    static int[] board = new int[size];

    static boolean isValid(int k)
    {
        int c1 = board[k];
        int c2 = board[k];
        for(int r=k-1;r>=0;r--)
        {
            c1--;
            c2++;
            if(board[r] == board[k] || board[r] == c1 || board[r] == c2)
                return false;
        }
        return true;
    }

    static int getNextCol(int k, int col)
    {
        if(k == fixedRow) {
            // Only one possible move on this row
            return col == -1 ? fixedCol : size;
        }
        else {
            // Try the next column
            return col+1;
        }
    }

    public static void main(String[] args) 
    {
        int t = 0;
        int k = 0;
        board[k] = -1;

        while(k >= 0) {
            board[k] = getNextCol(k, board[k]);
            while(board[k] < size && !isValid(k))
                board[k] = getNextCol(k, board[k]);
            if(board[k] < size) {
                if(k == size-1) {
                    t++;
                    System.out.println("Solution "+t+" --> "+Arrays.toString(board));
                }
                else {
                    k++;
                    board[k] = -1;
                }
            }
            else {
                k--;
            }
        }
    }
}

输出：

Solution 1 --> [1, 3, 0, 2, 4]
Solution 2 --> [4, 2, 0, 3, 1]

给定一个皇后固定在某一列，如何找到 NQueens 问题的所有解决方案？

How to find all the solutions for a NQueens problem given that one queen is fixed at some column?

java

arrays

backtracking