实现回溯 N 皇后算法
Implementing Backtracking N-Queens Algorithm
我正在用 C 实现一个算法来解决 N 皇后问题。我的代码解决了 n = 4 的问题,但不适用于 n 的任何其他值。我认为问题可能出在打印代码中,但我不确定。我试过更改 for
循环中的条件,但没有找到任何有效的方法。我还需要找到在求解时从解决方案树中修剪的节点数。我该如何解决这个问题并找到修剪后的节点数?
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
int count = 0;
void queens(int n, int row, int col[]);
int promising(int row, int col[]);
void usage(char *argv);
int main(int argc, char *argv[])
{
if (argc < 2) { usage(argv[0]); }
int n = atoi(argv[1]);
int col[n];
queens(n, 0, col);
}
void queens(int n, int row, int *col)
{
int index;
if (promising(row, col))
{
if (row == n)
{
printf("\nSolution %d\n------------\n", ++count);
for (int i = 1; i <= n; i++, putchar('\n')) // This works for n = 4.
{
for (int j = 0; j <= n - 1; j++) // This works for n = 4.
{
if (j == col[i]) { putchar('Q'); }
else { putchar('*'); }
}
}
return;
}
else
{
for (index = 0; index < n; index++)
{
col[row + 1] = index;
queens(n, row + 1, col);
}
}
}
}
int promising(int row, int *col)
{
int index;
int is_promising;
index = 0;
is_promising = 1;
while (index < row && is_promising)
{
if (col[row] == col[index] || abs(col[row] - col[index]) == row - index)
{
is_promising = 0;
}
index++;
}
return is_promising;
}
void usage(char *argv)
{
printf("usage: %s <number of queens>", argv);
exit(0);
}
您的代码存在多个问题:
您对索引范围不够系统化:您使用 0
到 n
和 1
到 n-1
,包括或排除(运算符 <=
和 <
) 混淆 reader... 并在访问 cols[n]
时调用未定义的行为。根据经验:在 C 中,有 <=
的地方就有错误。
您没有在 queens
函数中正确测试终止:您没有在枚举当前行的所有可能列之前测试终止,而是首先测试是否足够:因此,您错过了所有解决方案单元格 A1 中没有皇后。
这是更正和简化的版本:
#include <stdio.h>
#include <stdlib.h>
static int count = 0;
static int promising(int row, int *col) {
for (int i = 0; i < row; i++) {
if (col[row] == col[i] || abs(col[row] - col[i]) == row - i) {
return 0;
}
}
return 1;
}
static void queens(int n, int row, int *col) {
if (row == n) {
printf("\nSolution %d\n------------\n", ++count);
for (int i = 0; i < n; i++, putchar('\n')) {
for (int j = 0; j < n; j++) {
putchar("*Q"[j == col[i]]);
}
}
} else {
for (int i = 0; i < n; i++) {
col[row] = i;
if (promising(row, col)) {
queens(n, row + 1, col);
}
}
}
}
void usage(const char *argv) {
printf("usage: %s <number of queens>", argv);
exit(0);
}
int main(int argc, char *argv[]) {
if (argc < 2) { usage(argv[0]); }
int n = atoi(argv[1]);
int col[n];
queens(n, 0, col);
}
该算法使用蛮力,您仍然需要计算修剪节点等。
我正在用 C 实现一个算法来解决 N 皇后问题。我的代码解决了 n = 4 的问题,但不适用于 n 的任何其他值。我认为问题可能出在打印代码中,但我不确定。我试过更改 for
循环中的条件,但没有找到任何有效的方法。我还需要找到在求解时从解决方案树中修剪的节点数。我该如何解决这个问题并找到修剪后的节点数?
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
int count = 0;
void queens(int n, int row, int col[]);
int promising(int row, int col[]);
void usage(char *argv);
int main(int argc, char *argv[])
{
if (argc < 2) { usage(argv[0]); }
int n = atoi(argv[1]);
int col[n];
queens(n, 0, col);
}
void queens(int n, int row, int *col)
{
int index;
if (promising(row, col))
{
if (row == n)
{
printf("\nSolution %d\n------------\n", ++count);
for (int i = 1; i <= n; i++, putchar('\n')) // This works for n = 4.
{
for (int j = 0; j <= n - 1; j++) // This works for n = 4.
{
if (j == col[i]) { putchar('Q'); }
else { putchar('*'); }
}
}
return;
}
else
{
for (index = 0; index < n; index++)
{
col[row + 1] = index;
queens(n, row + 1, col);
}
}
}
}
int promising(int row, int *col)
{
int index;
int is_promising;
index = 0;
is_promising = 1;
while (index < row && is_promising)
{
if (col[row] == col[index] || abs(col[row] - col[index]) == row - index)
{
is_promising = 0;
}
index++;
}
return is_promising;
}
void usage(char *argv)
{
printf("usage: %s <number of queens>", argv);
exit(0);
}
您的代码存在多个问题:
您对索引范围不够系统化:您使用 0
到 n
和 1
到 n-1
,包括或排除(运算符 <=
和 <
) 混淆 reader... 并在访问 cols[n]
时调用未定义的行为。根据经验:在 C 中,有 <=
的地方就有错误。
您没有在 queens
函数中正确测试终止:您没有在枚举当前行的所有可能列之前测试终止,而是首先测试是否足够:因此,您错过了所有解决方案单元格 A1 中没有皇后。
这是更正和简化的版本:
#include <stdio.h>
#include <stdlib.h>
static int count = 0;
static int promising(int row, int *col) {
for (int i = 0; i < row; i++) {
if (col[row] == col[i] || abs(col[row] - col[i]) == row - i) {
return 0;
}
}
return 1;
}
static void queens(int n, int row, int *col) {
if (row == n) {
printf("\nSolution %d\n------------\n", ++count);
for (int i = 0; i < n; i++, putchar('\n')) {
for (int j = 0; j < n; j++) {
putchar("*Q"[j == col[i]]);
}
}
} else {
for (int i = 0; i < n; i++) {
col[row] = i;
if (promising(row, col)) {
queens(n, row + 1, col);
}
}
}
}
void usage(const char *argv) {
printf("usage: %s <number of queens>", argv);
exit(0);
}
int main(int argc, char *argv[]) {
if (argc < 2) { usage(argv[0]); }
int n = atoi(argv[1]);
int col[n];
queens(n, 0, col);
}
该算法使用蛮力,您仍然需要计算修剪节点等。