N Queens Problem

This article presents a fast way to find a solution to the famous N queens problem.

Note that we only look for one valid placement, not all of them. For N = 8 there are 92 placements; our program just finds one of those 92. If the problem itself is unfamiliar, the Wikipedia article is a good start.

N = 4#

When N = 4 there are only two placements (1 is a queen):

0100        0010
0001        1000
1000        0001
0010        0100

Our program will find one of the two. So, here we go.

The idea#

Representation. Put exactly one queen in every row and store only its column: queen[i] = j means the queen of row i stands in column j. If queen is a permutation of 1..N, no two queens share a row or a column, so the only possible conflicts are on the diagonals.

Diagonals. Number the anti-diagonals by row + column (from 2 to 2N) and the main diagonals by column - row (from 1 - N to N - 1). The arrays dn and dp count how many queens stand on each of them. The evaluation function collisions is the sum, over all diagonals, of the queens beyond the first one. A placement is a solution exactly when collisions == 0.

Moves. The only move is swapping the columns of two rows. A swap keeps queen a permutation and touches just four diagonals, so its effect on collisions is computed in constant time.

A good start. Most of the work goes into the initial placement. Row by row, we pick a random queen among the ones not placed yet and keep it only if it attacks none of the queens already placed. After at most 4N attempts we give up and place the rest at random. For large N this greedy start leaves only a handful of collisions, so the search that follows is short.

Hill climbing. We keep a list attack of the queens that are under attack. For each of them we pick a random partner and swap the two if the swap lowers collisions. Recomputing the list after every swap would be too expensive, so it is rebuilt only when collisions has dropped below half of its value at the last rebuild.

Random restart. If the climb has made about 32N attempts without reaching zero, it is stuck in a local minimum, and we start over with a new random placement.

This scheme is essentially the conflict-minimizing local search of Rok Sosič and Jun Gu (Efficient local search with conflict minimization: a case study of the n-queens problem, IEEE TKDE, 1994).

Code#

The program takes N on the command line and optionally a file to write the placement to (the column of each row, followed by a drawing of the board when N ≤ 20). It checks the result independently before reporting it.

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

// queen[i] = j 表示第 i 行的皇后在第 j 列（行列都从 1 开始编号）
// dn[k]：编号为 k = 行号 + 列号 的反对角线上有几个皇后，k ∈ [2, 2n]
// dp[k]：编号为 k = 列号 - 行号 的主对角线上有几个皇后，k ∈ [1-n, n-1]
// attack[]：所有正在被攻击的皇后的行号
static int n;
static int *queen, *dn, *dp, *attack;
static long collisions; // 评估函数：每条对角线上多出来的皇后个数之和

static uint64_t rng_state;

// 64 位线性同余随机数（Knuth MMIX 的参数），只用高 32 位
static uint32_t next_random(void)
{
    rng_state = rng_state * 6364136223846793005ULL + 1442695040888963407ULL;
    return (uint32_t)(rng_state >> 32);
}

// [0, k) 内的随机整数
static int random_below(int k)
{
    return (int)(next_random() % (uint32_t)k);
}

static void swap_int(int *p, int *q)
{
    int temp = *p;
    *p = *q;
    *q = temp;
}

// 把第 row 行的皇后从棋盘上拿走
static void remove_queen(int row)
{
    int col = queen[row];
    if (--dn[col + row] >= 1) // 这条对角线上原来就不止一个皇后
        --collisions;
    if (--dp[col - row] >= 1)
        --collisions;
}

// 把第 row 行的皇后放到第 col 列
static void place_queen(int row, int col)
{
    queen[row] = col;
    if (dn[col + row]++ >= 1) // 这条对角线上已经有皇后了
        ++collisions;
    if (dp[col - row]++ >= 1)
        ++collisions;
}

// 交换第 i 行和第 j 行的皇后，同时更新 dn、dp 和 collisions
static void swap_queens(int i, int j)
{
    int ci = queen[i], cj = queen[j];
    remove_queen(i);
    remove_queen(j);
    place_queen(i, cj);
    place_queen(j, ci);
}

static int is_attacked(int row)
{
    return dn[queen[row] + row] > 1 || dp[queen[row] - row] > 1;
}

// 重新计算 attack 数组，返回被攻击的皇后个数
static int compute_attack(void)
{
    int k = 0;
    for (int i = 1; i <= n; ++i)
        if (is_attacked(i))
            attack[++k] = i;
    return k;
}

// 生成初始棋盘
static void initialize(void)
{
    for (int k = 2; k <= 2 * n; ++k)
        dn[k] = 0;
    for (int k = 1 - n; k <= n - 1; ++k)
        dp[k] = 0;
    collisions = 0;

    for (int i = 1; i <= n; ++i)
        queen[i] = i;

    // 我们的目标是在初始化阶段生成一个很好的初态，
    // 这样初态的 collisions 已经很小，爬山的过程会大幅度缩短。
    // 做法是在初始化的时候就尽可能地避免碰撞：
    // 逐行从剩下的皇后里随机挑一个，如果放在这一行不和已经放好的皇后冲突，就采用它。
    // j 表示已经有多少个皇后被优化处理了（下一个要放的是第 j 行），
    // i 用来限制优化阶段所用的时间，超过 search_max 次尝试就强制退出。
    long search_max = 4L * n;
    int j = 1;
    for (long i = 1; i <= search_max && j <= n; ++i)
    {
        int m = j + random_below(n - j + 1); // m 为 [j, n] 之间的一个随机数
        if (dn[queen[m] + j] == 0 && dp[queen[m] - j] == 0)
        {
            swap_int(&queen[m], &queen[j]);
            place_queen(j, queen[j]);
            ++j;
        }
    }

    // 剩下的皇后随机打乱后直接放上去，同时累计 dn、dp 和 collisions
    for (int i = j; i <= n; ++i)
    {
        int m = i + random_below(n - i + 1);
        swap_int(&queen[m], &queen[i]);
        place_queen(i, queen[i]);
    }
}

// 找到一组解：初始化 + 爬山，陷入局部最优时随机重启
static void solve(void)
{
    for (;;)
    {
        initialize();
        if (collisions == 0)
            return;

        // limit 用来决定何时重新计算 attack 数组。
        // 每次交换都重新计算的话开销太大，所以设一个阈值：
        // 只有当 collisions 降到 limit 以下时才重新计算。
        long limit = collisions / 2;
        int number_of_attacks = compute_attack();

        // loopcount 用来判断何时随机重启：
        // 它比较大时，说明爬山法陷入了局部困境
        long loopcount = 0;
        while (loopcount < 32L * n)
        {
            for (int k = 1; k <= number_of_attacks; ++k)
            {
                // 取一个被攻击的皇后和一个随机的皇后，看交换它们能不能减少冲突
                int i = attack[k];
                int j = 1 + random_below(n);
                if (i == j)
                    continue;

                long before = collisions;
                swap_queens(i, j);
                if (collisions >= before)
                {
                    swap_queens(i, j); // 没有变好，换回去
                    continue;
                }

                if (collisions == 0)
                    return;
                if (collisions < limit)
                {
                    // 棋盘变动较大，重新计算 attack 数组
                    limit = collisions / 2;
                    number_of_attacks = compute_attack();
                }
            }
            loopcount += number_of_attacks;
        }
    }
}

// 独立地检查一遍答案：每列恰好一个皇后，且没有两个皇后在同一条对角线上
static int verify(void)
{
    char *col = calloc((size_t)n + 1, 1);
    char *d1 = calloc(2 * (size_t)n + 1, 1);
    char *d2 = calloc(2 * (size_t)n + 1, 1);
    int ok = col && d1 && d2;
    for (int i = 1; ok && i <= n; ++i)
    {
        int c = queen[i];
        if (c < 1 || c > n || col[c] || d1[c + i] || d2[c - i + n])
            ok = 0;
        else
            col[c] = d1[c + i] = d2[c - i + n] = 1;
    }
    free(col);
    free(d1);
    free(d2);
    return ok;
}

int main(int argc, char **argv)
{
    if (argc < 2 || (n = atoi(argv[1])) < 1 || n > 100000000)
    {
        fprintf(stderr, "usage: %s N [output-file]   (1 <= N <= 100000000)\n", argv[0]);
        return 1;
    }
    if (n == 2 || n == 3)
    {
        printf("no solution for N = %d\n", n);
        return 0;
    }

    // 下面几个数组的下标可能为负，所以先开辟空间，再让指针指向合适的位置，
    // 例如 queen[1] = pre_queen[0]，dn[2] = pre_dn[0]，dp[1-n] = pre_dp[0]
    int *pre_queen = malloc(sizeof(int) * (size_t)n);
    int *pre_dn = malloc(sizeof(int) * (2 * (size_t)n - 1));
    int *pre_dp = malloc(sizeof(int) * (2 * (size_t)n - 1));
    int *pre_attack = malloc(sizeof(int) * (size_t)n);
    if (!pre_queen || !pre_dn || !pre_dp || !pre_attack)
    {
        fprintf(stderr, "out of memory\n");
        return 1;
    }
    queen = pre_queen - 1;
    dn = pre_dn - 2;
    dp = pre_dp + (n - 1);
    attack = pre_attack - 1;

    rng_state = (uint64_t)time(NULL);

    clock_t start = clock();
    solve();
    clock_t end = clock();

    printf("N = %d: found a solution in %.3f seconds (%s)\n", n,
           (double)(end - start) / CLOCKS_PER_SEC, verify() ? "verified" : "INVALID");

    if (argc >= 3)
    {
        FILE *fp = fopen(argv[2], "w");
        if (!fp)
        {
            perror(argv[2]);
            return 1;
        }
        // 第 i 个数是第 i 行皇后所在的列；N 不超过 20 时再画出棋盘（* 为皇后）
        for (int i = 1; i <= n; ++i)
            fprintf(fp, "%d%c", queen[i], i == n ? '\n' : ' ');
        if (n <= 20)
            for (int i = 1; i <= n; ++i)
            {
                for (int j = 1; j <= n; ++j)
                    fputc(j == queen[i] ? '*' : '-', fp);
                fputc('\n', fp);
            }
        fclose(fp);
    }

    free(pre_queen);
    free(pre_dn);
    free(pre_dp);
    free(pre_attack);
    return 0;
}

Build and run:

$ cc -O2 -o nqueens nqueens.c
$ ./nqueens 8 out.txt
N = 8: found a solution in 0.000 seconds (verified)
$ cat out.txt
5 1 8 6 3 7 2 4
----*---
*-------
-------*
-----*--
--*-----
------*-
-*------
---*----
$ ./nqueens 1000000
N = 1000000: found a solution in 0.060 seconds (verified)

The placement differs between runs because the random seed comes from the clock.

---

Revised in October 2026. The original program had a few bugs, fixed above:

• It picked the random partner with ((rand() << 6) + rand()) % n + 1. On glibc, where RAND_MAX is 2³¹ − 1, the shift overflows int, which is undefined behaviour; in practice the index went negative and the program wrote outside its arrays. For large N it printed placements that were not even permutations. The program now uses its own 64-bit generator.
• The change in collisions caused by a swap was computed with a shortcut formula that is wrong when the two queens share a diagonal, so collisions could drift from the true count. A swap is now applied as “remove both queens, put them back swapped” and undone if it does not help, which is exact.
• The arrays were always allocated for 123,456,789 queens; they are now sized by N. N = 2 and N = 3, which have no solution, used to loop forever.
• Interactive prompts were replaced by command-line arguments, and the solution is verified before it is printed. Timings above were measured on an AMD Ryzen 9 9950X.