What is N Queen Problem ?

• The idea is to place queens one by one in different columns, starting from the leftmost column.
• When we place a queen in a column, we can checkout to clashes with already placed queens.
• In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution.
• If we do not find such a row due to clashes then we backtrack and return false.

[pastacode lang=”markdown” manual=”1)%20Start%20from%20the%20leftmost%20column%0A2)%20If%20all%20queens%20are%20placed%0A%20%20%20%20return%20true%0A3)%20Try%20all%20rows%20in%20the%20current%20column.%20%20Do%20following%20for%20every%20tried%20row.%0A%20%20%20%20a)%20If%20the%20queen%20can%20be%20placed%20safely%20in%20this%20row%20then%20mark%20this%20%5Brow%2C%20%0A%20%20%20%20%20%20%20%20column%5D%20as%20part%20of%20the%20solution%20and%20recursively%20check%20if%20placing%20queen%20here%20leads%20to%20a%20solution.%0A%20%20%20%20b)%20If%20placing%20the%20queen%20in%20%5Brow%2C%20column%5D%20leads%20to%20a%20solution%20then%20return%20%0A%20%20%20%20%20%20%20%20true.%0A%20%20%20%20c)%20If%20placing%20queen%20does%20not%20lead%20to%20a%20solution%20then%20umark%20this%20%5Brow%2C%20%0A%20%20%20%20%20%20%20%20column%5D%20(Backtrack)%20and%20go%20to%20step%20(a)%20to%20try%20other%20rows.%0A4)%20If%20all%20rows%20have%20been%20tried%20and%20nothing%20worked%2C%20return%20false%20to%20trigger%20%0A%20%20%20%20backtracking.” message=”” highlight=”” provider=”manual”/]

Sample Code in C

[pastacode lang=”c” manual=”%2F*%20C%2FC%2B%2B%20program%20to%20solve%20N%20Queen%20Problem%20using%20%0Abacktracking%20*%2F%0A%23define%20N%204%20%0A%23include%3Cstdio.h%3E%20%0A%23include%3Cstdbool.h%3E%20%0A%0A%2F*%20A%20utility%20function%20to%20print%20solution%20*%2F%0Avoid%20printSolution(int%20board%5BN%5D%5BN%5D)%20%0A%7B%20%0A%09for%20(int%20i%20%3D%200%3B%20i%20%3C%20N%3B%20i%2B%2B)%20%0A%09%7B%20%0A%09%09for%20(int%20j%20%3D%200%3B%20j%20%3C%20N%3B%20j%2B%2B)%20%0A%09%09%09printf(%22%20%25d%20%22%2C%20board%5Bi%5D%5Bj%5D)%3B%20%0A%09%09printf(%22%5Cn%22)%3B%20%0A%09%7D%20%0A%7D%20%0A%0A%2F*%20A%20utility%20function%20to%20check%20if%20a%20queen%20can%20be%20placed%20on%20board%5Brow%5D%5Bcol%5D.%20%0ANote%20that%20this%20function%20is%20called%20when%20%22col%22%20queens%20are%20already%20placed%20in%20columns%0A%20from%200%20to%20col%20-1.%20So%20we%20need%20to%20check%20only%20left%20side%20for%20attacking%20queens%20*%2F%0Abool%20isSafe(int%20board%5BN%5D%5BN%5D%2C%20int%20row%2C%20int%20col)%20%0A%7B%20%0A%09int%20i%2C%20j%3B%20%0A%0A%09%2F*%20Check%20this%20row%20on%20left%20side%20*%2F%0A%09for%20(i%20%3D%200%3B%20i%20%3C%20col%3B%20i%2B%2B)%20%0A%09%09if%20(board%5Brow%5D%5Bi%5D)%20%0A%09%09%09return%20false%3B%20%0A%0A%09%2F*%20Check%20upper%20diagonal%20on%20left%20side%20*%2F%0A%09for%20(i%3Drow%2C%20j%3Dcol%3B%20i%3E%3D0%20%26%26%20j%3E%3D0%3B%20i–%2C%20j–)%20%0A%09%09if%20(board%5Bi%5D%5Bj%5D)%20%0A%09%09%09return%20false%3B%20%0A%0A%09%2F*%20Check%20lower%20diagonal%20on%20left%20side%20*%2F%0A%09for%20(i%3Drow%2C%20j%3Dcol%3B%20j%3E%3D0%20%26%26%20i%3CN%3B%20i%2B%2B%2C%20j–)%20%0A%09%09if%20(board%5Bi%5D%5Bj%5D)%20%0A%09%09%09return%20false%3B%20%0A%0A%09return%20true%3B%20%0A%7D%20%0A%0A%2F*%20A%20recursive%20utility%20function%20to%20solve%20N%20%0AQueen%20problem%20*%2F%0Abool%20solveNQUtil(int%20board%5BN%5D%5BN%5D%2C%20int%20col)%20%0A%7B%20%0A%09%2F*%20base%20case%3A%20If%20all%20queens%20are%20placed%20%0A%09then%20return%20true%20*%2F%0A%09if%20(col%20%3E%3D%20N)%20%0A%09%09return%20true%3B%20%0A%0A%09%2F*%20Consider%20this%20column%20and%20try%20placing%20%0A%09this%20queen%20in%20all%20rows%20one%20by%20one%20*%2F%0A%09for%20(int%20i%20%3D%200%3B%20i%20%3C%20N%3B%20i%2B%2B)%20%0A%09%7B%20%0A%09%09%2F*%20Check%20if%20the%20queen%20can%20be%20placed%20on%20%0A%09%09board%5Bi%5D%5Bcol%5D%20*%2F%0A%09%09if%20(%20isSafe(board%2C%20i%2C%20col)%20)%20%0A%09%09%7B%20%0A%09%09%09%2F*%20Place%20this%20queen%20in%20board%5Bi%5D%5Bcol%5D%20*%2F%0A%09%09%09board%5Bi%5D%5Bcol%5D%20%3D%201%3B%20%0A%0A%09%09%09%2F*%20recur%20to%20place%20rest%20of%20the%20queens%20*%2F%0A%09%09%09if%20(%20solveNQUtil(board%2C%20col%20%2B%201)%20)%20%0A%09%09%09%09return%20true%3B%20%0A%0A%09%09%09%2F*%20If%20placing%20queen%20in%20board%5Bi%5D%5Bcol%5D%20%0A%09%09%09doesn’t%20lead%20to%20a%20solution%2C%20then%20%0A%09%09%09remove%20queen%20from%20board%5Bi%5D%5Bcol%5D%20*%2F%0A%09%09%09board%5Bi%5D%5Bcol%5D%20%3D%200%3B%20%2F%2F%20BACKTRACK%20%0A%09%09%7D%20%0A%09%7D%20%0A%0A%09%2F*%20If%20the%20queen%20cannot%20be%20placed%20in%20any%20row%20in%20%0A%09%09this%20colum%20col%20then%20return%20false%20*%2F%0A%09return%20false%3B%20%0A%7D%20%0A%0A%2F*%20This%20function%20solves%20the%20N%20Queen%20problem%20using%20Backtracking.%20It%20mainly%20uses%20%0AsolveNQUtil()%20to%20solve%20the%20problem.%20It%20returns%20false%20if%20queens%20cannot%20be%20placed%2C%20%0Aotherwise%2C%20return%20true%20and%20prints%20placement%20of%20queens%20in%20the%20form%20of%201s.%0A%0A%20Please%20note%20that%20there%20may%20be%20more%20than%20one%20solutions%2C%20this%20function%20prints%20one%20of%20the%20%0Afeasible%20solutions.*%2F%0Abool%20solveNQ()%20%0A%7B%20%0A%09int%20board%5BN%5D%5BN%5D%20%3D%20%7B%20%7B0%2C%200%2C%200%2C%200%7D%2C%20%0A%09%09%7B0%2C%200%2C%200%2C%200%7D%2C%20%0A%09%09%7B0%2C%200%2C%200%2C%200%7D%2C%20%0A%09%09%7B0%2C%200%2C%200%2C%200%7D%20%0A%09%7D%3B%20%0A%0A%09if%20(%20solveNQUtil(board%2C%200)%20%3D%3D%20false%20)%20%0A%09%7B%20%0A%09printf(%22Solution%20does%20not%20exist%22)%3B%20%0A%09return%20false%3B%20%0A%09%7D%20%0A%0A%09printSolution(board)%3B%20%0A%09return%20true%3B%20%0A%7D%20%0A%0A%2F%2F%20driver%20program%20to%20test%20above%20function%20%0Aint%20main()%20%0A%7B%20%0A%09solveNQ()%3B%20%0A%09return%200%3B%20%0A%7D” message=”” highlight=”” provider=”manual”/]

Output

[pastacode lang=”c” manual=”0%20%200%20%201%20%200%20%0A%201%20%200%20%200%20%200%20%0A%200%20%200%20%200%20%201%20%0A%200%20%201%20%200%20%200%20″ message=”” highlight=”” provider=”manual”/]