#StackBounty: #java #backtracking #n-queens How to find all the solutions for a NQueens problem given the first queen (at first row) is…

Bounty: 50

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("nnTotal: "+t+" --> "+Arrays.toString(board));   
                }
                else {
                    k++; board[k] = -1;
                }
            }
            else {              
                k--;    //  backtrack.              
            }
        }
        
        System.out.println("nnTotal: "+t);
    }
}


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.