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

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).

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. }

**Quick links:**

C FAQ(s)
C Advance programs
C/C++ Tips & Tricks
Puzzles
JavaScript
CSS
Python
Linux Commands
PHP
Android
Articles
More...

Was this page helpful? Please share with your friends...

Are you a blogger? Join our Blogging forum.

Comments and Discussions

.rgtpcss { float: right; }
@media(min-width: 300px) { .rgtpcss { float: left; }
@media(min-width: 480px) { .rgtpcss { float: left; }
@media(min-width: 750px) { .rgtpcss { float: right; }
.resCodeAS1 { display: block; width: 320px; height: 50px; }
@media(min-width: 300px) { .resCodeAS1 { display: block; width: 300px; height: 250px; } }
@media(min-width: 480px) { .resCodeAS1 { display: block; width: 300px; height: 250px; } }
@media(min-width: 750px) { .resCodeAS1 { display: block; width: 300px; height: 250px; } }
(adsbygoogle = window.adsbygoogle || []).push({});

(adsbygoogle = window.adsbygoogle || []).push({});

(adsbygoogle = window.adsbygoogle || []).push({});

solved programs: » C » C++ » DS » Java » C# |

aptitude que. & ans.: » C » C++ » Java » DBMS |

interview que. & ans.: » C » Embedded C » Java » SEO » HR |