# Interview Questions

# 8 queens problem

- April 9, 2017
- Posted by: Kamal Rawat
- Category: Algorithms

This problem is to place 8 queens on the chess board so that they do not check each other. It can be asked in two ways:

- Find one of the possible solutions to place 8-queens, so that no queen can attack any other.
- 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; }