There are several issues.
There is nothing to back out a move if it fails. After the recursive
call to queen, you need an "else" which unmarks the board. That will
be hard to do, because there isn't a good way to remember what was
marked before.
I don't think you need to loop i from p to 7. The parameter p should
indicate the row where you will place the queen. Each row gets one
queen, so just select a column on that row.
Count is incremented every time that you try a location, so all the
rejected positions will still be in the position array.
Your function never returns false.
Below is working code.
Don
// Solve 8 queens problem. queens[i] will contain the column of the
queen in row i.
bool placeQueens(int row, int *queens)
{
if (row == 8) return true;
// Look for locations to place queen on current row
for(queens[row] = 0; queens[row] < 8; ++queens[row])
{
// Determine if previously placed queens are attacking that
location
for(int i = 0; i < row; ++i)
if ((queens[row] == queens[i]) ||
(queens[row] == (queens[i]-row+i)) ||
(queens[row] == (queens[i]+row-i)))
break;
// Try to fill remaining rows
if ((i == row) && placeQueens(row+1, queens)) return true;
}
// No solution found. Backtrack and try something else.
return false;
}
On Sep 1, 2:30 pm, mc2 verma <[email protected]> wrote:
> hey guys ,
>
> I am trying to solve 8-queens problem using backtracking. Here is my algo.
> Could someone please tell me what is wrong in this code??
>
> bool queen(int p,int count , int position[][])
> {
> if(count == 8) return true;
>
> for(int i=p,i<8;i++)
> for(int j=0;j<8;j++)
> if(marked(i,j) == false ) // finding secure position on board
> {
> markboard(i,j); // if found any secure position then
> mark all board positions which are in range of queen.
> position[count][count]={i,j}; //save position for final answer
> count++;
> if(queen(p+1,count,position[][]) == true)
> return true;
> }
>
> }
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
