All possible solution to the n-Queen algorithm

Question

When implementing the algorithm for the whole possible solution to the n-Queen problem, I found that the same solution is achieved by many branches. Is there a good way to generate all the unique solutions to the n-Queens problem? How to avoid duplication of solutions generated by various branches (except for storage and comparison)?

Here is what I tried for the first solution: http://www.ideone.com/hDpr3

the code:

#include <stdio.h> #include <stdlib.h> #include <string.h> /* crude */ #define QUEEN 'Q' #define BLANK '.' int is_valid (char **board, int n, int a, int b) { int i, j; for (i=0; i<n; i++) { if (board[a][i] == QUEEN) return 0; if (board[i][b] == QUEEN) return 0; } for (i=a, j=b; (i>=0) && (j>=0); i--, j--) { if (board[i][j] == QUEEN) return 0; } for (i=a, j=b; (i<n) && (j<n); i++, j++) { if (board[i][j] == QUEEN) return 0; } for (i=a, j=b; (i>=0) && (j<n); i--, j++) { if (board[i][j] == QUEEN) return 0; } for (i=a, j=b; (i<n) && (j>=0); i++, j--) { if (board[i][j] == QUEEN) return 0; } return 1; } void show_board (char **board, int n) { int i, j; for (i=0; i<n; i++) { printf ("\n"); for (j=0; j<n; j++) { printf (" %c", board[i][j]); } } } int nqdfs_all (char **board, int n, int d) { int i, j, ret = 0; /* the last queen was placed on the last depth * therefore this dfs branch in the recursion * tree is a solution, return 1 */ if (d == n) { /* Print whenever we find one solution */ printf ("\n"); show_board (board, n); return 1; } /* check all position */ for (i=0; i<n; i++) { for (j=0; j<n; j++) { if (is_valid (board, n, i, j)) { board[i][j] = QUEEN; nqdfs_all (board, n, d + 1); board[i][j] = BLANK; } } } return ret; } int nqdfs_first (char **board, int n, int d) { int i, j, ret = 0; /* the last queen was placed on the last depth * therefore this dfs branch in the recursion * tree is a solution, return 1 */ if (d == n) return 1; /* check all position */ for (i=0; i<n; i++) { for (j=0; j<n; j++) { if (is_valid (board, n, i, j)) { board[i][j] = QUEEN; ret = nqdfs_first (board, n, d + 1); if (ret) { /* if the first branch is found, tell about its * success to its parent, we will not look in other * solutions in this function. */ return ret; } else { /* this was not a successful path, so replace the * queen with a blank, and prepare board for next * pass */ board[i][j] = BLANK; } } } } return ret; } int main (void) { char **board; int n, i, j, ret; printf ("\nEnter \"n\": "); scanf ("%d", &n); board = malloc (sizeof (char *) * n); for (i=0; i<n; i++) { board[i] = malloc (sizeof (char) * n); memset (board[i], BLANK, n * sizeof (char)); } nqdfs_first (board, n, 0); show_board (board, n); printf ("\n"); return 0; } 

To create the best possible solution, I used the same nqdfs_all () code function, but did not return the control to the parent element, but continued listing and validation. A call to this function displays duplicate results obtained by different branches.

Answer 1

You must use the fact that each queen must be placed in a different column. If you have already placed k kings in the first k columns, recursively put the number of kings k + 1 in column k + 1 and go through lines 1 to n (and not through all n * n cells, as you currently do). Continue with k: = k + 1 for each valid allocation. This will avoid any duplicate results, since this algorithm does not generate duplicate boards at all.

EDIT: to your question about the exclusion of symmetry: some of them can be avoided in advance, for example, by restricting Queen 1 in column 1 to rows 1, ... n/2 . If you want to completely exclude the output of symmetric solutions, you will need to store each solution found in the list and whenever you find a new solution, check whether there is one of its symmetric equivalents in the list before printing it.

To make this more efficient, you can work with the “canonical representation” of each board, defined as follows. Generate all the symmetric boards of the given one, pack each of them into an array of bytes, and among these arrays, an array that is interpreted as a large number is stored has a minimum value. This packaged view is a unique identifier for the symmetry class of each board and can easily be placed in the dictionary / hash table, which makes testing if this symmetry class has already been very effective.