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

Question

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 <stdint.h>
#include <stdio.h>
#include <time.h>

#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 < 64; ++a)
    {
        for (int_fast8_t b = a + 1; b < 64; ++b)
        {
            for (int_fast8_t c = b + 1; c < 64; ++c)
            {
                for (int_fast8_t d = c + 1; d < 64; ++d)
                {
                    for (int_fast8_t e = d + 1; e < 64; ++e)
                    {
                        uint64_t board = mkBoard(a, b, c, d, e);
                        if (coverQueens(board) == COVERED_BOARD)
                        {
                            //printBoard(board);
                            ++boardCount;
                        }
                    }
                }
            }
        }
    }

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

static uint64_t mkBoard(int_fast8_t a, int_fast8_t b, int_fast8_t c,
                        int_fast8_t d, int_fast8_t e)
{
    uint64_t board = 0;
    board |= (uint64_t) 1 << (uint64_t) a;
    board |= (uint64_t) 1 << (uint64_t) b;
    board |= (uint64_t) 1 << (uint64_t) c;
    board |= (uint64_t) 1 << (uint64_t) d;
    board |= (uint64_t) 1 << (uint64_t) e;
    return board;
}

static uint64_t coverQueens(uint64_t board)
{
    uint64_t coveredBoard = 0;
    coveredBoard |= coverRows(board);
    coveredBoard |= coverCols(board);
    coveredBoard |= coverDiagonals(board);
    return coveredBoard;
}

static void printBoard(uint64_t board)
{
    for (int y = 7; y >= 0; --y)
    {
        for (int x = 0; x < 8; ++x)
        {
            uint64_t i = (7 - y) * 8 + x;
            int bit = getBit(board, i);
            printf("%d ", bit);
        }
        puts("");
    }
    puts("");
}

uint64_t coverRows(uint64_t oldBoard)
{
    uint64_t newBoard = 0;
    static const uint64_t rows[8] =
    {
        0xFF00000000000000,
        0x00FF000000000000,
        0x0000FF0000000000,
        0x000000FF00000000,
        0x00000000FF000000,
        0x0000000000FF0000,
        0x000000000000FF00,
        0x00000000000000FF,
    };
    for (uint_fast8_t i = 0; i < ARRAY_LEN(rows); ++i)
    {
        if (oldBoard & rows[i]) newBoard |= rows[i];
    }
    return newBoard;
}

uint64_t coverCols(uint64_t oldBoard)
{
    uint64_t newBoard = 0;
    static const uint64_t cols[8] =
    {
        0x8080808080808080,
        0x4040404040404040,
        0x2020202020202020,
        0x1010101010101010,
        0x0808080808080808,
        0x0404040404040404,
        0x0202020202020202,
        0x0101010101010101
    };
    for (uint_fast8_t i = 0; i < ARRAY_LEN(cols); ++i)
    {
        if (oldBoard & cols[i]) newBoard |= cols[i];
    }
    return newBoard;
}

static uint64_t coverDiagonals(uint64_t oldBoard)
{
    uint64_t newBoard = 0;
    // diagonals from top right corner to bottom left corner
    static const uint64_t diags1[13] =
    {
        0x0201000000000000,
        0x0402010000000000,
        0x0804020100000000,
        0x1008040201000000,
        0x2010080402010000,
        0x4020100804020100,
        0x8040201008040201,
        0x0080402010080402,
        0x0000804020100804,
        0x0000008040201008,
        0x0000000080402010,
        0x0000000000804020,
        0x0000000000008040
    };
    // diagonals from top left corner to bottom right corner
    static const uint64_t diags2[13] =
    {
        0x4080000000000000,
        0x2040800000000000,
        0x1020408000000000,
        0x0810204080000000,
        0x0408102040800000,
        0x0204081020408000,
        0x0102040810204080,
        0x0001020408102040,
        0x0000010204081020,
        0x0000000102040810,
        0x0000000001020408,
        0x0000000000010204,
        0x0000000000000102
    };
    for (uint_fast8_t i = 0; i < ARRAY_LEN(diags1); ++i)
    {
        if (oldBoard & diags1[i]) newBoard |= diags1[i];
    }
    for (uint_fast8_t i = 0; i < ARRAY_LEN(diags2); ++i)
    {
        if (oldBoard & diags2[i]) newBoard |= diags2[i];
    }
    return newBoard;
}

static int_fast8_t getBit(uint64_t n, int_fast8_t i)
{
    uint64_t mask = (uint64_t) 1 << (uint64_t) i;
    return (n & mask) > 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 <inttypes.h>
#include <stdio.h>

#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("%" PRIu64 "\n", positionCount);

    return 0;
}

static void initializeQCoverageTable(uint64_t *qCoverageTable)
{
    for (int_fast8_t q = 0; q < 64; ++q)
    {
        uint_fast64_t coverage = 0;
        int_fast8_t x = q % 8;
        int_fast8_t y = q / 8;
        for (int_fast8_t i = 0; i < 8; ++i)
        {
            coverage = setBit(coverage, x, i); // Rows
            coverage = setBit(coverage, i, y); // Columns
        }
        for (int_fast8_t i = -7; i <= 7; ++i)
        {
            coverage = setBit(coverage, x+i, y+i); // Bottom left > top right
            coverage = setBit(coverage, x-i, y+i); // Bottom right > top left
        }
        qCoverageTable[q] = coverage;
    }
}

static uint64_t setBit(uint64_t n, int_fast8_t x, int_fast8_t y)
{
    if (x < 0 || x > 7 || y < 0 || y > 7) return n;
    else return n | ((uint64_t) 1 << (uint64_t) (y * 8 + x));
}


static uint64_t countPositions(int_fast8_t qIndex, int_fast8_t qCount,
                               int_fast8_t *qs, const uint64_t *qCoverageTable)
{
    uint64_t n = 0;
    for (int_fast8_t i = qs[qIndex - 1] + 1; i < 64; ++i)
    {
        qs[qIndex] = i;
        if (qIndex<qCount)n+=countPositions(qIndex+1,qCount,qs,qCoverageTable);
        else if (mkBoard(qCount, qs, qCoverageTable) == COVERED_BOARD) ++n;
    }
    return n;
}

static uint64_t mkBoard(int_fast8_t qCount, const int_fast8_t *qs,
                        const uint64_t *qCoverageTable)
{
    uint64_t board = 0;
    for (int_fast8_t q = 1; q <= qCount; ++q) board |= qCoverageTable[qs[q]];
    return board;
}

• GCC 5.4.0 with -O3: 0.12088s
• Clang 3.8.0 with -O3: 0.0808s - 6.5X faster

Keep in mind, this version is much more generalized than the first one.

Answer 1

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 <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;
    }
}