n皇后算法的所有可能解
当为n-
Queen问题的所有可能解决方案实现算法时,我发现许多分支机构都可以达到相同的解决方案。有什么好的方法可以生成解决n皇后问题的每一个独特的解决方案?如何避免由不同分支机构(存储和比较除外)生成的重复解决方案?
这是我尝试的第一个解决方案:http :
//www.ideone.com/hDpr3
码:
#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;
}
为了生成所有可能的解决方案,我使用了相同的代码nqdfs_all
()功能,但没有将控件返回给父级,而是继续枚举和检查。对该函数的调用将显示不同分支获得的重复结果。
回答:
您应该利用每个皇后必须放在不同列中的事实。如果已经在前k列中放置了k个皇后,则将第k + 1个皇后号递归地放置在k +
1列中,并遍历第1到n行(而不是像现在那样遍历所有n * n个单元格)。为每个有效的位置继续k:= k +
1。这将避免任何重复的结果,因为该算法根本不会生成任何重复的板。
编辑:您如何避免对称性的问题:可以预先避免的一部分,例如,通过在列1到行1限制女王1,…
n/2
。如果要完全避免对称解决方案的输出,则必须将找到的每个解决方案存储在列表中,每当找到新解决方案时,在打印出来之前,请测试列表中是否已存在对称解决方案之一。
为了提高效率,您可以使用每个板的“规范代表”,定义如下。生成给定板的所有对称板,将每块对称板包装到一个字节数组中,并保留其中的数组,该数组被解释为一个大数字,具有最小值。这种打包的表示形式是每个板对称类的唯一标识符,可以轻松地放入字典/哈希表中,这使测试该对称类是否已经非常有效。
以上是 n皇后算法的所有可能解 的全部内容, 来源链接: utcz.com/qa/419825.html