Thread: Sudoku Puzzle Solver

Here's my attempt at a sudoku puzzle solver in C. Please note this is not a copy & paste and implement in C solution but a solution I build from the ground up..

Also: This is a brute force solution but that shouldn't be a concern(stack overflow) because a sudoku puzzle only has 81 squares so the function call depth shouldn't exceed 81 by much.

The sudoku puzzle to solve is stored in an array(Sudoku_Str) in main.c. The values of the sudoku puzzle are placed into the array(Sudoku_Str) row by row. i.e. Enter the values of the first row and then the second row and so on.

Code:

#define SUDOKU_SIZE 81

unsigned int Sudoku_Str[SUDOKU_SIZE] = {
    0, 0, 0, 0, 0, 8, 0, 0, 0, 2,
    0, 0, 0, 5, 9, 0, 0, 0, 1, 0,
    0, 0, 0, 0, 2, 5, 0, 0, 0, 8,
    0, 0, 1, 4, 6, 0, 3, 0, 0, 0,
    0, 0, 1, 0, 0, 9, 0, 4, 0, 8,
    3, 0, 0, 0, 0, 0, 0, 5, 0, 0,
    0, 8, 4, 0, 0, 0, 0, 0, 4, 9,
    0, 0, 0, 2, 3, 0, 0, 0, 0, 0, 0};

Here's the code:
dyn_array.h

Code:

#ifndef DYN_ARRAY__HH
#define DYN_ARRAY__HH

#define ARR_LENGTH_MULTI 2

typedef unsigned int *ARRAY;
typedef struct dyn_array *DYN_ARRAY_PTR;
typedef void (*APPEND)(DYN_ARRAY_PTR, unsigned int);
typedef void (*DISPLAY)(DYN_ARRAY_PTR);
typedef void (*FREE)(DYN_ARRAY_PTR);

typedef struct dyn_array
{
    size_t pos;
    size_t length;
    ARRAY arr;
    APPEND append;
    DISPLAY display;
    FREE free;
} DYN_ARRAY;

DYN_ARRAY_PTR createNewDynamicArray(size_t);

#endif

dyn_array.c

Code:

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

void check_allocation(void *ptr)
{
    if (!ptr)
    {
        fputs("Allocation failed!\n", stderr);
        exit(EXIT_FAILURE);
    }
}

static void append(DYN_ARRAY_PTR da, unsigned int value)
{
    if (da->pos < da->length)
    {
        da->arr[da->pos++] = value;
        return;
    }
    size_t new_length = da->length * ARR_LENGTH_MULTI;
    da->arr = realloc(da->arr, new_length);
    check_allocation(da->arr);
    da->arr[da->pos++] = value;
    da->length = new_length;
}

static void display(DYN_ARRAY_PTR da)
{
    if (da)
    {
        fprintf(stdout, "Pos: %ld, Len: %ld\n", da->pos, da->length);
        fputs("[ ", stdout);
        if (da->arr)
        {
            size_t i = 0;
            for (; i < da->length; i++)
            {
                fprintf(stdout, "%d ", da->arr[i]);
            }
        }
        fputs("]\n", stdout);
    }
}

static void free_array(DYN_ARRAY_PTR da)
{
    free(da->arr);
    free(da);
}

DYN_ARRAY_PTR createNewDynamicArray(size_t length)
{
    DYN_ARRAY_PTR ans = malloc(sizeof(*ans));
    check_allocation(ans);
    ans->arr = calloc(sizeof(*ans->arr), length);
    check_allocation(ans);
    ans->pos = 0;
    ans->length = length;
    ans->append = append;
    ans->display = display;
    ans->free = free_array;
    return ans;
}

main.c

Code:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "dyn_array.h"

#define SUDOKU_SIZE 81
#define SUDOKU_ROW 9
#define SUDOKU_BOX 3
#define BOX_EDGES 4
#define NUM_EDGES 20

const unsigned int Sudoku_Valid_Characters[SUDOKU_ROW] = {
    1, 2, 3, 4, 5, 6, 7, 8, 9};

// Sudoku puzzle to solve
unsigned int Sudoku_Str[SUDOKU_SIZE] = {
    0, 0, 0, 0, 0, 8, 0, 0, 0, 2,
    0, 0, 0, 5, 9, 0, 0, 0, 1, 0,
    0, 0, 0, 0, 2, 5, 0, 0, 0, 8,
    0, 0, 1, 4, 6, 0, 3, 0, 0, 0,
    0, 0, 1, 0, 0, 9, 0, 4, 0, 8,
    3, 0, 0, 0, 0, 0, 0, 5, 0, 0,
    0, 8, 4, 0, 0, 0, 0, 0, 4, 9,
    0, 0, 0, 2, 3, 0, 0, 0, 0, 0, 0};
// Sudoku puzzle to solve

typedef struct rrp
{
    unsigned int r;
    unsigned int rp;
} RRP;

RRP build_rrp(const unsigned int p)
{
    RRP ans = {(p % SUDOKU_ROW), (p / SUDOKU_ROW)};
    return ans;
}

DYN_ARRAY_PTR build_row(const unsigned int p)
{
    DYN_ARRAY_PTR ans = createNewDynamicArray(SUDOKU_ROW - 1);
    RRP rrp = build_rrp(p);
    size_t e = 0;
    for (; e < SUDOKU_ROW; e++)
    {
        if (e != rrp.r)
        {
            ans->append(ans, (e + (rrp.rp * SUDOKU_ROW)));
        }
    }
    return ans;
}

DYN_ARRAY_PTR build_col(const unsigned int p)
{
    DYN_ARRAY_PTR ans = createNewDynamicArray(SUDOKU_ROW - 1);
    RRP rrp = build_rrp(p);
    size_t e = 0;
    for (; e < SUDOKU_ROW; e++)
    {
        if (e != rrp.rp)
        {
            ans->append(ans, (rrp.r + (e * SUDOKU_ROW)));
        }
    }
    return ans;
}

typedef struct box_offset
{
    int x;
    int y;
} BOX_OFFSET;

BOX_OFFSET build_box_offset(const unsigned int p)
{
    BOX_OFFSET ans;
    if (p == 0)
    {
        ans.x = 1;
        ans.y = 2;
        return ans;
    }
    else if (p == 1)
    {
        ans.x = -1;
        ans.y = 1;
        return ans;
    }
    ans.x = -2;
    ans.y = -1;
    return ans;
}

DYN_ARRAY_PTR build_box(const unsigned int p)
{
    DYN_ARRAY_PTR ans = createNewDynamicArray(BOX_EDGES);
    BOX_OFFSET r = build_box_offset((p / SUDOKU_ROW) % SUDOKU_BOX);
    BOX_OFFSET c = build_box_offset(p % SUDOKU_BOX);
    ans->append(ans, (c.x + p + (r.x * SUDOKU_ROW)));
    ans->append(ans, (c.x + p + (r.y * SUDOKU_ROW)));
    ans->append(ans, (c.y + p + (r.x * SUDOKU_ROW)));
    ans->append(ans, (c.y + p + (r.y * SUDOKU_ROW)));
    return ans;
}

DYN_ARRAY_PTR build_edges(const unsigned int p)
{
    DYN_ARRAY_PTR ans = createNewDynamicArray(NUM_EDGES);
    size_t i = 0;
    DYN_ARRAY_PTR row = build_row(p);
    DYN_ARRAY_PTR col = build_col(p);
    DYN_ARRAY_PTR box = build_box(p);
    for (; i < row->pos; i++)
    {
        ans->append(ans, row->arr[i]);
    }
    for (i = 0; i < col->pos; i++)
    {
        ans->append(ans, col->arr[i]);
    }
    for (i = 0; i < box->pos; i++)
    {
        ans->append(ans, box->arr[i]);
    }
    row->free(row);
    col->free(col);
    box->free(box);
    return ans;
}

DYN_ARRAY_PTR build_starting_values(const DYN_ARRAY_PTR edges)
{
    DYN_ARRAY_PTR ans = createNewDynamicArray(SUDOKU_ROW);
    bool found = false;
    size_t i = 0, j = 0;
    for (; i < SUDOKU_ROW; i++)
    {
        for (j = 0; j < edges->pos; j++)
        {
            if (Sudoku_Str[edges->arr[j]] == Sudoku_Valid_Characters[i])
            {
                found = true;
                break;
            }
        }
        if (!found)
        {
            ans->append(ans, Sudoku_Valid_Characters[i]);
        }
        found = false;
    }
    return ans;
}

typedef struct sudoku_data
{
    size_t position;
    unsigned int value;
    bool fixed;
    DYN_ARRAY_PTR edges;
    DYN_ARRAY_PTR starting_values;
} SUDOKU_DATA;
typedef struct sudoku_data *SUDOKU_DATA_PTR;

SUDOKU_DATA_PTR build_sudoku_data()
{
    SUDOKU_DATA_PTR ans = calloc(sizeof(*ans), SUDOKU_SIZE);
    size_t i = 0;
    for (; i < SUDOKU_SIZE; i++)
    {
        bool fixed = Sudoku_Str[i] != 0;
        if (fixed)
        {
            SUDOKU_DATA da = {i, Sudoku_Str[i], fixed, NULL, NULL};
            ans[i] = da;
        }
        else
        {
            DYN_ARRAY_PTR edges = build_edges(i);
            SUDOKU_DATA da = {i, Sudoku_Str[i], fixed, edges, build_starting_values(edges)};
            ans[i] = da;
        }
    }
    return ans;
}

void solve_it(const SUDOKU_DATA_PTR s, size_t p, bool free_data)
{
    if (p < SUDOKU_SIZE)
    {
        if (s[p].fixed)
        {
            solve_it(s, p + 1, free_data);
        }
        else
        {
            bool found = false;
            size_t i = 0, j = 0;
            for (i = 0; i < s[p].starting_values->pos; i++)
            {
                for (j = 0; j < s[p].edges->pos; j++)
                {
                    if (Sudoku_Str[s[p].edges->arr[j]] == s[p].starting_values->arr[i])
                    {
                        found = true;
                        break;
                    }
                }
                if (!found)
                {
                    Sudoku_Str[p] = s[p].starting_values->arr[i];
                    solve_it(s, p + 1, free_data);
                    Sudoku_Str[p] = 0;
                }
                found = false;
            }
        }
    }
    else
    {
        size_t i = 0;
        for (; i < SUDOKU_SIZE; i++)
        {
            fprintf(stdout, "%d ", Sudoku_Str[i]);
        }
        if (free_data)
        {
            for (i = 0; i < SUDOKU_SIZE; i++)
            {
                if (s[i].edges)
                    s[i].edges->free(s[i].edges);
                if (s[i].starting_values)
                    s[i].starting_values->free(s[i].starting_values);
            }
            free(s);
        }
        exit(EXIT_SUCCESS);
    }
}

int main(int argc, char **argv)
{
    solve_it(build_sudoku_data(), 0, true);
    return 0;
}

The program compiles and runs without any problems and I even used valgrind to check that I could free all allocated memory.

Any comments? Please post them.