N Queen Placement Algorithm

Question

I was solving the N Queen problem where we need to place N queens on a N X N chess board such that no two queens can attack each other.

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

int size=8;
char arr[8][8];
int i,j;

void initializeBoard()
{
  for(i=0;i<size;i++)
  {
    for(j=0;j<size;j++)
    {
        arr[i][j]='.';
    }
  }
}

void printArray()
{

  for(i=0;i<size;i++)
  {

    for(j=0;j<size;j++)
    {
        printf("%c\t",arr[i][j]);
    }

    printf("\n");
  }
  printf("\n\n");
}

void placeQueen(int i,int j)
{
  arr[i][j]='Q';
}

int isAvailable(int i,int j)
{
   int m,n,flag;

   for(m=0;m<i;m++)
   {
      for(n=0;n<size;n++)
      {
        int k=abs(i-m);
        int l=abs(j-n);

        if(arr[m][j]!='Q' && arr[k][l]!='Q')
        {
            flag=1;
        }

        else
        {
            flag=0;
            break;
        }
    }
}
return flag;

}


int main(void)
{
    initializeBoard();

    for(i=0;i<size;i++)
    {
        for(j=0;j<size;j++)
        {
            if(isAvailable(i,j)==1)
            {
                // means that particular position is available
                // and so we place the queen there

                placeQueen(i,j);
                break;
            }
        }
    }

    printArray();
    return 0;
}

I think the problem is with the isAvailable() method. However, I am not able to find the bug. Please help me identify it.

Is the approach that i am taking involves backtracking ? If not, please provide the same with some explanations

Answer 1

Your code has no recursive method, which is the first thought that should pop in head while designing a backtracking algorithm. Thus, you aren't implementing any backtracking strategy here.

Your function isAvailable() is incomplete in many ways.

To check whether a cell (row,column) is under attack or not from already placed queens, you could use the following strategy.

Points to note:

1. Placing queens row by row

2. To place queen in ith row, we need to check conflict with queens placed in 0 to (i-1)th rows.

3. Queen attacks horizontally, vertically and diagonally.

Code (Reference: Tushar Roy's Lecture/Code)

boolean isSafe = true;
for(int queen = 0; queen<row; queen++) // Checking with already placed queens
{
    // attack condition
    if(position[queen].column == column || position[queen].row + 
    position[queen].column == row + column || position[queen].row - 
    position[queen].column == row-column)
    {
        isSafe = false;
        break;
    }
}

Hope this helps.

Answer 2

use a single dimensional array to keep track of the column in which queen can be placed in each row.

the conditions when the queen can be threatened can be formualted as 1) ColumnForRow[i] == ColumnForRow[j] - they will be in the same column 2) (ColumnForRow[i] - ColumnForRow[j] ) == ( i- j) or (ColumnForRow[j] - ColumnForRow[i]) == (i - j) - they will be on the same diagonal.

public class NQueenSolver {

static int BOARD_SIZE = 15;
static int count = 0;
static int columnForRow[] = new int[BOARD_SIZE];

public static void main(String[] args) {
    PlaceQueen(0);
    System.out.println(count);
}

static boolean check(int row) {
    for (int i = 0; i < row; i++) {
        int diff = Math.abs(columnForRow[i] - columnForRow[row]);
        if (diff == 0 || diff == row - i)
            return false;
    }
    return true;
}

static void PlaceQueen(int row) {
    if (row == BOARD_SIZE) {
        printBoard();
        ++count;
        return;
    }
    for (int i = 0; i < BOARD_SIZE; i++) {
        columnForRow[row] = i;
        if (check(row)) {
            PlaceQueen(row + 1);
        }
    }
}

private static void printBoard() {
    //System.out.println(Arrays.toString(columnForRow));
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            if (columnForRow[i] == j)
                System.out.print("Q ");
            else
                System.out.print("* ");
        }
        System.out.println();
    }
    System.out.println();
}

}

Answer 3

Your approach does not backtrack. It iterates over some possibilities, not all. This problems is best solved recursively, so I wouldn't do it as you are doing. You have to define the rules for a Queen being attacked by other. You do it using ifs, and recursion to apply the rule again and to iterate. Most of the backtracking algorithms are written recursively. I will give you an answer, so you can base yours on mine.

#include <stdio.h>
#include <stdlib.h>

int count = 0;
void solve(int n, int col, int *hist)
{
    int i, j;
    if (col == n) {
        printf("\nNo. %d\n-----\n", ++count);
        for (i = 0; i < n; i++, putchar('\n'))
            for (j = 0; j < n; j++)
                putchar(j == hist[i] ? 'Q' : ((i + j) & 1) ? ' ' : '.');

        return;
    }

#   define attack(i, j) (hist[j] == i || abs(hist[j] - i) == col - j)
    for (int i = 0, j = 0; i < n; i++) {
        for (j = 0; j < col && !attack(i, j); j++);
        if (j < col) continue;

        hist[col] = i;
        solve(n, col + 1, hist);
    }
}

int main(int n, char **argv)
{
    if (n <= 1 || (n = atoi(argv[1])) <= 0) n = 8;
    int hist[n];
    solve(n, 0, hist);
}

The way backtracking works in the following:

1. create a constraint (a rule) to check if the conditions are meet.
2. Consider the problem as a search tree. The time spent to search this tree is based on n, the size of the board. The best way to search is recursively, so have in mind, the smart way to solve is using recursion.
3. In that code, the first set of for loops just prints the board out, and checks if Q if found.
4. # define attack(i, j) (hist[j] == i || abs(hist[j] - i) == col - j) is my rule, which asserts 2 queens are not attacking each other.
5. The second set of for loops finds a condition which another queen can be inserted, within the constraint rules.
6. Then I call find function again. That's how the backtracking is done.
7. My base case is that 2 queens can be on the board, then I'm going recursively check if another queen can be added until 8. Thus, 2 + 1 = (1+1) + 1 = 1 (1 + 1). Applying the rule again, we have 3 + 1 = (2) + 1 + 1 = (2) + (1 + 1), and again 4 = (3) + 1 + 1 = (3) + (1+1).
8. Recursion does that for you. Let out apply the rule over and over. So f(n+1) = f(n) + 1 for that case and f(2) = 2 is my base case.
9. The base of backtracking is if one of those branches don't work out, you can go one level up and search another branch, and so on, until the tree is all searched out. Again, recursion is the way to go.

Answer 4

Having done this problem before, not all placements will allow for a valid solution to the problem.

Your solution involves always placing a queen at position (0,0) which will always be available.

You will need to either involve backtracking whenever you go through everything and can't find anything, or you will need to rely on a solution that places all queen's randomly and checking for a solution then (this method is actually much faster than you would think, but at the same time, random therefore very inefficient in the average case)

a potential pseudo solution:

while(!AllQueensPlaced){
    for(going through the array ){
        if(isAvailable())
        {
            placeQueen();
            lastQueenPlaced = some logical location of last queen;
        }
    }
    if(!AllQueensPlaced)
    {
         backtrack(lastQueenPlaced);
    }
}

Your backtrack method should mark the lastQueenPlaced as dirty and traverse through the array again looking for a new location, and then go through the while loop again. don't forget to change lastQueenPlaced in backtrack() in case that is also a lastQueenPlaced.