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.

Sample Output

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;
}