Thread: 8 Queens, problem with searching 2D array

Originally Posted by vart

bool isPathViable(int row, int column)

is called AFTER the Queen is placed in the (row,column)

if(board[row][i]==1) for i == column will be ALWAYS true

so

Code:

void solve(int n,int row, int column)
{
    if(isPathViable(row,column))
   {
        addQueen(row,column);
        if(column == 8)
            displayBoard();
        else
            for(int i=0; i < n; ++i)
                solve(n,i,column+1);
        removeQueen(row,column);
   }
}

so,ething like that maybe?

I seem to get the same results with this, as I do with my code, just a blank board. Perhaps it is the loop in the main function that is messing me up?

EDIT- I've changed the loop in main, and I get queens that are placed, but they are kind of random, and don't follow the rules.

I've fixed it up a lot more. I got it to place the first queen in the top-left corner, then place the second queen in a way that it is safe from the first. However, after this, it doesn't go on to the other columns.

Main:

Code:

int main()
{
	int n=8;

	resetBoard();
	
        for(int i=0;i < 8;i++)
		solve(8,0,i);

        displayBoard();

        return 0;
}

Solve:

Code:

void solve(int n,int row, int column)
{
	if(isPathSuccess(row,column))
		displayBoard();
	
	else if(isPathViable(row,column))
	{
		addQueen(row,column);
		
		cout << "[" << row << "," << column << "]" << endl;
		
		for(int i=0; i < n; ++i)
			solve(n,i,column+1);
	}
	
	else
		removeQueen(row,column);	
	
}

why do you remove the Queen from the cell where you have not placed it?

Originally Posted by vart

why do you remove the Queen from the cell where you have not placed it?

I'm not sure that's the part I need help with. How would I remove the Queen that I placed, but that is in a threatening position?

I'm not really sure where to place the removeQueens function, and what to pass it, I've tried putting it everywhere it seems.

Code:

#include <iostream>

using namespace std;


void displayBoard(int size);
void addQueen(int row, int column);
void removeQueen(int row,int column);
void solve(int size, int column, int row);

bool isPathViable(int row, int column);

const int size = 8;
int board[size][size] = {0};


int main()
{
	for(int i=0;i < size;i++)
		solve(size,i,0);

	return 0;
}

void solve(int size,int row, int column)
{

	if(isPathViable(row,column))
	{
		addQueen(row,column);

		if(column == size - 1)
		{
			displayBoard(size);
		}
		else
		{
			for(int i=0; i < size; ++i)
			{
				if(i != row)
					solve(size,i,column+1);
			}
		}
		removeQueen(row,column);	
	}
	return ;
}

bool isPathViable(int row, int column)
{
	for(int i=column-1;i >= 0; --i)	//Checks row
	{
		if(board[row][i]==1)
			return false;

	}

	for(int j=row-1, k=column-1 ; j >= 0, k >= 0;--j, --k)	//Checks left and up diagonal
	{
		if(board[j][k]==1)
			return false;

	}

	for(int u=row+1, h=column-1 ;u >= 0,h >= 0;++u,--h)	//Checks left and down diagonal 
	{
		if(board[u][h]==1)
			return false;
	}

	return true;

}

void displayBoard(int size)
{
	for(int i=0; i < size; ++i)
	{
		for(int j=0; j < size; ++j)
			cout << board[i][j] << " ";

		cout << "\n";
	}
	cout << "\n";
	cout << "\n";
}

void addQueen(int row,int column)
{
	board[row][column]=1;
}

void removeQueen(int row,int column)
{
	board[row][column]=0;
}

find n differencies...

Thanks! It seems so simple, but I see what I messed up. I've been going crazy trying to figure this out!