8 Queens puzzle with recursive deep search

Question

我正在尝试解决 C 中的 8 皇后拼图问题。我在递归搜索方面遇到了问题。该程序应该从给定的列开始：

 execute(tabuleiro,8,0);

其中 8 是面板中的列数，0 是起始列。

这在我从第 0 列开始时起作用。当我将任何其他列号发送到递归搜索时，程序只计算到最后一列。例如，如果我选择从第 5 列开始搜索，代码从第 5 列搜索到第 7 列，之后它应该从 0 到 4 搜索，但它没有这样做。

如果我这样做：

execute(tabuleiro,8,3);

它只填写最后 5 列，不会 return 到第 0 列以完成解决方案：

此外，如何 select 这段代码中皇后的初始位置？正如我之前所说，该列已在代码中指定，但我不确定如何选择正确的列。

该代码有 3 个功能：一个是显示棋盘，第二个是检查移动是否合法（因此一个皇后不会攻击另一个），最后一个是放置一个皇后并重复董事会的其余部分。

#include <stdlib.h>
#include <windows.h>
int sol = 0;
void viewtab(int tab[][8], int N)
{
    int i,j;
    for( i = 0; i < N; i++)
    {
        for( j = 0; j < N; j++)
        {

            if(tab[i][j] == 1)
                printf("R\t");
            else
                printf("-\t");
        }
        printf("\n\n");
    }
    printf("\n\n");
    system("pause");
    printf("\n");
}
int secury(int tab[][8], int N, int lin, int col)
{
    // this function is to check if the move is secury
    int i, j;

    // attack in line
    for(i = 0; i < N; i++)
    {
        if(tab[lin][i] == 1)
            return 0;
    }

    //attack in colune
    for(i = 0; i < N; i++)
    {
        if(tab[i][col] == 1)
            return 0;
    }

    // attack in main diagonal
    //
    for(i = lin, j = col; i >= 0 && j >= 0; i--, j--)
    {
        if(tab[i][j] == 1)
            return 0;
    }
    for(i = lin, j = col; i < N && j < N; i++, j++)
    {
        if(tab[i][j] == 1)
            return 0;
    }

    // attack in main secondary

    for(i = lin, j = col; i >= 0 && j < N; i--, j++)
    {
        if(tab[i][j] == 1)
            return 0;
    }
    for(i = lin, j = col; i < N && j >= 0; i++, j--)
    {
        if(tab[i][j] == 1)
            return 0;
    }

    // if arrive here the move is secury and return true
    return 1;
}
void execute(int tab[][8], int N, int col)
{
    int i;
    if(col == N)
    {
        printf("Solution %d ::\n\n", sol + 1);
        viewtab(tab, N);
        sol++;
        return;
    }

    for( i = 0; i < N; i++)
    {
        // check if is secury to put the queen at that colune
        if(secury(tab, N, i, col))
        {
            // insert the queen (with 1)
            tab[i][col] = 1;

            // call recursive
            execute(tab, N, col + 1);

            // remove queen (backtracking)
            tab[i][col] = 0;
        }
    }
}
int main()
{
    int i, j, tabuleiro[8][8];
    for (i = 0; i < 8; i = i + 1)
        for (j = 0; j < 8; j = j + 1) tabuleiro[i][j] = 0;

    execute(tabuleiro,8,0);

    return 0;
}

Answer 1

一个。您可以将第一个皇后放置在 (0,0) 处。 B. 也从 (0,0) 开始搜索。 C. 我认为没有必要开始寻找其他索引。成功！！

Answer 2

搜索总是停在最右边的列，因为您明确告诉它停在那里：

void execute(int tab[][8], int N, int col)
{
    int i;
    if(col == N)
    {
        printf("Solution %d ::\n\n", sol + 1);
        viewtab(tab, N);
        sol++;
        return;
    }

查看您的终止条件：您将当前列与最高列号进行比较，然后停在那里。

如果你想回到第 0 列，你必须改变你的循环逻辑。例如，让 col 达到 N，此时您将其重置为 0，并让它继续直到达到原始值。另一种方法是继续，直到放置皇后的数量为N。

您以相同的方式选择初始点：您选择第一个并进行递归调用。如果最终得出解决方案，则将其打印出来。如果不是，您的最上面的调用将继续到板的下一行（行）并将第一个皇后放在那里。

这已经在你的主逻辑中了。只要确保 secury 将 return true 当板为空时，而不是 false 或抛出错误。

8 Queens puzzle with recursive deep search

8 Queens puzzle with recursive deep search

c

puzzle

recursion

search