The 8 Queens Problem

The problem you're asking about is known as the "Eight Queens Puzzle," which is a classic example of a more general case called the "N Queens Problem." In the Eight Queens Puzzle, the challenge is to place eight queens on an 8x8 chessboard so that no two queens threaten each other. This means no two queens can share the same row, column, or diagonal.

There are exactly 92 distinct solutions to the Eight Queens Puzzle. However, if solutions that are reflections or rotations of each other are considered to be essentially the same, then there are 12 unique solutions.

Have you ever tried to place eight queens on a chessboard in such a way that none of them can attack each other? If you have, how long did it take you to find a solution? Did you know that there is not just one solution to this problem? Our goal is to have a computer find the number and details of these different solutions as quickly as possible. To achieve this, we utilized the pruning backtracking method, which significantly reduces solution times compared to another method called Recursive Functions.

Problem

Place N queens on an N x N chessboard so that none of them can attack each other.

Imagine trying to solve this on a 15x15 chessboard; how much effort would you put into it? And how quickly do you think a computer program written by an Olympiad student could solve it? Perhaps in as short as 1 second?

Using backtracking, our results on an Intel Pentium dual-core E2200, 1 GB RAM, 100GB HD, running Linux UBUNTU were:

 Based on our observations, the time required approximately increases sevenfold for each additional queen. Here are a few sample solutions for the 8x8 board:

C codes:

#include <stdio.h>

#define MAX 20

int A[MAX][MAX],C1[MAX*2],C2[MAX*2],SUT[MAX],V_S,s;

FILE *yaz,*oku;

void Vezir_Kaldir(int i,int j)

{

            SUT[j]=0;

            C1[i-j+(V_S-1)]=0;

            C2[i+j]=0;

            A[i][j]=0;

}

void Arttir(int i,int j)

{

            SUT[j]=1;

            C1[i-j+(V_S-1)]=1;

            C2[i+j]=1;

}

int Vezir_Koy(int i,int j)

{    

            A[i][j]=-1;

            Arttir(i,j);

}

void Yap(int satir)

{

            if(satir==V_S)

            {

                        s++; return;

            }

            int i;

            for(i=0;i<V_S;i++)

                        if(!SUT[i] && !C1[satir-i+(V_S-1)] && !C2[i+satir])

                        {

                                   Vezir_Koy(satir,i);

                                   Yap(satir+1);

                                   Vezir_Kaldir(satir,i);

                        }

}

int main()

{

            oku=fopen("Queen.in","r");

            fscanf(oku,"%d ",&V_S);

            yaz=fopen("Queen.out","w");

            Yap(0);

            fprintf(yaz,"%d",s);

}