Write an algorithm to print all ways of arranging eight queens on a chess board so that none of them share the same row, column or diagonal.

Solution #1: This is a classic problem to implement using backtracking. We will start from the first row and move down to the last row placing a queen at each row and checking that each queen satisfies the following two conditions:

- The column number must be different from the already placed queens.
- It should not share a diagonal with already placed queens.

Here is the code,

#define BOARD_SIZE 8
int col[BOARD_SIZE]={0,};

void printQueens()
{
    int i;
    for(i=0; i < BOARD_SIZE; i++)
    {
        printf("%d\n", col[i]);
    }
    printf("\n");

}

int checkRow(int row)
{
    int i;
    for(i=0; i < row; i++)
    {
        int diff = abs(col[i] - col[row]);
        if((diff == 0) || (diff == (row-i)))
            return 0;
    }
    return 1;
}

void putQueen(int row)
{
    if(row == BOARD_SIZE)
    {
        printQueens();
        return;
    }

    int i=0;
    for(i=0; i < BOARD_SIZE; i++)
    {
        col[row] = i;
        if(checkRow(row))
            putQueen(row+1);
    }
}

void main()
{
    putQueen(0);
}