Member Avatar for inspire_all

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
  • 214 Views
  • 4 Days Discussion Span
  • Latest Post Latest Post by inspire_all
Member Avatar for inspire_all 
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?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.