sudoku solver

sudoku.c

#include <stdio.h>
#include <string.h>

typedef char Sudoku[9][9];
typedef struct {
    Sudoku board;
    int x;
    int y;
    char i;
} Choice;

int is_valid(Sudoku board) {
    char slots[9];
    // Check every row
    for (int row = 0; row < 9; row++) {
        memset(slots, 0, sizeof(slots));
        for (int i = 0; i < 9; i++) {
            char n = board[row][i];
            if (n != 0) {
                if (slots[n - 1] != 0) {
                    return 0;
                } else {
                    slots[n - 1] = n;
                }
            }
        }
    }
    // Check every column
    for (int col = 0; col < 9; col++) {
        memset(slots, 0, sizeof(slots));
        for (int i = 0; i < 9; i++) {
            char n = board[i][col];
            if (n != 0) {
                if (slots[n - 1] != 0) {
                    return 0;
                } else {
                    slots[n - 1] = n;
                }
            }
        }
    }
    // Check every square
    // clang-format off
    size_t squares[9][9][2] = {
        {{0, 0}, {0, 1}, {0, 2},
        {1, 0}, {1, 1}, {1, 2},
        {2, 0}, {2, 1}, {2, 2},},
        {{3, 0}, {3, 1}, {3, 2},
        {4, 0}, {4, 1}, {4, 2},
        {5, 0}, {5, 1}, {5, 2},},
        {{6, 0}, {6, 1}, {6, 2},
        {7, 0}, {7, 1}, {7, 2},
        {8, 0}, {8, 1}, {8, 2},},
        {{0, 3}, {0, 4}, {0, 5},
        {1, 3}, {1, 4}, {1, 5},
        {2, 3}, {2, 4}, {2, 5},},
        {{3, 3}, {3, 4}, {3, 5},
        {4, 3}, {4, 4}, {4, 5},
        {5, 3}, {5, 4}, {5, 5},},
        {{6, 3}, {6, 4}, {6, 5},
        {7, 3}, {7, 4}, {7, 5},
        {8, 3}, {8, 4}, {8, 5},},
        {{0, 6}, {0, 7}, {0, 8},
        {1, 6}, {1, 7}, {1, 8},
        {2, 6}, {2, 7}, {2, 8},},
        {{3, 6}, {3, 7}, {3, 8},
        {4, 6}, {4, 7}, {4, 8},
        {5, 6}, {5, 7}, {5, 8},},
        {{6, 6}, {6, 7}, {6, 8},
        {7, 6}, {7, 7}, {7, 8},
        {8, 6}, {8, 7}, {8, 8},}
    };
    // clang-format on
    for (int square = 0; square < 9; square++) {
        memset(slots, 0, sizeof(slots));
        for (int slot = 0; slot < 9; slot++) {
            int x = squares[square][slot][0];
            int y = squares[square][slot][1];
            char n = board[y][x];
            if (n != 0) {
                if (slots[n - 1] != 0) {
                    return 0;
                } else {
                    slots[n - 1] = n;
                }
            }
        }
    }
    return 1;
}

void choose(Choice *choice, Sudoku board, int x, int y) {
    memcpy(choice->board, board, sizeof(Sudoku));
    choice->x = x;
    choice->y = y;
    choice->i = 1;
}

int iter(int *x, int *y) {
    *y += 1;
    if (*y >= 9) {
        *y = 0;
        *x += 1;
    }
    if (*x >= 9) {
        return 0;
    }
    return 1;
}

int main() {
    // clang-format off
    // Sudoku starting_board = {
    //         {0, 0, 0, 0, 0, 0, 0, 0, 0},
    //         {0, 0, 0, 0, 0, 0, 0, 0, 0},
    //         {0, 0, 0, 0, 0, 0, 0, 0, 0},
    //         {0, 0, 0, 0, 0, 0, 0, 0, 0},
    //         {0, 0, 0, 0, 0, 0, 0, 0, 0},
    //         {0, 0, 0, 0, 0, 0, 0, 0, 0},
    //         {0, 0, 0, 0, 0, 0, 0, 0, 0},
    //         {0, 0, 0, 0, 0, 0, 0, 0, 0},
    //         {0, 0, 0, 0, 0, 0, 0, 0, 0},
    // };
    Sudoku starting_board = {
        {0, 0, 0, 0, 0, 0, 0, 5, 3},
        {0, 0, 2, 7, 0, 9, 0, 4, 0},
        {0, 0, 7, 8, 0, 0, 0, 0, 0},
        {0, 3, 0, 0, 0, 0, 0, 0, 6},
        {0, 0, 0, 9, 0, 1, 0, 0, 0},
        {0, 8, 9, 0, 0, 2, 0, 0, 7},
        {4, 0, 0, 0, 0, 0, 2, 0, 0},
        {1, 0, 0, 0, 6, 0, 9, 0, 0},
        {8, 0, 0, 0, 4, 0, 0, 0, 0},
    };
    // clang-format on

    Sudoku board;
    memcpy(&board, &starting_board, sizeof(Sudoku));

    Choice choices[9 * 9];
    int p = 0;
    int x = 0;
    int y = 0;
    for (;;) {
        if (is_valid(board)) {
            // Make a new choice.
            if (board[y][x] == 0) {
                choose(&choices[p++], board, x, y);
                board[y][x] = 1;
            }
        } else {
            // backtrack and make a different choice
            Choice *choice = NULL;
            for (;;) {
                if (p == 0) {
                    printf("Error: no more choices to backtrack!");
                    return 1;
                }
                choice = &choices[p - 1];
                if (choice->i < 9) {
                    memcpy(&board, choice->board, sizeof(Sudoku));
                    x = choice->x;
                    y = choice->y;
                    choice->i++;
                    board[y][x] = choice->i;
                    break;
                } else {
                    --p;
                }
            }
        }
        if (!iter(&x, &y)) {
            break;
        }
    }

    for (int yi = 0; yi < 9; yi++) {
        for (int xi = 0; xi < 9; xi++) {
            printf("%i  ", board[yi][xi]);
        }
        printf("\n");
    }

    return 0;
}