Coders Packet

N-Queen problem using C++

By Lokesh Madhav S

N-Queen problem is an important problem that uses recursion and backtracking. It inputs the board size and gives the output where the queen can be placed in a 2d array.

The N-Queen solution discussed here uses the class solution to solve the problem. The solution class contains methods such as NQ_main - To perform recursion and backtracking also by satisfying the base condition it updates 2d vector(V) with board value in column format.  The method is_valid checks if the current position is valid with respect to all the previous placements.

Finally vector<vector> v will store all the combinations of vector<vector> board in a column-wise manner. The print_help function outside the class gets the solution (v) and changes the 2d array into 'Q' and '-' to specify the valid placement and empty placement respectively.

For eg for input: 4

vector<vector> v, will become [2 4 1 3 ] [3 1 4 2 ] , where [2 3 1 3 ] is combination 1 and [3 1 4 2 ] is combination 2.

Then print_help will decode the combinations as shown below.


Download Complete Code


No comments yet