C Programming 8 Queens Problem with Recursive Function

8 Queens Problem Solving with Recursion in C Programming

In the game of chess, the queen can attack any piece that lies on the same row, on the same column, or along a diagonal. The eight-queens is a classic logic puzzle. The task is to place 8 queens on a chessboard in such a fashion that no queen can attack any other queen

A fun problem that can be solved using recursion is the Eight Queens Problem. The goal is to place 8 queens on a chessboard so that none is in the same row or column or diagonal of the board. Consider a recursive function such as subsets or permutation that makes not just one recursive call, but several. The tree of function calls has multiple branches at each level, which in turn have further branches, and so on down to the base case. The Reclusive function for 8 Queens problem assume to ensure that the following conditions
1. No two queens share a column
2. No two queens share a row
3. No two queens share a / diagonal
4. No two queens share a \ diagonal

8 Queens problem Recursive Function
#include
static int t[10]={-1};
void queens(int i);
int empty(int i);

void print_solution();
int main()
{
queens(1);
print_solution();
return(0);
}

void queens(int i)
{
for(t[i]=1;t[i]<=8;t[i]++)
{
if(empty(i))
{
if(i==8)
{
print_solution();
/* If this exit is commented, it will show ALL possible combination */
exit(0);
}
else
{
// Recursion!
queens(i+1);
}
}
}
}

int empty(int i)
{
int j;
j=1;

while(t[i]!=t[j] && abs(t[i]-t[j])!=(i-j) &&j<8)j++;

return((i==j)?1:0);
}
void print_solution()
{
int i;
for(i=1;i<=8;i++)printf("\nt[%d] = [%d]",i,t[i]);
}

The Output of the above 8 Queens Problem will be
t[1] = [1] // The first square of the first row
t[2] = [5] // The fifth square of the second row
t[3] = [8] // The eight square of the third row
t[4] = [6] // The sixth square of the fourth row
t[5] = [3] // The third square of the fifth row
t[6] = [7] // The seventh square of the sixth row
t[7] = [2] // The second square of the seventh row
t[8] = [4] // The fourth square of the eighth row

The Graphical Representation for 8 Queens Problem
8 Queens Problem with Recursive Function


Related Topic 8 Queens Problem with Recursive Function in CPP
Implicit Property Declaration
Use of array_merge_recursive() function in PHP Programming
Using array_replace_recursive() function in PHP Programming
Using array_replace() function PHP Programming

nScraps.com 2011   Privacy Policy  Terms of Service  Feedback