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

Question

This is all about the famous NQueens problem. My program works fine (backtrack approach). It finds all the solutions for a given board size. Code is shown below.

I'm trying to modify the code so that I can find all the solutions for a given column of the first queen. I don't want to change the position of first queen. For an example it will provide me with the solution of

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

when I set the first queen at 2, board size 5 (third column, index starts from zero).

I tried this by setting different values for k (and board[k] as well) but doesn't quite reach the goal. Any hints will be appreciated.

Here is my code. Removed details about place method since it shouldn't be changed to achieve my new goal.

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

Just keep k greater than 0 in the while loop:

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

Output:

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

UPDATE

Here is a generalized version that can force a queen at position (fixedRow, fixedCol). The key change is the new getNextCol() method, which is used to get the next possible column for a queen. On row fixedRow, the only possible column is fixedCol. On the other rows, all columns are possible.

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

Output:

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