# N Queen's problem and solution using backtracking algorithm

In this article, we are going to learn about the **N Queen's problem and how it can be solved by using backtracking**?

Submitted by Shivangi Jain, on June 29, 2018

## N - Queen's problem

The **n – queen problem** is the generalized problem of 8-queens or 4 – queen’s problem. Here, the n – queens are placed on a n * n chess board, which means that the chessboard has n rows and n columns and the n queens are placed on thus n * n chessboard such that no two queens are placed in the same row or in the same column or in same diagonal. So that, no two queens attack each other.

Here, we suppose that the queen i is to be placed in row i. We can say that 1 queen is placed in the first row only but can have columns from 1, 2... n so that they satisfy all the explicit and implicit constraints.

All solutions to the **n – queen’s problem** can be therefore represented as n – tuples (x1, x2... xn) where xi is the column on which queen i is to be placed.

The explicit constraints using this formulation are Si = {1, 2, 3... n-1, n}, where 1 <= I <= n. Therefore, the solution space consists of nˆn n- tuples. Now, while considering the implicit constraints, that no two xi’s can be same i.e., two queens cannot be in the same row, same column, or in same diagonal. So, each xi should be different. Now by the above constraint, the solution is the permutations of the n – tuples (1, 2, 3, 4... n-1, n).

### Algorithm

For all the solutions of the **n - queen’s problem**...

1. Algorithm N Queen (k, n) 2. // Using backtracking, this procedure prints all possible placements of 3. // n- queens on the n*n chess board so that they are non-attacking. 4. { 5. For I = 1 to n do 6. { 7. If Place (k, i) then 8. { 9. X[k] = I; 10. If (k = n) then write (x[1: n ]) ; 11. Else N Queens (k+1, n); 12. } 13. } 14. }

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions