// sudoku: A solver for sudoku puzzles.
// Copyright ©2017-2024 Evan Pretti.  All rights reserved.

// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:

//     1.  Redistributions of source code must retain the above copyright
//         notice, this list of conditions and the following disclaimer.
//     2.  Redistributions in binary form must reproduce the above copyright
//         notice, this list of conditions and the following disclaimer in the
//         documentation and/or other materials provided with the distribution.

// This software is provided by the author and contributors "as is" and any
// express or implied warranties, including, but not limited to, the implied
// warranties of merchantability and fitness for a particular purpose are
// disclaimed.  In no event shall the author or contributors be liable for any
// direct, indirect, incidental, special, exemplary, or consequential damages
// (including, but not limited to, procurement of substitute goods or services;
// loss of use, data, or profits; or business interruption) however caused and
// on any theory of liability, whether in contract, strict liability, or tort
// (including negligence or otherwise) arising in any way out of the use of this
// software, even if advised of the possibility of such damage.

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

// 9x9 sudoku constants and string constants.
#define CELL_COUNT ((uint8_t)81)
#define CONSTRAINT_COUNT ((uint8_t)20)
#define DIGIT_COUNT ((uint8_t)9)
#define ROW_COUNT ((uint8_t)9)
#define COLUMN_COUNT ((uint8_t)9)
#define NAME "sudoku: "
#define BUFFER "* * * * * * * * *\n"
#define GRID_BUFFER "* * *   * * *   * * *   * * *   * * *   * * *   * * *   * * *" \
    "   * * *\n* * *   * * *   * * *   * * *   * * *   * * *   * * *   * * *   * *" \
    " *\n* * *   * * *   * * *   * * *   * * *   * * *   * * *   * * *   * * *\n"
#define ROW_LENGTH 70
#define SPACING 8
#define MAX_ITERATIONS ((uint16_t)1000)
#define MAX_RECURSIONS ((uint16_t)1000)

// Represents a sudoku grid with candidates.
typedef struct {
    uint8_t solved[CELL_COUNT];
    uint8_t candidates[CELL_COUNT][DIGIT_COUNT];
} grid_t;

// Indices of cells in grids which must be different from each cell.
static const uint8_t constraints[CELL_COUNT][CONSTRAINT_COUNT] = {
    { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 18, 19, 20, 27, 36, 45, 54, 63, 72 },
    { 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 18, 19, 20, 28, 37, 46, 55, 64, 73 },
    { 0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 18, 19, 20, 29, 38, 47, 56, 65, 74 },
    { 0, 1, 2, 4, 5, 6, 7, 8, 12, 13, 14, 21, 22, 23, 30, 39, 48, 57, 66, 75 },
    { 0, 1, 2, 3, 5, 6, 7, 8, 12, 13, 14, 21, 22, 23, 31, 40, 49, 58, 67, 76 },
    { 0, 1, 2, 3, 4, 6, 7, 8, 12, 13, 14, 21, 22, 23, 32, 41, 50, 59, 68, 77 },
    { 0, 1, 2, 3, 4, 5, 7, 8, 15, 16, 17, 24, 25, 26, 33, 42, 51, 60, 69, 78 },
    { 0, 1, 2, 3, 4, 5, 6, 8, 15, 16, 17, 24, 25, 26, 34, 43, 52, 61, 70, 79 },
    { 0, 1, 2, 3, 4, 5, 6, 7, 15, 16, 17, 24, 25, 26, 35, 44, 53, 62, 71, 80 },
    { 0, 1, 2, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 27, 36, 45, 54, 63, 72 },
    { 0, 1, 2, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 28, 37, 46, 55, 64, 73 },
    { 0, 1, 2, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 29, 38, 47, 56, 65, 74 },
    { 3, 4, 5, 9, 10, 11, 13, 14, 15, 16, 17, 21, 22, 23, 30, 39, 48, 57, 66, 75 },
    { 3, 4, 5, 9, 10, 11, 12, 14, 15, 16, 17, 21, 22, 23, 31, 40, 49, 58, 67, 76 },
    { 3, 4, 5, 9, 10, 11, 12, 13, 15, 16, 17, 21, 22, 23, 32, 41, 50, 59, 68, 77 },
    { 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 24, 25, 26, 33, 42, 51, 60, 69, 78 },
    { 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 24, 25, 26, 34, 43, 52, 61, 70, 79 },
    { 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 24, 25, 26, 35, 44, 53, 62, 71, 80 },
    { 0, 1, 2, 9, 10, 11, 19, 20, 21, 22, 23, 24, 25, 26, 27, 36, 45, 54, 63, 72 },
    { 0, 1, 2, 9, 10, 11, 18, 20, 21, 22, 23, 24, 25, 26, 28, 37, 46, 55, 64, 73 },
    { 0, 1, 2, 9, 10, 11, 18, 19, 21, 22, 23, 24, 25, 26, 29, 38, 47, 56, 65, 74 },
    { 3, 4, 5, 12, 13, 14, 18, 19, 20, 22, 23, 24, 25, 26, 30, 39, 48, 57, 66, 75 },
    { 3, 4, 5, 12, 13, 14, 18, 19, 20, 21, 23, 24, 25, 26, 31, 40, 49, 58, 67, 76 },
    { 3, 4, 5, 12, 13, 14, 18, 19, 20, 21, 22, 24, 25, 26, 32, 41, 50, 59, 68, 77 },
    { 6, 7, 8, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 33, 42, 51, 60, 69, 78 },
    { 6, 7, 8, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 34, 43, 52, 61, 70, 79 },
    { 6, 7, 8, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 35, 44, 53, 62, 71, 80 },
    { 0, 9, 18, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 45, 46, 47, 54, 63, 72 },
    { 1, 10, 19, 27, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 45, 46, 47, 55, 64, 73 },
    { 2, 11, 20, 27, 28, 30, 31, 32, 33, 34, 35, 36, 37, 38, 45, 46, 47, 56, 65, 74 },
    { 3, 12, 21, 27, 28, 29, 31, 32, 33, 34, 35, 39, 40, 41, 48, 49, 50, 57, 66, 75 },
    { 4, 13, 22, 27, 28, 29, 30, 32, 33, 34, 35, 39, 40, 41, 48, 49, 50, 58, 67, 76 },
    { 5, 14, 23, 27, 28, 29, 30, 31, 33, 34, 35, 39, 40, 41, 48, 49, 50, 59, 68, 77 },
    { 6, 15, 24, 27, 28, 29, 30, 31, 32, 34, 35, 42, 43, 44, 51, 52, 53, 60, 69, 78 },
    { 7, 16, 25, 27, 28, 29, 30, 31, 32, 33, 35, 42, 43, 44, 51, 52, 53, 61, 70, 79 },
    { 8, 17, 26, 27, 28, 29, 30, 31, 32, 33, 34, 42, 43, 44, 51, 52, 53, 62, 71, 80 },
    { 0, 9, 18, 27, 28, 29, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 54, 63, 72 },
    { 1, 10, 19, 27, 28, 29, 36, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 55, 64, 73 },
    { 2, 11, 20, 27, 28, 29, 36, 37, 39, 40, 41, 42, 43, 44, 45, 46, 47, 56, 65, 74 },
    { 3, 12, 21, 30, 31, 32, 36, 37, 38, 40, 41, 42, 43, 44, 48, 49, 50, 57, 66, 75 },
    { 4, 13, 22, 30, 31, 32, 36, 37, 38, 39, 41, 42, 43, 44, 48, 49, 50, 58, 67, 76 },
    { 5, 14, 23, 30, 31, 32, 36, 37, 38, 39, 40, 42, 43, 44, 48, 49, 50, 59, 68, 77 },
    { 6, 15, 24, 33, 34, 35, 36, 37, 38, 39, 40, 41, 43, 44, 51, 52, 53, 60, 69, 78 },
    { 7, 16, 25, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 44, 51, 52, 53, 61, 70, 79 },
    { 8, 17, 26, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 51, 52, 53, 62, 71, 80 },
    { 0, 9, 18, 27, 28, 29, 36, 37, 38, 46, 47, 48, 49, 50, 51, 52, 53, 54, 63, 72 },
    { 1, 10, 19, 27, 28, 29, 36, 37, 38, 45, 47, 48, 49, 50, 51, 52, 53, 55, 64, 73 },
    { 2, 11, 20, 27, 28, 29, 36, 37, 38, 45, 46, 48, 49, 50, 51, 52, 53, 56, 65, 74 },
    { 3, 12, 21, 30, 31, 32, 39, 40, 41, 45, 46, 47, 49, 50, 51, 52, 53, 57, 66, 75 },
    { 4, 13, 22, 30, 31, 32, 39, 40, 41, 45, 46, 47, 48, 50, 51, 52, 53, 58, 67, 76 },
    { 5, 14, 23, 30, 31, 32, 39, 40, 41, 45, 46, 47, 48, 49, 51, 52, 53, 59, 68, 77 },
    { 6, 15, 24, 33, 34, 35, 42, 43, 44, 45, 46, 47, 48, 49, 50, 52, 53, 60, 69, 78 },
    { 7, 16, 25, 33, 34, 35, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 53, 61, 70, 79 },
    { 8, 17, 26, 33, 34, 35, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 62, 71, 80 },
    { 0, 9, 18, 27, 36, 45, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 72, 73, 74 },
    { 1, 10, 19, 28, 37, 46, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 72, 73, 74 },
    { 2, 11, 20, 29, 38, 47, 54, 55, 57, 58, 59, 60, 61, 62, 63, 64, 65, 72, 73, 74 },
    { 3, 12, 21, 30, 39, 48, 54, 55, 56, 58, 59, 60, 61, 62, 66, 67, 68, 75, 76, 77 },
    { 4, 13, 22, 31, 40, 49, 54, 55, 56, 57, 59, 60, 61, 62, 66, 67, 68, 75, 76, 77 },
    { 5, 14, 23, 32, 41, 50, 54, 55, 56, 57, 58, 60, 61, 62, 66, 67, 68, 75, 76, 77 },
    { 6, 15, 24, 33, 42, 51, 54, 55, 56, 57, 58, 59, 61, 62, 69, 70, 71, 78, 79, 80 },
    { 7, 16, 25, 34, 43, 52, 54, 55, 56, 57, 58, 59, 60, 62, 69, 70, 71, 78, 79, 80 },
    { 8, 17, 26, 35, 44, 53, 54, 55, 56, 57, 58, 59, 60, 61, 69, 70, 71, 78, 79, 80 },
    { 0, 9, 18, 27, 36, 45, 54, 55, 56, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 },
    { 1, 10, 19, 28, 37, 46, 54, 55, 56, 63, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 },
    { 2, 11, 20, 29, 38, 47, 54, 55, 56, 63, 64, 66, 67, 68, 69, 70, 71, 72, 73, 74 },
    { 3, 12, 21, 30, 39, 48, 57, 58, 59, 63, 64, 65, 67, 68, 69, 70, 71, 75, 76, 77 },
    { 4, 13, 22, 31, 40, 49, 57, 58, 59, 63, 64, 65, 66, 68, 69, 70, 71, 75, 76, 77 },
    { 5, 14, 23, 32, 41, 50, 57, 58, 59, 63, 64, 65, 66, 67, 69, 70, 71, 75, 76, 77 },
    { 6, 15, 24, 33, 42, 51, 60, 61, 62, 63, 64, 65, 66, 67, 68, 70, 71, 78, 79, 80 },
    { 7, 16, 25, 34, 43, 52, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 71, 78, 79, 80 },
    { 8, 17, 26, 35, 44, 53, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 78, 79, 80 },
    { 0, 9, 18, 27, 36, 45, 54, 55, 56, 63, 64, 65, 73, 74, 75, 76, 77, 78, 79, 80 },
    { 1, 10, 19, 28, 37, 46, 54, 55, 56, 63, 64, 65, 72, 74, 75, 76, 77, 78, 79, 80 },
    { 2, 11, 20, 29, 38, 47, 54, 55, 56, 63, 64, 65, 72, 73, 75, 76, 77, 78, 79, 80 },
    { 3, 12, 21, 30, 39, 48, 57, 58, 59, 66, 67, 68, 72, 73, 74, 76, 77, 78, 79, 80 },
    { 4, 13, 22, 31, 40, 49, 57, 58, 59, 66, 67, 68, 72, 73, 74, 75, 77, 78, 79, 80 },
    { 5, 14, 23, 32, 41, 50, 57, 58, 59, 66, 67, 68, 72, 73, 74, 75, 76, 78, 79, 80 },
    { 6, 15, 24, 33, 42, 51, 60, 61, 62, 69, 70, 71, 72, 73, 74, 75, 76, 77, 79, 80 },
    { 7, 16, 25, 34, 43, 52, 60, 61, 62, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 80 },
    { 8, 17, 26, 35, 44, 53, 60, 61, 62, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79 }
};

int main(void);
void read_grid(grid_t *const);
void write_grid(grid_t const *const);
void write_grid_full(grid_t const *const);
uint8_t check_grid(grid_t *const);
void populate_grid(grid_t *const);
uint8_t solve_grid(grid_t, uint16_t const, uint32_t *const, uint16_t* const);

int main(void) {
    grid_t grid;
    uint32_t calls;
    uint16_t max_depth;

    read_grid(&grid);
    printf("Input:\n");
    write_grid(&grid);
    if(!check_grid(&grid)) {
        fprintf(stderr, NAME "Input grid is not a valid sudoku.\n");
        exit(EXIT_FAILURE);
    }
    populate_grid(&grid);
    calls = 0;
    max_depth = 0;
    if(!solve_grid(grid, 0, &calls, &max_depth)) {
        fprintf(stderr, NAME "No solutions exist.\n");
        exit(EXIT_FAILURE);
    }
    printf("%" PRIu32 " iterations completed.\n", calls);
    printf("Maximum recursion depth %" PRIu32 ".\n", max_depth + 1);
}

// Reads a grid from standard input and fills the "solved" field.
void read_grid(grid_t* const grid) {
    uint8_t cell_index = 0;
    int next_character;
    
    while(1) {
        next_character = getchar();
        switch(next_character) {
            case EOF:
                if(cell_index == CELL_COUNT) {
                    // The input has ended and all cells are filled.
                    return;
                } else {
                    // The input has ended but not all cells were filled.
                    fprintf(stderr, NAME "Did not receive enough inputs (expected %"
                        PRIu8 ", received %" PRIu8 ").\n", CELL_COUNT, cell_index);
                    exit(EXIT_FAILURE);
                }
            case '\t':
            case '\n':
            case '\r':
            case ' ':
                // Ignore all whitespace received.
                continue;
            case '#':
            case '*':
            case '-':
            case '.':
            case '0':
            case '?':
            case '_':
                if(cell_index == CELL_COUNT) {
                    goto overflow;
                }
                // Store placeholders as zeros in "solved" field.
                grid->solved[cell_index] = 0;
                break;
            default:
                if(next_character >= '1' && next_character <= '9') {
                    if(cell_index == CELL_COUNT) {
                        goto overflow;
                    }
                    // Convert digit characters to integers.
                    grid->solved[cell_index] =
                        (uint8_t)(next_character - '1' + 1);
                } else {
                    // Report an error if any abnormal characters were received.
                    fprintf(stderr, NAME "Received invalid characters in input "
                        "(expected whitespace, 0-9, or #*-.?_).\n");
                    exit(EXIT_FAILURE);
                }
        }

        // If the switch statement was navigated successfully, a cell was set.
        cell_index++;
    }

    // If this label was reached, too many inputs were received.
overflow:
    fprintf(stderr, NAME "Received too many inputs (expected no more than %" PRIu8
        ").\n", CELL_COUNT);
    exit(EXIT_FAILURE);
}

// Writes a grid to standard output from its "solved" field.
void write_grid(grid_t const *const grid) {
    uint8_t row_index, column_index, value;
    char buffer[(2 * COLUMN_COUNT) + 1] = BUFFER;

    for(row_index = 0; row_index < ROW_COUNT; row_index++) {
        for(column_index = 0; column_index < COLUMN_COUNT; column_index++) {
            value = grid->solved[(row_index * COLUMN_COUNT) + column_index];
            if(!value) {
                buffer[2 * column_index] = '_';
            } else {
                buffer[2 * column_index] = (char)(value - 1 + '1');
            }
        }
        printf("%s", buffer);
    }
}

// Writes a grid with guesses to standard output.
void write_grid_full(grid_t const *const grid) {
    uint8_t row_index, column_index, digit_index, value, target;
    char buffer[(3 * ROW_LENGTH) + 1] = GRID_BUFFER;

    for(row_index = 0; row_index < ROW_COUNT; row_index++) {
        for(column_index = 0; column_index < COLUMN_COUNT; column_index++) {
            for(digit_index = 0; digit_index < DIGIT_COUNT; digit_index++) {
                value = grid->candidates[(row_index * COLUMN_COUNT) +
                    column_index][digit_index];
                target = (ROW_LENGTH * (digit_index / 3)) +
                    (SPACING * column_index) + (2 * (digit_index % 3));
                if(!value) {
                    buffer[target] = '_';
                } else {
                    buffer[target] = (char)(digit_index + '1');
                }
            }
        }
        printf("%s", buffer);
        if(row_index != ROW_COUNT - 1) {
            printf("\n");
        }
    }
}

// Ensures that a solved or partially solved grid is a valid sudoku.
uint8_t check_grid(grid_t *const grid) {
    uint8_t cell_index, check_index, target_index, value;

    for(cell_index = 0; cell_index < CELL_COUNT; cell_index++) {
        value = grid->solved[cell_index];
        if(!value) {
            continue;
        }
        for(check_index = 0; check_index < CONSTRAINT_COUNT; check_index++) {
            target_index = constraints[cell_index][check_index];
            if(grid->solved[target_index] == value) {
                return 0;
            }
        }
    }

    return 1;
}

// Populates the "candidates" field of a grid in preparation for solving.
void populate_grid(grid_t *const grid) {
    uint8_t cell_index, digit_index, value;

    for(cell_index = 0; cell_index < CELL_COUNT; cell_index++) {
        value = grid->solved[cell_index];
        for(digit_index = 0; digit_index < DIGIT_COUNT; digit_index++) {
            grid->candidates[cell_index][digit_index] = !value || value == digit_index + 1;
        }
    }
}

// Solves a grid recursively.
uint8_t solve_grid(grid_t grid, uint16_t const depth, uint32_t *const calls, uint16_t *const max_depth) {
    uint8_t cell_index, check_index, digit_index, found, status, value;
    uint8_t candidates[DIGIT_COUNT];
    uint16_t iteration;

    (*calls)++;
    if(depth > *max_depth) {
        *max_depth = depth;
    }

    if(depth == MAX_RECURSIONS) {
        fprintf(stderr, NAME "Exceeded recursion depth (%" PRIu16 ").\n",
            MAX_RECURSIONS);
    }

    for(iteration = 0; 1; iteration++) {
        if(iteration == MAX_ITERATIONS) {
            fprintf(stderr, NAME "Exceeded iteration count (%" PRIu16 ").\n",
                MAX_ITERATIONS);
        }

#ifdef TRACE
        printf("Solving (%" PRIu16 ", %" PRIu16 "):\n", depth, iteration);
        write_grid(&grid);
        write_grid_full(&grid);
#endif

        // Step 1: remove candidates.
        for(cell_index = 0; cell_index < CELL_COUNT; cell_index++) {
            // Check all unsolved cells.
            if(grid.solved[cell_index]) {
                continue;
            }
            for(check_index = 0; check_index < CONSTRAINT_COUNT; check_index++) {
                // Check all constraint-related solved cells and disable candidates.
                value = grid.solved[constraints[cell_index][check_index]];
                if(!value) {
                    continue;
                }
                grid.candidates[cell_index][value - 1] = 0;
            }
        }

        // Step 2: check for new digits.
        status = 0;
        for(cell_index = 0; cell_index < CELL_COUNT; cell_index++) {
            // Check all unsolved cells.
            if(grid.solved[cell_index]) {
                continue;
            }
            found = 0;
            for(digit_index = 0; digit_index < DIGIT_COUNT; digit_index++) {
                // Proceed until a set candidate is found.
                if(!grid.candidates[cell_index][digit_index]) {
                    continue;
                }
                if(!found) {
                    // No others were yet found; mark this one.
                    found = digit_index + 1;
                } else {
                    // Another was found; indicate failure.
                    found = DIGIT_COUNT + 1;
                    break;
                }
            }
            if(!found) {
                // No candidates were found (an invalid state was reached).
                return 0;
            } else if(found <= DIGIT_COUNT) {
                // Exactly one candidate was found; mark the cell as solved.
                grid.solved[cell_index] = found;
                status = 1;
            }
        }
        // When multiple candidates are eliminated at once from a grid with an error,
        // it is possible to reach this point in an invalid state: make sure that all
        // solved cells satisfy the sudoku constraints at this point.
        if(!check_grid(&grid)) {
            return 0;
        }

        // Step 3: if no new digits were set, recurse; otherwise, check for solution.
        if(!status) {
            // Keep track of the index and value of the best cell.
            check_index = CELL_COUNT;
            value = DIGIT_COUNT;
            for(cell_index = 0; cell_index < CELL_COUNT; cell_index++) {
                // Look for unsolved cells with 2 or more candidates present.
                if(grid.solved[cell_index]) {
                    continue;
                }
                found = 0;
                for(digit_index = 0; digit_index < DIGIT_COUNT; digit_index++) {
                    if(grid.candidates[cell_index][digit_index]) {
                        found++;
                    }
                }
                // Cells with fewer candidates are superior.
                if(found < value) {
                    check_index = cell_index;
                    value = found;
                }
            }

            // Try each candidate in turn.
            memmove(candidates, grid.candidates[check_index],
                DIGIT_COUNT * sizeof(uint8_t));
            found = 0;
            for(digit_index = 0; digit_index < DIGIT_COUNT; digit_index++) {
                if(!candidates[digit_index]) {
                    continue;
                }
                // The grid cell can be modified since the routine will be returning
                // unconditionally after this point and the needed candidate data has
                // already been copied out.
                grid.solved[check_index] = digit_index + 1;
                for(value = 0; value < DIGIT_COUNT; value++) {
                    grid.candidates[check_index][value] = value == digit_index;
                }

#ifdef TRACE
                printf("Substituting (%" PRIu8 ", %" PRIu8 ").\n", digit_index,
                    check_index);
#endif
                
                // Do not feed the solver an invalid grid to start.
                if(check_grid(&grid) && solve_grid(grid, depth + 1, calls, max_depth)) {
                    found = 1;
                }
            }
            return found;
        } else {
            // See if a solution was found (all cells solved).
            found = 1;
            for(cell_index = 0; cell_index < CELL_COUNT; cell_index++) {
                if(!grid.solved[cell_index]) {
                    found = 0;
                    break;
                }
            }
            if(found) {
                printf("Solution found:\n");
                write_grid(&grid);
                return 1;
            }
        }
    }
}