Re: [algogeeks] Re: Fwd: 8 queens problem
thanks guys
On Fri, Sep 2, 2011 at 1:53 AM, Don wrote:
> 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 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Fwd: 8 queens problem
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 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Fwd: 8 queens problem
interesting because just the other day I wrote something to get all 92
solutions for 8x8 "n queens" problem in a little under 3 sec. I
also used to play chess seriously, and my coach once gave me this
exercise to find a few working configurations.
I would advise against blindly placing all queens and then checking if
"secure" -- way too many combinations to go through. Your problem
here might be that it is possible to place 7 queens, and the 8th one
might have no place to go. At this point in your algorithm, doesnt
"count" become 8 anyway, and tries to return true?
I went with the algorithm to place the rooks on the board, 8!
permutations, one on each row, and then check all diagonals. This can
be limited to even fewer iterations, but it was fast enough for me.
hope this helps,
icy`
On Sep 1, 3:30 pm, mc2 verma 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
