0

Suppose i have a 4 queens problem then i know what state space tree means but i am not able to get what does** solution space** mean?Also what is** difference between brute force and backtracking technique**s.I know that in backtracking if you don't get to a state whose bounded function is true ,we backtrack and that's how we build a solution and it requires much less states to reach to the problem.But we have to store the entire state space tree somewhere then inspite it takes less states to get to the solution what's the advantage comparing it with brute force.Is it that in both the techniques the entire state space tree is stored but the time required to find the solution is less in backtracking as it involves backtracking.

1
Contributor
1
Reply
20
Views
4 Years
Discussion Span
Last Post by inspire_all
0
Algorithm NQueens ( k, n) //Prints all Solution to the n-queens problem
{
for i := 1 to n do
{
if Place (k, i) then
{
x[k] := i;
if ( k = n) then write ( x [1 : n]
else NQueens ( k+1, n);
}
}
}
Algorithm Place (k, i)
{
for j := 1 to k-1 do
if (( x[ j ] = // in the same column
or (Abs( x [ j ] - i) =Abs ( j – k ))) // or in the same diagonal
then return false;
return true;
}

The above code is for solving 8Queens problem using backtracking.I think that it can place the first 2 queens of two rows in respective columns and then when it comes to 3rd row queen it can't be placed as no queen needs to be attacking and it will simply exit from Algorithm Nqueens...So how is this algorithm implements backtracking?

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.