sudokusolver.c

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

// SET INITIALIZATION

struct Set {
    int *data;
    int size;
};

typedef struct Set *SetPtr;

SetPtr set_init(int size)
{
    SetPtr set = (SetPtr) malloc(sizeof(struct Set));
    set->size = size;
    set->data = (int *) malloc(sizeof(int) * size);
    int idx;
    for (idx = 0; idx < size; idx++)
        set->data[idx] = -1;
    return set;
}

void set_free(SetPtr set)
{
    free(set->data);
    free(set);
}

void set_print(SetPtr set)
{
    printf("{ ");
    int idx;
    for (idx = 0; idx < set->size; idx++)
    {
        if (set->data[idx] != -1)
            printf("%d ", idx);
    }
    printf("}\n");
}

void set_print1(SetPtr set)
{
    printf("{ ");
    int idx;
    for (idx = 0; idx < set->size; idx++)
    {
        if (set->data[idx] != -1)
            printf("%d ", idx+1);
    }
    printf("}\n");
}

void set_add(SetPtr set, int elem)
{
    if (elem < 0 || elem > set->size)
        return;
    set->data[elem] = elem;
}

void set_remove(SetPtr set, int elem)
{
    if (elem < 0 || elem > set->size)
        return;
    set->data[elem] = -1;
}

int set_find_lowest(SetPtr set)
{
    int idx;
    for (idx = 0; idx < set->size; idx++)
    {
        if (set->data[idx] != -1)
            return set->data[idx];
    }
    return -1;
}

// SUDOKU TABLE INITIALIZATION

struct Table {
    int *data;
    int size;
    int given_flag;
    int num_mask;
};

typedef struct Table *TablePtr;

TablePtr table_init(int size) 
{
    int element_count = size * size;
    
    TablePtr table = (TablePtr) malloc(sizeof(struct Table));
    table->size = size;
    table->data = (int *) malloc(sizeof(int) * element_count);
    int idx;
    for (idx = 0; idx < element_count; idx++) 
    {
        table->data[idx] = -1;
    }
    
    table->given_flag = 1;
    while (element_count > 0) 
    {
        element_count >>= 1;
        table->given_flag <<= 1;   
    }
    table->num_mask = table->given_flag - 1;

    return table;
}

void table_free(TablePtr table)
{
    free(table->data);
    free(table);
}

void table_place_given(TablePtr table, int x, int y, int given) 
{
    if (given < 0 || given > table->size)
        return;
    table->data[y*table->size + x] = (given - 1) | table->given_flag;
}

void table_print(TablePtr table) 
{
    int size = table->size;
    int y, x;
    for (y = 0; y < size; y++) 
    {
        for (x = 0; x < size; x++) 
        {
            int num = table->data[y*size + x];
            if (num == -1)
                printf("_ ");
            else 
            {
                num &= table->num_mask;
                printf("%d ", num + 1);   
            }
        }
        printf("\n");
    }
}

int table_calc_lowest(TablePtr table, SetPtr set, int ptr)
{
    // clear the set, and fill the set with values greater than the current number of the current cell
    int idx;
    for (idx = 0; idx <= table->data[ptr]; idx++)
        set_remove(set, idx);
    for (idx = table->data[ptr] + 1; idx < table->size; idx++)
        set_add(set, idx);
    
    // remove numbers horizontal and vertical of the current cell, from the set
    for (idx = 0; idx < table->size; idx++)
    {
        set_remove(set, table->data[(ptr/table->size) * table->size + idx] & table->num_mask);
        set_remove(set, table->data[ptr%table->size + idx * table->size] & table->num_mask);
    }

    // if table is 9x9, also calculate the 3x3 space of the current cell
    if (table->size == 9)
    {
        int y = (ptr / 9 / 3) * 3;
        int x = ((ptr % 9) / 3) * 3;

        set_remove(set, table->data[y * 9 + x] & table->num_mask);
        set_remove(set, table->data[y * 9 + x + 1] & table->num_mask);
        set_remove(set, table->data[y * 9 + x + 2] & table->num_mask);

        set_remove(set, table->data[(y + 1) * 9 + x] & table->num_mask);
        set_remove(set, table->data[(y + 1) * 9 + x + 1] & table->num_mask);
        set_remove(set, table->data[(y + 1) * 9 + x + 2] & table->num_mask);

        set_remove(set, table->data[(y + 2) * 9 + x] & table->num_mask);
        set_remove(set, table->data[(y + 2) * 9 + x + 1] & table->num_mask);
        set_remove(set, table->data[(y + 2) * 9 + x + 2] & table->num_mask);
    }
    
    return set_find_lowest(set);
}

void table_solve(TablePtr table, int prev) 
{
    SetPtr set = set_init(table->size);
    int element_count = table->size * table->size;
    int ptr = 0;
    int is_backing = 0;
    while (ptr < element_count) 
    {
        // continue moving forward or backward if cell contains given number from original problem
        if (table->data[ptr] != -1 && (table->data[ptr] & table->given_flag)) 
        {
            if (prev)
                printf("it's a given\nforward\n");
            ptr += (is_backing) ? -1 : 1;
        } 
        // process cell
        else 
        {
            // if cell is empty, calculate the lowest possible number
            // if cell is filled, calculate the next lowest possible number
            int next_num = table_calc_lowest(table, set, ptr);
            table->data[ptr] = next_num;
            if (prev)
            {
                printf("available nums: ");
                set_print1(set);
            }
            // if no possible number is found, clear the cell and go backwards
            if (next_num == -1)
            {
                if (prev)
                    printf("no num found :(\nforward\n");
                ptr--;
                is_backing = 1;
            }
            // if possible number is found, fill the cell with the number and go forwards
            else
            {
                if (prev)
                    printf("placed %d\nforward\n", next_num+1);
                ptr++;
                is_backing = 0;
            }
        }
        if (prev)
        {
            table_print(table);
            printf("\n");
        }
    }
    set_free(set);
}

// GUTS

TablePtr table9x9()
{
    TablePtr table = table_init(9);
    table_place_given(table, 0, 0, 3);
    table_place_given(table, 3, 0, 8);
    table_place_given(table, 5, 0, 1);
    table_place_given(table, 8, 0, 2);

    table_place_given(table, 0, 1, 2);
    table_place_given(table, 2, 1, 1);
    table_place_given(table, 4, 1, 3);
    table_place_given(table, 6, 1, 6);
    table_place_given(table, 8, 1, 4);

    table_place_given(table, 3, 2, 2);
    table_place_given(table, 5, 2, 4);

    table_place_given(table, 0, 3, 8);
    table_place_given(table, 2, 3, 9);
    table_place_given(table, 6, 3, 1);
    table_place_given(table, 8, 3, 6);

    table_place_given(table, 1, 4, 6);
    table_place_given(table, 7, 4, 5);

    table_place_given(table, 0, 5, 7);
    table_place_given(table, 2, 5, 2);
    table_place_given(table, 6, 5, 4);
    table_place_given(table, 8, 5, 9);

    table_place_given(table, 3, 6, 5);
    table_place_given(table, 5, 6, 9);

    table_place_given(table, 0, 7, 9);
    table_place_given(table, 2, 7, 4);
    table_place_given(table, 4, 7, 8);
    table_place_given(table, 6, 7, 7);
    table_place_given(table, 8, 7, 5);

    table_place_given(table, 0, 8, 6);
    table_place_given(table, 3, 8, 1);
    table_place_given(table, 5, 8, 7);
    table_place_given(table, 8, 8, 3);
    return table;
}

TablePtr table5x5()
{
    TablePtr table = table_init(5);
    table_place_given(table, 0, 0, 1);
    table_place_given(table, 1, 1, 2);
    table_place_given(table, 2, 2, 3);
    table_place_given(table, 3, 3, 4);
    table_place_given(table, 4, 4, 5);
    return table;
}

int main()
{
    TablePtr table = table9x9();

    printf("GIVEN TABLE:\n");
    table_print(table);
    printf("\nSOLVING TABLE...\n");
    table_solve(table, 1);
    printf("\n\nSOLVED TABLE:\n");
    table_print(table);

    table_free(table);
    return 0;
}