# How to avoid permutations in the n-Queens problem?

EDIT: if you are not familiar with the problem and the solution, it's nicely explained here.

I have solved the n-Queens problem as an exercise using backtracking (recursion), but the problem I have right now is I get multiple permutations of the same solution:

n = 4
(0,1) (1,3) (2,0) (3,2)
(0,1) (1,3) (3,2) (2,0)
(0,1) (2,0) (1,3) (3,2)
(0,1) (2,0) (3,2) (1,3)
(0,1) (3,2) (1,3) (2,0)
...


For n=4 i get a total of 48 solutions. Of course there are rotations and mirroring which are fine and should be included, but as you can see in the example above permutations of the exact same solution appear.

My program works as follows:

solve(queens){
if (n_queens_are_on_the_board){
remember_solution();
return;
}
for(x: 0 to n){
for(y: 0 to n){
if(current_position_not_attacked){
solve(board);
}
}
}
}


Obviously I can just find the permutations and remove them from the final result, but is there a faster way of getting rid of them or ideally completely avoiding them?

Any help is appreciated.

• Since the solution must have exactly one queen in each row, you should only position the next queen in the next row. Commented Apr 9, 2018 at 21:06

Note that your solution is not optimized - if you really want a speed boost, you should handle rotations / mirroring instead of looping through every possible combination. With a large board, this will be much more significant than looping through the solutions one extra time.

There are a few ways you could handle the permutations. I would handle them as a secondary check under if (n_queens_are_on_the_board), resulting in the following algorithm:

solve(queens){
if (n_queens_are_on_the_board){
if (solution_is_sorted) {
remember_solution();
}
return;
}
for(x: 0 to n){
for(y: 0 to n){
if(current_position_not_attacked){
solve(board);

All that you have to do now is define a function to tell if the solution is sorted - again, there are a few ways you could do this. The simplest is probably to define the hash of a point to be point[0] * length(points) + point[1] and discard the solution if the hash of position n + 1 is less than the hash of position n. With this algorithm, you will end up with the solution (0,1) (1,3) (2,0) (3,2) from the sample provided.