Data Structures 14 - N-Queens Problem

Code

#include <stdio.h>
#include <malloc.h>
#include <math.h>
#include <stdbool.h>
#include <stdlib.h>

// Check if the queen in row paraT can be placed at column paraSolution[paraT]
bool place(int* paraSolution, int paraT){
	int j;
    for (j = 1; j < paraT; j ++){
        // Check if they are in the same column or on the same diagonal
        if ((abs(paraT - j) == abs(paraSolution[j] - paraSolution[paraT])) || (paraSolution[j] == paraSolution[paraT]))
            return false;
    }
    return true;
}

// Solve the N-Queens problem using recursive backtracking
void backtracking(int* paraSolution, int paraN, int paraT){
	int i;
    if (paraT > paraN){
        // Found a solution, print it out
        for (i = 1; i <= paraN; i ++)
            printf("%d ", paraSolution[i]);
		printf("\r\n");
    }else{
        for (i = 1; i <= paraN; i ++){
            paraSolution[paraT] = i;
            if (place(paraSolution, paraT))
                backtracking(paraSolution, paraN, paraT + 1);
        }
    }
}

// Initialize and call the backtracking function to solve the N-Queens problem
void nQueen(int paraN){
	int i;
	int* solution = (int*)malloc((paraN + 1) * sizeof(int));
	for (i = 0; i <= paraN; i ++)
		solution[i] = 0;
 
    backtracking(solution, paraN, 1);
}
 
int main(){
	nQueen(5);  // Solve the 5-Queens problem
	return 1;
}

Code Summary

This code implements a classic solution for the N-Queens problem. The N-Queens problem is a classic backtracking problem where the goal is to place N queens on an ( N \times N ) chessboard such that no two queens can attack each other. Specifically, queens cannot share the same row, column, or diagonal.

1. Header Includes:

   • #include <stdio.h>: Standard input/output library.
   • #include <malloc.h>: Dynamic memory allocation library.
   • #include <math.h>: Mathematical functions library.
   • #include <stdbool.h>: Boolean type support.
   • #include <stdlib.h>: General utility library.

2. place Function:

   • Checks whether placing a queen at row paraT would conflict with any previously placed queen.
   • Determines conflicts by comparing whether the column difference equals the row difference (diagonal conflict) and whether the columns are identical (column conflict).

3. backtracking Function:

   • This is a recursive function that attempts to place queens on the board.
   • If paraT is greater than paraN, all queens have been successfully placed, and the solution is printed.
   • Otherwise, it tries placing a queen in each column and checks for conflicts via the place function. If no conflict exists, it continues recursively placing queens in the next row.

4. nQueen Function:

   • Responsible for initializing the solution array and calling the backtracking function to begin solving.
   • Dynamically allocates an array solution to store queen positions.

5. main Function:

   • Calls nQueen(5) to solve the 5-Queens problem.

Output

1 3 5 2 4 
1 4 2 5 3 
2 4 1 3 5 
2 5 3 1 4 
3 1 4 2 5 
3 5 2 4 1 
4 1 3 5 2 
4 2 5 3 1 
5 2 4 1 3 
5 3 1 4 2 
 
 
...Program finished with exit code 1
Press ENTER to exit console.