Tech Learning

Algorithm: n-Queens Problem (Backtracking)

📢 This article was translated by gemini-3-flash-preview

Problem Description

The n-Queens problem involves placing $n$ queens on an $n \times n$ chessboard such that no two queens attack each other. This means no two queens can be in the same row, same column, or on the same diagonal (following standard chess queen movement rules).

Problem Analysis

We can solve the n-Queens problem using the following approach:

  1. Place the $i$-th queen in the $i$-th row.
  2. Starting from the first queen, try each column in its corresponding row (the $i$-th queen corresponds to the $i$-th row) starting from the first column.
  3. If a position is valid (no attacks), place the queen and move to the next queen.
  4. If it conflicts with existing queens, try the next column.
  5. If all columns in the current row are exhausted, backtrack to the previous queen and move it to its next possible column.

Repeat this process until all possible configurations are found.

C Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <stdio.h>
#include <math.h>

#define N 4 // Number of queens

// Check if the k-th queen's current position conflicts with previous ones
int isplace(int pos[], int k){
        int i;
        for(i=1; i<k; i++){
            if(pos[i]==pos[k] || fabs(i-k) == fabs(pos[i]-pos[k]))
                return 0;
        }
        return 1;
}

int main(){
    int i,j;
    int count = 1;
    int pos[N+1];

    // Initialize positions
    for(i=1;i<=N;i++)
        pos[i]=0;
    
    j = 1;
    while(j>=1){
        pos[j]=pos[j]+1;

        // Try placing the j-th queen
        while(pos[j]<=N && !isplace(pos,j)){
            pos[j]=pos[j]+1;
        }

        // Found a valid solution
        if(pos[j]<=N && j==N){
            printf("Solution %d: ", count++);
            for(i=1;i<=N;i++)
                printf("%d", pos[i]);
            printf("\n");
        }

        // Move to the next queen
        if(pos[j]<=N && j<N){
            j+=1;
        }else{ // Backtrack to the previous queen
            pos[j]=0;
            j-=1;
        }
    }
    return 1;
}