N queens problem
We have discussed Knight’s tour and Rat in a Maze problems in Set 1 and Set 2 respectively. Let us discuss N Queen as another example problem that can be solved using Backtracking. The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. For example, following is a solution for 4 Queen problem.
Clicking on this step you can see the Create code learningstep of the algorithm.
Everything is awesome!
void Nqueens(int x[], int n, int k){
for(x[k] = ; x[k] <= ; ++x[k]) {
if(promising_subsolution(x,k)) {
if( < ) {
Nqueens( x, n, );
}
else{
print_solution(x,n);
}
}
}
}
bool promising_subsolution (int x[], int k){
for ( int i = 1 ; i < k ; ++i ){
if((x[i] == x[k]) || ((k-i) == abs(x[k]-x[i]))){
return false;
}
}
return true;
}
You're awesome! No need for help!
1. Identify the cycle structure!
1. Listening
Listen carefully, and try to understand
the cycle structure that may exist in this algorithm!
2. Choosing structure
Now choose the cycle structure:
Congratulations! You've chosen the right structure!
May we continue, with watching the animation?
Oops! Sadly, that is not the right answer.
Would you like to listen again to the sounds?
