# Hackety Hacking Problem Chess puzzle

## Problem Statement

CHESS PUZZLE

My friend who is very good at chess bets me (not so good at chess ) to solve a classical puzzle of positioning eight queens on an 8*8 chessboard such that no two queens threaten each other. This means that no two queens may lie on the same row, column or diagonal.Please help me as I cannot do this on my own.

HINT : You have to write a program to print a chessboard positioning 8 queens according to the puzzle. Use backtracking technique and then check each case that does it satisfy the requirement.

```
1 * * * * * * *
* * * * 1 * * *
* * * * * * * 1
* * * * * 1 * *
* * 1 * * * * *
* * * * * * 1 *
* 1 * * * * * *
* * * 1 * * * *

```

## Curriculum Connections

This problem gives student help in understanding few thins mentioned below:

• Making use of an important tool to develop Advanced programs - Backtracking technique
• Making use of structures

## Solution

```

This program is written in C++.
Compiled using Borland 5.5 C++ compiler.

#include<stdio.h>
#include<conio.h>
#include<process.h>
/* This is the structure used to save the status of every block of chess if it is affected by the queen or not
*/
struct b
{
int p;
int hit;
};

typedef struct b node;

/* This function traverse every possible status of the chess with 8 queens on it.
And then searches for a status that satisfies the given condition.
Using nested for and if loops.
*/
void reset(node a[8][8])
{
int i , j , k , l;
for(i=0;i<8 ;i++)
for(j=0;j<8;j++)
a[i][j].hit=0;
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{
if(a[i][j].p==1)
{
for(k=0;k<8;k++)
for(l=0;l<8;l++)
{
if((i-j)==(k-l))
a[k][l].hit=1;
if((i+j)==(k+l))
a[k][l].hit=1;
if(k==i)
a[k][l].hit=1;
if(l==j)
a[k][l].hit=1;
}

}
}
};

/* This function prints the chessboard once the solution of the puzzle is found
This uses two nested for loop to print the chess board using ‘*’ for an empty position and ‘1’ for a queen.
*/
void print(node a[8][8])
{
int i, j;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
if(a[i][j].p==1)
printf("1 ");
else
printf("* ");
}
printf("\n");
}
getch();
};

void solve(node a[8][8], int count)
{
int i,j;
if(count==8)
{
print(a);
exit(0);
}
else
{
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{
if((a[i][j].p==0)&&(a[i][j].hit==0))
{
a[i][j].p=1;
reset(a);
solve(a,count+1);
a[i][j].p=0;
reset(a);
}

}
}
};
/* Small main code to call the function that is created */
int main()
{
int i, j;
clrscr();
struct b c[8][8];
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{
c[i][j].p=0;
c[i][j].hit=0;
}
solve(c,0);
return 0;
}
```