c - 皇后拼图 4x4

Question

我正在尝试解决在 4x4 矩阵中放置 4 个皇后的皇后问题。我知道可以用回溯算法解决。但是我还没有研究过，我正试图用我目前的知识来解决它。所以我正在尝试的是在 4x4 矩阵中生成 Queen 的所有可能组合，并只打印一个不能相互抵消的组合。

1) 为了生成所有组合，我使用了 rand 函数。

但是我上面的代码显然有错误。有些输出只有三个 '1' 而不是四个 '1' 。我无法消除这个问题。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

main()
{
    srand(time(NULL));
    int ar[30][30], i , j , a , b , c = -1, d = -1, k = 0;  

    while (1)
    {
        for (i = 0 ; i < 4 ; i++)
        {
            for (j = 0 ; j < 4 ; j++)
            {
                ar[i][j] = 0;
            }
        }

        for (i = 0 ; i < 2 ; i++)
        {
            for (j = 0 ; j < 2 ; j++)
            {
                a = rand() % 3 ;
                b = rand() % 3 ;
                if (a != c || b != d)
                {
                    ar[a][b] =  1 ; // here 1 = Queen 
                    c = a ;
                    d = b;
                }
            }
        }
    }  
}

2) 还有什么方法可以仅使用这些方法来降低时间复杂度吗？

Answer 1

与其使用临时变量来检查数组是否已填充，不如使用数组本身!

    for (i = 0 ; i < 2 ; i++)
    {
        for (j = 0 ; j < 2 ; j++)
        {
            a = rand() % 3 ;
            b = rand() % 3 ;
            if (ar[a][b] == 0)
            {
                ar[a][b] =  1 ; // here 1 = Queen 
            }
        }
    }

您的问题是内循环将执行 4 次，您只能使用变量 c 和 d 控制 1 次重复。

假设 a 为 1，b 为 1:您使 c = 1 和 d = 1 .

那么 a 是 2 而 b 是 1 ...使得 c = 2 和 d = 1 .

然后如果 a 为 1 且 b 再次为 1，则无法检查是否重复。