COMP1721 - Higher Computing 1B

/*
 * Find a placement of queens on a chessboard such that they 
 * can't attack each other.
 *
 * written by Andrew Taylor andrewt@cse.unsw.edu.au
 * August 2001 as a COMP1721 lab exercise
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

enum {
    EMPTY = '.',
    QUEEN = 'q',
    BOARD_SIZE = 6,
    N_QUEENS = 6
};
    
void initialize_board(int chessboard[BOARD_SIZE][BOARD_SIZE]);
void place_queens(int chessboard[BOARD_SIZE][BOARD_SIZE], int nQueens);
int no_queens_attack_each_other(int chessboard[BOARD_SIZE][BOARD_SIZE]);
void print_board(int chessboard[BOARD_SIZE][BOARD_SIZE]);

/*
 * Find a placment of N_QUEENS queens on a BOARD_SIZE size chessboard
 * such that no queen attacks any other.
 *
 * This is done by generating a placement randomly and testing
 * if any two queens can attack each other and repeating this
 * until a suitable placement is found
 *
 * Much more efficient approaches exist to this problem!
 */
 
int
main(void) {
    int board[BOARD_SIZE][BOARD_SIZE];

    srand(time(NULL));
    while (1) {
        initialize_board(board);
        place_queens(board, N_QUEENS);
        if (no_queens_attack_each_other(board))
            break;
    }
    print_board(board);
    return 0;
}


/*
 * initialize the squares of the chessboard to EMPTY
 */
void
initialize_board(int chessboard[BOARD_SIZE][BOARD_SIZE]) {
    int i, j;
    
    for (i = 0; i < BOARD_SIZE; i++)
        for (j = 0; j < BOARD_SIZE; j++)
            chessboard[i][j] = EMPTY;
}

/*
 * place n_queens in random positions
 * on a chessboard.
 */
void
place_queens(int chessboard[BOARD_SIZE][BOARD_SIZE], int n_queens) {
    int i, x, y;
    i = 0;
    while (i < n_queens) {
        x = rand() % BOARD_SIZE;
        y = rand() % BOARD_SIZE;
        if (chessboard[x][y] != EMPTY)
            continue;
        chessboard[x][y] = QUEEN;   
        i++;
    }
}

/*
 * given a chessboard, return false, iff any two queens can attack
 * each other, return true otherwise
 *
 * Two queens can attack each other if they are on
 * the same row, the same column or the same diagonal
 * of the chessboard.
 */
    
int
no_queens_attack_each_other(int chessboard[BOARD_SIZE][BOARD_SIZE]) {
    int row, column, queens_count, start;
    /*
     * check rows
     * return false iff any contains multiple queens
     */
    for (row = 0; row < BOARD_SIZE; row++) {
        queens_count = 0;
        for (column = 0; column < BOARD_SIZE; column++) {
            if (chessboard[row][column] == QUEEN)
                queens_count++;
            if (queens_count > 1)
                return 0;
        }
    }
    /*
     * check columns
     * return false iff any contains multiple queens
     */
    for (column = 0; column < BOARD_SIZE; column++) {
        queens_count = 0;
        for (row = 0; row < BOARD_SIZE; row++) {
            if (chessboard[row][column] == QUEEN)
                queens_count++;
            if (queens_count > 1)
                return 0;
        }
    }
    
    /*
     * check the diagonals where row & column increase together
     * return false iff any contains multiple queens
     */
    for (start = 1 - BOARD_SIZE; start < BOARD_SIZE; start++) {
        queens_count = 0;
        for (row = 0; row < BOARD_SIZE; row++) {
            column = start + row;
            if (column < 0 || column >= BOARD_SIZE)
                continue;
            if (chessboard[row][column] == QUEEN)
                queens_count++;
        }
        if (queens_count > 1)
            return 0;
    }
    
    /*
     * check the diagonals where column increases as to descreases
     * return false iff any contains multiple queens
     */
    for (start = 0; start < 2*BOARD_SIZE; start++) {
        queens_count = 0;
        for (row = 0; row < BOARD_SIZE; row++) {
            column = start - row;
            if (column < 0 || column >= BOARD_SIZE)
                continue;
            if (chessboard[row][column] == QUEEN)
                queens_count++;
        }
        if (queens_count > 1)
            return 0;
    }
    
    return 1;
}

/*
 * print the chessboard
 */
void
print_board(int chessboard[BOARD_SIZE][BOARD_SIZE]) {
    int i, j;
    
    printf("\n\n");
    for (i = 0; i < BOARD_SIZE; i++) {
        for (j = 0; j < BOARD_SIZE; j++)
            printf("%c ", chessboard[i][j]);
        printf("\n\n");
    }
    printf("\n\n");
}

    
 /*
 * Find a placment of queens on a chessboard such that they 
 * can't attack each other.
 *
 * written by Andrew Taylor andrewt@cse.unsw.edu.au
 * August 2001 as a COMP1721 lab exercise
 */
 
#include <stdio.h>
#include <stdlib.h>

enum {
    EMPTY = '.',
    QUEEN = 'q',
};
    
int place_queens(int rows[], int columns[], int diagonals1[], int diagonals2[], int row, int board_size);
void print_board(int queens[], int board_size);

/*
 * Find a placment of N_QUEENS queens on a BOARD_SIZE size chessboard
 * such that no queen attacks any other.
 *
 * Naive backtracking with tables of rows, columns and diagonals is used.
 */
 
int
main(int argc, char *argv[]) {
    int *rows;
    int *columns;
    int *diagonals1;
    int *diagonals2;
    int board_size, i;
    
    if (argc != 2) {
        fprintf(stderr, "Usage: nqueens \n");
        return 1;
    }
    board_size = atoi(argv[1]);
    rows = (int *)malloc(board_size*sizeof (int));
    columns = (int *)malloc(board_size*sizeof (int));
    diagonals1 = (int *)malloc(2*board_size*sizeof (int));
    diagonals2 = (int *)malloc(2*board_size*sizeof (int));
    for (i = 0; i < board_size; i++) {
        rows[i] = 0;
        columns[i] = 0;
    }
    for (i = 0; i < 2*board_size; i++) {
        diagonals1[i] = 0;
        diagonals2[i] = 0;
    }
    if (rows == NULL||columns == NULL||diagonals1 == NULL||diagonals2 == NULL) {
        fprintf(stderr, "Couldn't allocate memory\n");
        return 1;
    }
    
    if (place_queens(rows, columns, diagonals1, diagonals2, 0, board_size))
        print_board(rows, board_size);
    else
        printf("No solution found!\n");
    return 0;
}


/*
 * place n_queens in random positions
 * on a chessboard.
 */
int
place_queens(int rows[], int columns[], int diagonals1[], int diagonals2[], int row, int board_size) {
    int column, d1, d2;
    if (row == board_size)
            return 1;
    for (column = 0; column < board_size; column++) {
        d1 = column + row;
        d2 = board_size + column - row;
        if (columns[column] + diagonals1[d1] + diagonals2[d2])
            continue;
        rows[row] = column;
        columns[column] = 1;
        diagonals1[d1] = 1;
        diagonals2[d2] = 1;
        if (place_queens(rows, columns, diagonals1, diagonals2, row + 1, board_size))
            return 1;
        /*
         * backtracking
         */
        columns[column] = 0;
        diagonals1[d1] = 0;
        diagonals2[d2] = 0;
    }
    return 0;
}
/*
 * print the chessboard
 */
void
print_board(int queens[], int board_size) {
    int row;
    
    printf("\n");
    for (row = 0; row < board_size; row++) {
        int column;
        for (column = 0; column < queens[row]; column++)
            printf("%c", EMPTY);
        putchar(QUEEN);
        for (column++;column < board_size; column++)
            printf("%c", EMPTY);
        printf("\n");
    }
    printf("\n");
}