CODEWITHSUNDEEP
javaalgorithm
b3gun
b3gun

Reputation: 53

Queens exercise in java using stacks

I'm kind of new to programming, and i have this assignment to solve the N Queens problem. I don't know what wrong with my code, and i kind of spent a lot of time. Could anyone help me out by guiding me to the right direction ?

public static boolean isSafe(int[] col, int size, stack s)
{       
    int x;

    for(int i = 1; i<=size; i++)
    {
        if(s.get(i)==i || ((s.get(i-1) - s.get(i)) == (col[i-1] - col[i])))
            return false;
    }

    return true;
}

public static void solve(int size, stack s)
{
    int[] column = new int[size];
    int x = 0;

    s.push(0);
    column[0] = 0;

    for(int i = 0; i<size; i++)
    {
        for(int j = 0; j<size;j++)
        {
            if(isSafe(column,size) == true)
            {
                s.push(i);
                column[i] = j;
            }
            else
            {
                x = s.pop();
                if(x+1<size)
                {
                    column[i] = x+1;
                    s.push(x+1);
                }
                else
                {   
                    j=0;
                    column[i] = j;
                    s.push(i+1);
                }
            }
        }
    }

    if(s.size() == size)
        printBoard(column, size);
}

The stack class, has a push, pop, size, get functions (returns int and the parameter for the push function is an int)

I only need to solve it using backtracking and stacks, no recursion.

Edit: Btw if i changed

if(s.size() == size)
  printBoard(column, size);

replaced size variable to 1, i get the board printed else i get nothing.

Edit: The problem is with the push and pop, the algorithm is not quite correct because i'm ending up with only 1 element in the stack.

Upvotes: 2

Views: 565

Answers (2)

xikkub
xikkub

Reputation: 1660

Just to clarify for anyone interested, the "N Queens" problem is reminiscent of the "8 Queens" problem in which 8 queens must be placed on a chess board such that no one queen can capture another. This can be extended to any number of queens (so long as the chess board has the appropriate dimensions). The puzzle lends itself well to recursion and is often taught in chapters on recursion. Here's a link to the puzzle.

You say that you're allowed to use a stack but not recursion. Recursion actually works by using a stack (which you never explicitly interact with). This means it's possible to write any recursive function by instead using a stack. In this situation, a stack is used to keep track of function parameters and other related variables. More specifically, when a new recursive function is called, all of the current local data in the function is pushed onto the stack. When the data needs to be retrieved after exiting a recursive call, the data at the top of the stack is popped out and then used again.

It might be easier for you to first write a recursive function to solve the problem, then figure out how to "convert" the recursive solution into an iterative one with a stack. It's also a good idea to try writing the solution iteratively, then figuring out what information needs to be kept track of for backtracking to work. I noticed that you're also using a 1D array to store the positions of the queens, but it might be useful to better visualize the puzzle by using 2D array first. This also makes your programming more straightforward.

Upvotes: 2

rhinds
rhinds

Reputation: 10043

I'm not familiar with the N Queens problem, and as the commenter mentioned, Im not sure what the problem you are facing is, but here are two quick observations:

  1. in you isSafe() method you initialise a new stack (so will be empty) and then you immediately perform checks in the if condition to determine its content - so this method will always return true - Did you mean to pass the stack you created in the main method through to this?

  2. Very minor observation, but when performing if statements on booleans you dont need the "==false" - if(!isSafe(column,size)) is enough (notice I added the ! for checking false)

Upvotes: 0

Related Questions