patterncMinor

Find all distinct 8x8 chessboards where 5 queens attack/occupy every square

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

distinctqueensallsquarewherechessboardsoccupyattackeveryfind

Problem

Average time (without printBoard()) on Intel(R) Celeron(R) CPU N2840 of 100 runs:

GCC 5.4.0 with -O3: 0.48885504s

Clang 3.8.0 with -O3: 0.52578794s

My ideas for further optimization were board reflection and rotation, but I don't know how to implement them.

// Finds all distinct 8x8 chessboards where 5 queens attack/occupy every square

#include 
#include 
#include 

#define ARRAY_LEN(arr) (sizeof(arr) / sizeof(arr[0]))

const uint64_t COVERED_BOARD = 0xFFFFFFFFFFFFFFFF;

static uint64_t mkBoard(int_fast8_t a, int_fast8_t b, int_fast8_t c,
                        int_fast8_t d, int_fast8_t e);
static uint64_t coverQueens(uint64_t board);
static uint64_t coverRows(uint64_t board);
static uint64_t coverCols(uint64_t board);
static uint64_t coverDiagonals(uint64_t board);
static void printBoard(uint64_t board);
static int_fast8_t getBit(uint64_t n, int_fast8_t i);

int main(void)
{
    clock_t start = clock();

    int boardCount = 0;
    for (int_fast8_t a = 0; a = 0; --y)
    {
        for (int x = 0; x  0;
}

Advice on making code nicer and more readable is also welcome :)

New, shorter and faster version capable of calculating position count with any number of Queens:

```
#include
#include

#define COVERED_BOARD ((uint64_t) 0xFFFFFFFFFFFFFFFF)
#define QUEEN_COUNT ((int_fast8_t) 5)

static void initializeQCoverageTable(uint64_t *qCoverageTable);
static uint64_t setBit(uint64_t n, int_fast8_t x, int_fast8_t y);
static uint64_t countPositions(int_fast8_t qIndex, int_fast8_t qCount,
int_fast8_t qs,const uint64_t qCoverageTable);
static uint64_t mkBoard(int_fast8_t qCount, const int_fast8_t *qs,
const uint64_t *qCoverageTable);

int main(void)
{
uint64_t qCoverageTable[64], positionCount;
int_fast8_t qs[65] = { -1 }; // the rest are filled with zeroes

initializeQCoverageTable(qCoverageTable);
positionCount = countPositions(1, QUEEN_COUNT, qs, qCoverageTable);
printf("%" PR

Solution

Back of the envelope calculations

Your code currently runs through \$64 \choose 5\$ combinations of queen placements (which is 7.6 million combinations). For each queen placement, it checks rows (8), columns (8), and diagonals (26), for a total of 42 checks per placement or around 319 million total checks.

On the whole, this isn't bad, because your algorithm is \$O(1)\$ per queen placement and \$O(n)\$ where \$n\$ is the number of possible queen placements.

Faster algorithm

You could do better by precomputing the coverage of a queen for each of the 64 squares. That is, for a given square, you would create a 64-bit value which contained a 1 bit for each square a queen could reach from that square. Then, for each set of five queens, you would need to just OR together five 64-bit values and check whether that result was all 1 bits, similar to your current final check. Even better, the inner loop would only need to OR in one value. So overall, your program would only need to do around 7.6 million checks for a 42x speedup.

Sample rewrite

Here is a sample rewrite which demonstrates the above algorithm. It ran in 0.01 seconds compared to 0.72 seconds for the original program:

// Finds all distinct 8x8 chessboards where 5 queens attack/occupy every square

#include 
#include 
#include 

const uint64_t COVERED_BOARD = 0xFFFFFFFFFFFFFFFF;

static uint64_t attack[64];

static void initAttack(void);

int main(void)
{
    clock_t start = clock();
    int boardCount = 0;

    initAttack();
    for (int a = 0; a = 0 && row1 = 0 && row2 < 8)
                attacked |= (1ull << (row2 * 8 + attkCol));
        }
        attack[queen] = attacked;
    }
}

Code Snippets

// Finds all distinct 8x8 chessboards where 5 queens attack/occupy every square

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

const uint64_t COVERED_BOARD = 0xFFFFFFFFFFFFFFFF;

static uint64_t attack[64];

static void initAttack(void);

int main(void)
{
    clock_t start = clock();
    int boardCount = 0;

    initAttack();
    for (int a = 0; a < 64; ++a)
    {
        for (int b = a + 1; b < 64; ++b)
        {
            for (int c = b + 1; c < 64; ++c)
            {
                for (int d = c + 1; d < 64; ++d)
                {
                    uint64_t board = attack[a] | attack[b] |
                                     attack[c] | attack[d];
                    for (int e = d + 1; e < 64; ++e)
                    {
                        if ((board | attack[e]) == COVERED_BOARD)
                        {
                            ++boardCount;
                        }
                    }
                }
            }
        }
    }

    printf("%d %f\n", boardCount, (double) (clock() - start) /
                (double) CLOCKS_PER_SEC);
    return 0;
}

static void initAttack(void)
{
    for (int queen = 0; queen < 64; queen++) {
        uint64_t attacked = 0;
        int row = queen / 8;
        int col = queen % 8;
        for (int i = 0; i < 8; i++) {
            // Mark all squares in the same row and column.
            int attackedRow = row * 8 + i;
            int attackedCol = i   * 8 + col;

            attacked |= (1ull << attackedRow);
            attacked |= (1ull << attackedCol);
        }
        for (int attkCol = 0; attkCol < 8; attkCol++) {
            // Mark diagonals attacked, starting from column 0.
            int colDiff = attkCol - col;
            int row1 = row + colDiff;
            int row2 = row - colDiff;

            if (row1 >= 0 && row1 < 8)
                attacked |= (1ull << (row1 * 8 + attkCol));
            if (row2 >= 0 && row2 < 8)
                attacked |= (1ull << (row2 * 8 + attkCol));
        }
        attack[queen] = attacked;
    }
}

Context

StackExchange Code Review Q#159056, answer score: 4

Revisions (0)

No revisions yet.