实现回溯法 N 皇后算法

Question

我正在使用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);
}

- user3736742

---

请注意，当col[n]，索引为0..(n-1)。 - BLUEPIXY

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - chqrlie

Answer 1

你的代码存在多个问题：

你对索引范围不够系统化：在使用0到n和1到n-1时使用了包括和不包括（运算符<=和<），这会使读者感到困惑...并在访问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);
}

该算法使用暴力方法，您仍需要计算修剪节点等内容。

- chqrlie