4
\$\begingroup\$

This is a code I wrote for solving the famous nqueens problem. It returns only the first solution. I would like your reviews and comments and ways to convert it to a solution which will return a set of all solutions are welcome. So, here I go:

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

int isSafe(int** matrix, long long row, long long col, long long matrixDim) {
    //check col
    for (long long i = 0; i < row; i++) {
        if (matrix[i][col] == 1) {
            return 0;
        }
    }
    //check upper left diagonal
    for (long long i = row, j = col;;) {
        i--; j--;
        if (i < 0 || j < 0) {
            break;
        }
        if (matrix[i][j] == 1) {
            return 0;
        }
    }
    //check upper right diagonal
    for (long long i = row, j = col;;) {
        i--; j++;
        if (i < 0 || j == matrixDim) {
            break;
        }
        if (matrix[i][j] == 1) {
            return 0;
        }
    }
    //check lower left diagonal
    for (long long i = row, j = col;;) {
        i++; j--;
        if (i == matrixDim || j < 0) {
            break;
        }
        if (matrix[i][j] == 1) {
            return 0;
        }
    }
    //check lower right diagonal
    for (long long i = row, j = col;;) {
        i++; j++;
        if (i == matrixDim || j == matrixDim) {
            break;
        }
        if (matrix[i][j] == 1) {
            return 0;
        }
    }
    return 1;
}

void printSqMatrix(int** matrix, long long Dim) {
    for (int i = 0; i < Dim; i++) {
        for (int j = 0; j < Dim; j++) {
            printf("%d ", matrix[i][j]);
        }
        puts("");
    }
}

int solve(int** chessBoard, long long row_index, long long boardSize) {
    if (row_index == boardSize) {
        return 1;
    }
    long long j;
    for (j = 0; j < boardSize; j++) {
        if (isSafe(chessBoard, row_index, j, boardSize)) {
            chessBoard[row_index][j] = 1;
            int retVal = solve(chessBoard, row_index + 1, boardSize);
            if (retVal == 1) {
                return 1;
            }
            else if (retVal == -1) {
                puts("Something seriously wrong with execution");
                exit(1);
            }
            chessBoard[row_index][j] = 0;
        }
    }
    if (j == boardSize) {
        return 0;
    }
    return 1;   //never reaches here (written to solve a warning saying not all codepaths return a value
}

int main(void) {
    int** board = NULL;
    long long sizeOfBoard = 0;
    printf("Enter the size of the board: ");
    scanf("%lld", &sizeOfBoard);
    board = malloc(sizeof(int*) * sizeOfBoard);
    for (long long i = 0; i < sizeOfBoard; i++) {
        board[i] = malloc(sizeof(int) * sizeOfBoard);
        for (long long k = 0; k < sizeOfBoard; k++) {   //if I don't write this loop, the 0s get printed as 3452816845....Why???
            board[i][k] = 0;
        }
    }
    solve(board, 0, sizeOfBoard);
    printSqMatrix(board, sizeOfBoard);
}
\$\endgroup\$
1

2 Answers 2

9
\$\begingroup\$
  • //if I don't write this loop, the 0s get printed as 3452816845....Why???
    

    Because malloc doesn't initialize an allocated memory. It contains garbage. You may avoid the explicit loop by using calloc.

    As a side note, prefer sizeof(variable) to sizeof(type), e.g.

    board[i] = malloc(sizeof(*board[i]) * sizeOfBoard);
    

    This way, if you ever change the type of board squares, this line wouldn't change. No double maintenance.

  • The code adds queens into the rows sequentially. There is no need to test lower diagonals: there are no queens there yet.

  • Working with the entire 2-dimensional board is an overkill. A one-dimensional array of queen files suffices. Besides, testing for placement safety becomes much simpler:

    bool is_safe(int * queens, long long row, long long col, long long dim) {
        for (long long rank = 0; rank < row; rank++) {
            if (queens[rank] == col) {
                // Another queen is at this column already
                return false;
            if ((row - rank) == abs(queens[rank] - col)) {
                // A square is under diagonal attack
                return false;
            }
        return true;
    }
    
  • A for having all the solutions, do not break the loop when retVal == 1, and

    if (row_index == boardSize) {
        do_something();
        return 1;
    }
    

    where do_something() may print the board, or save the board in a global state, or whatever suites your needs.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ @chux-ReinstateMonica Oops indeed. Thanks. \$\endgroup\$
    – vnp
    May 5, 2020 at 20:21
3
\$\begingroup\$

There is no benefit in using long long for the row, col.

For practical uses, int would be sufficient.

For pedantically large cases, use size_t. It is some unsigned integer type.

[edit] Concerning the holy wars of using size_t vs. some signed type: Code to your group's coding standard. For personal use, I model code to the C standard library which favors size_t for size concerns.


Allocating

Getting the right size is prone to failure when code use the type for sizing. Note the 2 below (from OP's code and a discussion comment)

board[i] = malloc(sizeof(int) * sizeOfBoard);
solutionSet = realloc(solutionSet, sizeof(solutionSet) + sizeof(chessBoard));

The first obliges a check: "Is int correct?" I can search around and later find int** board and conclude yes, it matches. Yet if code was below, no search needed. Consider using ptr = malloc(sizeof *ptr * n); it is easy to code right, review and maintain.

board[i] = malloc(sizeof *(board[i]) * sizeOfBoard);

With the idiom ptr = malloc(sizeof *ptr * n);, the below looks wrong. The size calculation is using the size of a pointer and not the size of of its referenced type.

solutionSet = realloc(solutionSet, sizeof(solutionSet) + sizeof(chessBoard));
//                                       ^^^^^^^^^^^^^
//                    maybe        sizeof *solutionSet
\$\endgroup\$
8
  • \$\begingroup\$ size_t in my PC is simply a typedef of unsigned long long. As a result the check <0 fails. \$\endgroup\$ May 6, 2020 at 6:57
  • 1
    \$\begingroup\$ @d4rk4ng31 Easy enough to code the check before the decrement: i--; j--; if (i < 0 || j < 0) { break; } --> if (i == 0 || j == 0) { break; } i--; j--;. Even though size_t is unsigned long long on your machine, good code adapts well to many platforms. In the cases of sizing and array indexing, size_t is the type to use. Yes size_t is some unsigned type, yet that is not difficult to account for in coding. \$\endgroup\$ May 6, 2020 at 10:24
  • \$\begingroup\$ Will you please take a look at github.com/fish-shell/fish-shell/issues/3493#issue-185297171 ? And also will you correct me if I'm wrong? I really could use some help 'bout this size_t thing :) \$\endgroup\$ May 6, 2020 at 10:30
  • 1
    \$\begingroup\$ The link is more of a rant than a thoughtful discussion yet one quote I do find some agreement: "Which means those statements are alligators waiting to bite someone in the ass if they change the code without understanding the subtleties of those statements.". If coding with an unsigned is done by someone without understanding the subtleties, there are issues. Yet the C standard library if rife with size_t usages. So size_t is fundamentally not avoidable. If coding with unsigned poses too much troubles, perhaps the coder should be using a different language? \$\endgroup\$ May 6, 2020 at 10:43
  • 1
    \$\begingroup\$ @d4rk4ng31 Usage of size_t or not steps into a holy war. You can readily find many strong opinions on it either way - and unfortunate little constructive discussion. I find it useful useful. YMMV. \$\endgroup\$ May 6, 2020 at 10:48

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.