10
\$\begingroup\$

The code below is intended to be a learning material for high school intermediate programming class, as an introduction to recursion and backtracking. I was thinking of rook placement and found it too boring. I was also thinking of unique queen placements and found it missing the point.

The code works (verified against OEIS A000170).

Pupils are comfortable with C basics.

Seeking advice on clarity, and optimization (as long as it doesn't obscure clarity). Particularly, a good replacement for nw_se and ne_sw as names for diagonals.

I know I'd better test the calloc return value and put my ifs on a separate line.

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

typedef struct {
    long size;
    bool * ranks;
    bool * nw_se;
    bool * ne_sw;
} BoardState;

BoardState * board_state_init(long size)
{
    BoardState * bs = malloc(sizeof(*bs));

    bs->size = size;
    bs->ranks = calloc(size, sizeof(bs->ranks[0]));
    bs->nw_se = calloc(2*size - 1, sizeof(bs->nw_se[0]));
    bs->ne_sw = calloc(2*size - 1, sizeof(bs->ne_sw[0]));

    return bs;
}

void board_state_delete(BoardState * bs) {
    free(bs->ranks);
    free(bs->nw_se);
    free(bs->ne_sw);
    free(bs);
};

bool board_state_square_attacked(BoardState * bs, long file, long rank)
{
    if (bs->ranks[rank]) return true;
    if (bs->nw_se[bs->size - (file - rank)]) return true;
    if (bs->ne_sw[2*bs->size - 1 - (file + rank)]) return true;
    return false;
}

void board_state_set(BoardState * bs, long file, long rank, bool occupy)
{
    bs->ranks[rank] = occupy;
    bs->nw_se[bs->size - (file - rank)] = occupy;
    bs->ne_sw[2*bs->size - 1 - (file + rank)] = occupy;
}

long place_queens(BoardState * bs, long file)
{
    long placements = 0;
    if (file == bs->size) return 1;

    for (long rank = 0; rank < bs->size; ++rank) {
        if (board_state_square_attacked(bs, file,  rank)) continue;

        board_state_set(bs, file, rank, true);
        placements += place_queens(bs, file + 1);
        board_state_set(bs, file, rank, false);
    }
    return placements;
}

int main(int argc, char ** argv)
{
    long max_board_size = (argv[1] == 0)? 9: strtol(argv[1], 0, 0);

    for (long board_size = 1; board_size < max_board_size; ++board_size) {
        BoardState * bs = board_state_init(board_size);
        long placements = place_queens(bs, 0);
        board_state_delete(bs);
        printf("%ld: %ld\n", board_size, placements);
    }

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ I get this output: 1: 1 2: 0 3: 0 4: 2 5: 10 6: 4 7: 40 8: 92 which seems wrong to me. (0 queens for 2x2 board?) \$\endgroup\$ – Emanuele Paolini Aug 17 '14 at 14:05
  • \$\begingroup\$ It is correct: there are 0 ways to place 2 queens on a 2x2 board. \$\endgroup\$ – vnp Aug 17 '14 at 15:26
  • \$\begingroup\$ long max_board_size = (argv[1] == 0)? 9: strtol(argv[1], 0, 0); will lead to undefined behaviour if there are no arguments. You should always test argc before, especially at learning materials. \$\endgroup\$ – mch Aug 18 '14 at 12:30
5
\$\begingroup\$

I think it's pretty good. However since it's teaching I would stick to C89 so that student's aren't surprised when they try to use Visual Studio on their own machines. This means no declaration inside for-statements and no bool-header file.

There's always opinions about indentation and formatting. I would prefer that you've spaces between operators and that if-bodies are on their own line.

I would also like the three if statements after each other to become one. It's easier to read since the body of the if statement are the same for all three if statements.

I don't see why you're using long instead of int. Is there any reason? From what I can see, an int should be enough here.

The nw_se was I first going to rename a1_h8 to be familiar with chessboard navigation, since all squares have a name, but you seldom talk about direction. However this idea falls since you can have bigger or smaller chessboards. Hence I do think that your naming is good enough, if not the best possible there is.

I also changed the check for boardsize from < to <=. If I give 2 as an input I would want to see the result from board sized 1 and 2, not just 1 as in your example. This also lets the default value to be 8 instead of 9 which make more sense, since "everybody" knows that there's 8 rows on a Chess board.

A bit curious: why are you using _ for variables and camelCase for types?

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

typedef struct {
    int size;
    short * ranks;
    short * nw_se;
    short * ne_sw;
} BoardState;

BoardState * board_state_init(int size)
{
    BoardState * bs = malloc(sizeof(*bs));

    bs->size = size;
    bs->ranks = calloc(size, sizeof(bs->ranks[0]));
    bs->nw_se = calloc(2 * size - 1, sizeof(bs->nw_se[0]));
    bs->ne_sw = calloc(2 * size - 1, sizeof(bs->ne_sw[0]));

    return bs;
}

void board_state_delete(BoardState * bs) {
    free(bs->ranks);
    free(bs->nw_se);
    free(bs->ne_sw);
    free(bs);
};

short board_state_square_attacked(BoardState * bs, int file, int rank)
{
    if (bs->ranks[rank] ||
        bs->nw_se[bs->size - (file - rank)] ||
        bs->ne_sw[2 * bs->size - 1 - (file + rank)])
            return 1;

    return 0;
}

void board_state_set(BoardState * bs, int file, int rank, short occupy)
{
    bs->ranks[rank] = occupy;
    bs->nw_se[bs->size - (file - rank)] = occupy;
    bs->ne_sw[2 * bs->size - 1 - (file + rank)] = occupy;
}

int place_queens(BoardState * bs, int file)
{
    int placements = 0;
    int rank;

    if (file == bs->size)
            return 1;

    for (rank = 0; rank < bs->size; rank++) {
        if (board_state_square_attacked(bs, file,  rank))
                continue;

        board_state_set(bs, file, rank, 1);
        placements += place_queens(bs, file + 1);
        board_state_set(bs, file, rank, 0);
    }
    return placements;
}

int main(int argc, char ** argv)
{
    int max_board_size = (argv[1] == 0) ? 8 : strtol(argv[1], 0, 0);
    int board_size;

    for (board_size = 1; board_size <= max_board_size; board_size++) {
        BoardState * bs = board_state_init(board_size);
        int placements = place_queens(bs, 0);
        board_state_delete(bs);
        printf("%ld: %ld\n", board_size, placements);
    }

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ if (x) return 1; return 0; would't be better written as return x? \$\endgroup\$ – Emanuele Paolini Aug 17 '14 at 13:49
  • 5
    \$\begingroup\$ "I would stick to C89" - NO! There is no good reason for not using the nice things C99 or C11 gives you, besides being able to use the crappy Visual Studio C compiler (which does support some C99 features anyways). \$\endgroup\$ – syb0rg Aug 17 '14 at 15:37
  • 3
    \$\begingroup\$ It has been 15 years since C99, and 25 years since C89! \$\endgroup\$ – 200_success Aug 17 '14 at 16:14
  • \$\begingroup\$ @EmanuelePaolini not sure it's easier to understand, but it's definitely better. I missed it. \$\endgroup\$ – iveqy Aug 17 '14 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.