N-Queens Problem

The problem is to place 8 queens on the 8x8 chessboard so that they are not in a position to attack each other.

It can be asked in two ways:

1. Find one of the possible solutions to place 8-queens, so that no queen can attack any other.
2. How many different ways are possible to place 8 queens such that no one attack the other.

One of the solutions to 8-queens is as shown below:

Consider the general case of the n-Queens Problem If n is a prime number, a solution is easily found by drawing a straight line in the (n, n) finite plane. Since no two straight lines can intersect at two points, a straight line y=ax+b where a is not equal to 1 or -1 can give a solution. Coordinates start from 0.

Solution:

Starting from leftmost column, place queens one by one in different columns. While placing a queen in a particular column, check if it clashes with already placed queens.

If you can find a row in the column that is not under attack then, place the queen there and continue with the next column. If you could not find such a row due to clashes then return false and backtrack.

Code:

#include<stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define N 8
// 0 = No Queen at this position
// 1 = Queen placed at this position
int board[N][N] = {0};
void printBoard()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            printf(" %d ", board[i][j]);
        printf("\n");
    }
}
// Check if Queen can be placed at position (row,col) on the board
// Do Not place the queen. Just check.
// Check in only the rows and col before (row,col) cell. moving in col-wise order. Don't check after it
bool isSafe(int row, int col)
{
    int i, j;
    // Row-Check
    for (i = 0; i < col; i++)
        if (board[row][i])
            return false;
    // Upper-left Diagonal
    for (i=row, j=col; i>=0 && j>=0; i--, j--)
        if (board[i][j])
            return false;
    // Lower-left Diagonal
    for (i=row, j=col; j>=0 && i<N; i++, j--)
        if (board[i][j])
            return false;
    return true;
}
// This function places the Queen in Column order.
bool placeQueensRecursive(int col) {
    // Terminating condition of Recursion.
    // All Queens are placed
    if (col >= N)
        return true;
    // Try placing the queen in all rows of current col
    for (int i = 0; i < N; i++)
    {
        if ( isSafe(i, col) )
        {
            board[i][col] = 1;
            // Place rest of the queens
            if ( placeQueensRecursive(col + 1) )
                // If able to place all other queens
                return true;
            else
                // If not able to place queens then empty that row
                // and try to place queen in other rows
                board[i][col] = 0;
        }
    }
    // If no solution possible
    return false;
}
// Wrapper Function to call the main function (that is recursive)f
bool placeQueens()
{
    if ( placeQueensRecursive(0) == false )
    {
        printf("No Solution Exist.");
        return false;
    }
    else
    {
        printf("One of the Solutions is: \n");
        printBoard();
        return true;
    }
}
// driver program to test above function
int main()
{
    placeQueens();
    return 0;
}