how to draw state space tree for n queens problem
4 Queens Problem
4 – Queens' problem is to place 4 – queens on a 4 x 4 chessboard in such a manner that no queens attack each other by being in the same row, column, or diagonal.
We will look for the solution for n=4 on a 4 x 4 chessboard in this article.
A 4*4 Chess Board
Approach:
Here we have to place 4 queens say Q1, Q2, Q3, Q4 on the 4 x 4 chessboard such that no 2 queens attack each other.
- Let's suppose we're putting our first queen Q1 at position (1, 1) now for Q2 we can't put it in 1 row( because they will conflict ).
- So for Q2 we will have to consider row 2. In row 2 we can place it in column 3 I.e at (2, 3) but then there will be no option for placing Q3 in row 3.
- So we backtrack one step and place Q2 at (2, 4) then we find the position for placing Q3 is (3, 2) but by this, no option will be left for placing Q4.
- So for Q2 we will have to consider row 2. In row 2 we can place it in column 3 I.e at (2, 3) but then there will be no option for placing Q3 in row 3.
- Then we have to backtrack till 'Q1' and put it to (1, 2) instead of (1, 1) and then all other queens can be placed safely by moving Q2 to the position (2, 4), Q3 to (3, 1), and Q4 to (4, 3).
Hence we got our solution as (2, 4, 1, 3), this is the one possible solution for the 4-Queen Problem. For another solution, we will have to backtrack to all possible partial solutions
- The other possible solution for the 4 Queen problem is (3, 4, 1, 2)
Finding solutions through State Space Tree:
State space tree can be drawn using backtracking and by this, we will be able to find the all possible solution for the 4 queen problem and not only 4 queens by this we can find all possible solutions to N queen problem
State Space Tree of 4 Queen Problem
- The simple logic of generating the state space tree is to keep exploring all possible solutions using backtracking and stop exploring that solution where ever two queens are attacking each other.
For all the positions(columns) in the current row:
- Check for all the previous rows is there a queen or not?
- Check for all the previous diagonal columns is there a queen or not?
- If any of these conditions are true, then backtrack to the previous row and move the previous queen 1 step forward.
- Otherwise, put the current queen in the position and move to the next row.
Now Let's see the Implementation of this problem:
C++14
#include <bits/stdc++.h>
using namespace std;
int a[30], cnt;
int place( int pos)
{
int i;
for (i = 1; i < pos; i++) {
if ((a[i] == a[pos])
|| (( abs (a[i] - a[pos]) == abs (i - pos))))
return 0;
}
return 1;
}
void print_sol( int N)
{
int i, j;
cnt++;
cout << "\n\nSolution " << cnt << ":\n" ;
for (i = 1; i <= N; i++) {
for (j = 1; j <= N; j++) {
if (a[i] == j)
cout << "Q\t" ;
else
cout << "*\t" ;
}
cout << endl;
}
}
void queen( int n)
{
cnt = 0;
int k = 1;
a[k] = 0;
while (k != 0) {
a[k] = a[k] + 1;
while ((a[k] <= n) && !place(k))
a[k]++;
if (a[k] <= n) {
if (k == n)
print_sol(n);
else {
k++;
a[k] = 0;
}
}
else
k--;
}
}
int main()
{
int N = 4;
queen(N);
cout << "\nTotal solutions=" << cnt;
return 0;
}
Java
import java.io.*;
import java.util.*;
class GFG
{
static int a[] = new int [ 30 ], cnt;
static int place( int pos)
{
int i;
for (i = 1 ; i < pos; i++) {
if ((a[i] == a[pos])
|| ((Math.abs(a[i] - a[pos]) == Math.abs(i - pos))))
return 0 ;
}
return 1 ;
}
static void print_sol( int N)
{
int i, j;
cnt++;
System.out.println( "Solution #" + cnt + ":" );
for (i = 1 ; i <= N; i++) {
for (j = 1 ; j <= N; j++) {
if (a[i] == j)
System.out.print( "Q " );
else
System.out.print( "* " );
}
System.out.println( "\n" );
}
}
static void queen( int n)
{
cnt = 0 ;
int k = 1 ;
a[k] = 0 ;
while (k != 0 ) {
a[k] = a[k] + 1 ;
while ((a[k] <= n) && place(k) == 0 )
a[k]++;
if (a[k] <= n) {
if (k == n)
print_sol(n);
else {
k++;
a[k] = 0 ;
}
}
else
k--;
}
}
public static void main(String[] args)
{
int N = 4 ;
queen(N);
System.out.println( "Total solutions=" + cnt);
}
}
C#
using System;
public class GFG {
static int [] a = new int [30];
static int cnt;
static int place( int pos)
{
int i;
for (i = 1; i < pos; i++) {
if ((a[i] == a[pos])
|| ((Math.Abs(a[i] - a[pos])
== Math.Abs(i - pos))))
return 0;
}
return 1;
}
static void print_sol( int N)
{
int i, j;
cnt++;
Console.WriteLine( "Solution #" + cnt + ":" );
for (i = 1; i <= N; i++) {
for (j = 1; j <= N; j++) {
if (a[i] == j)
Console.Write( "Q " );
else
Console.Write( "* " );
}
Console.WriteLine( "\n" );
}
}
static void queen( int n)
{
cnt = 0;
int k = 1;
a[k] = 0;
while (k != 0) {
a[k] = a[k] + 1;
while ((a[k] <= n) && place(k) == 0)
a[k]++;
if (a[k] <= n) {
if (k == n)
print_sol(n);
else {
k++;
a[k] = 0;
}
}
else
k--;
}
}
static public void Main()
{
int N = 4;
queen(N);
Console.WriteLine( "Total solutions=" + cnt);
}
}
Javascript
<script>
let a = new Array(30), cnt;
function place(pos)
{
let i;
for (i = 1; i < pos; i++) {
if ((a[i] == a[pos])
|| ((Math.abs(a[i] - a[pos]) == Math.abs(i - pos))))
return 0;
}
return 1;
}
function print_sol(N)
{
let i, j;
cnt++;
document.write( "Solution #" + cnt + ":" + "<br/>" );
for (i = 1; i <= N; i++) {
for (j = 1; j <= N; j++) {
if (a[i] == j)
document.write( "Q " );
else
document.write( "* " );
}
document.write( "<br/>" );
}
}
function queen(n)
{
cnt = 0;
let k = 1;
a[k] = 0;
while (k != 0) {
a[k] = a[k] + 1;
while ((a[k] <= n) && place(k) == 0)
a[k]++;
if (a[k] <= n) {
if (k == n)
print_sol(n);
else {
k++;
a[k] = 0;
}
}
else
k--;
}
}
let N = 4;
queen(N);
document.write( "Total solutions=" + cnt + "<br/>" );
</script>
Output
Solution #1: * Q * * * * * Q Q * * * * * Q * Solution #2: * * Q * Q * * * * * * Q * Q * * Total solutions=2
Time complexity: O(N2)
Auxiliary Space: O(N)
Source: https://www.geeksforgeeks.org/4-queens-problem/
0 Response to "how to draw state space tree for n queens problem"
Post a Comment