Sudoku solver, gcc sudoku_solver.c -O2 -o sudoku_solver && echo '..6.7......9.....35..163...38...27.6.......8.7.....2596..5.71...5.....3.....218..' | ./sudoku_solver

sudoku_solver.c

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

#include "sudoku_solver.h"

int fill(sudokuGrid grid, int row, int column, int entry)
{
    for (int i = 0; i < DIMENSIONS; i++) {
        /* check row */
        if (grid[row][i] == entry)
            return 0;

        /* check column */
        if (grid[i][column] == entry)
            return 0;
    }

    /* grid and row of top left corner of subgrid */
    int subgridRow = row / SUB_DIMENSIONS * SUB_DIMENSIONS;
    int subgridColumn = column / SUB_DIMENSIONS * SUB_DIMENSIONS;

    /* check subgrid */
    for (int i = subgridRow; i < subgridRow + SUB_DIMENSIONS; i++) {
        for (int j = subgridColumn; j < subgridColumn + SUB_DIMENSIONS; j++) {
            if (grid[i][j] == entry)
                return 0;
        }
    }

    /* fill the grid at specified position */
    grid[row][column] = entry;

    return 1;
}

int backTrack(sudokuGrid grid, int startOffset, int emptySquares)
{
    if (interactive)
        clearTerminalAndPrintGrid(grid);

    if (!emptySquares)
        return 1;

    for (int i = startOffset; i < DIMENSIONS * DIMENSIONS; i++) {
        int r = i / DIMENSIONS;
        int c = i % DIMENSIONS;

        /* skip square if it's non-empty */
        if (grid[r][c])
            continue;

        /* try to fill empty square with each number */
        for (int k = 1; k < DIMENSIONS + 1; k++) {
            /* try to fill each square */
            if (fill(grid, r, c, k)) {
                if (backTrack(grid, i + 1, emptySquares - 1))
                    return 1;

                /* number didn't work, so unfill it */
                grid[r][c] = 0;
            }
        }

        /* square can't be filled, so no solution */
        return 0;

    }

    return 0;
}

int solve(sudokuGrid grid)
{
    int emptySquares = 0;
    for (int i = 0; i < DIMENSIONS; i++) {
        for (int j = 0; j < DIMENSIONS; j++) {
            if (!grid[i][j])
                emptySquares++;
        }
    }

    return backTrack(grid, 0, emptySquares);
}

void printLine(sudokuGrid grid)
{
    for (int i = 0; i < DIMENSIONS; i++) {
        for (int j = 0; j < DIMENSIONS; j++) {
            if (!grid[i][j])
                printf(".");
            else
                printf("%d", grid[i][j]);
        }
    }
    printf("\n");
}

void printGrid(sudokuGrid grid)
{
    for (int i = 0; i < DIMENSIONS; i++) {
        for (int j = 0; j < DIMENSIONS; j++) {
            if (!grid[i][j])
                printf(". ");
            else
                printf("%d ", grid[i][j]);

            if (j % SUB_DIMENSIONS == SUB_DIMENSIONS - 1)
                printf(" ");
        }

        if (i != DIMENSIONS - 1)
            printf("\n");

        if (i % SUB_DIMENSIONS == SUB_DIMENSIONS - 1)
            printf("\n");
    }
}

void clearTerminalAndPrintGrid(sudokuGrid grid)
{
    struct timespec tim, tim2;
    tim.tv_sec = 0;
    tim.tv_nsec = 700000;

    nanosleep(&tim , &tim2);
    printf("%c", 27);
    printf("[2J\n");

    if (compact)
        printLine(grid);
    else
        printGrid(grid);
}

int main(int argc, char *argv[])
{
    if (argc > 3)  {
        printf("Usage: sudoku_solver [-i]\n");
        return 1;
    }

    compact = 0;

    /* get optional arguments */
    for (int i = 1; i < argc; i++) {
        if (!strcmp("-i", argv[i])) {
            interactive = 1;
        }
        if (!strcmp("-c", argv[i])) {
            compact = 1;
        }
    }

    sudokuGrid grid;
    char *line = NULL;
    size_t size = DIMENSIONS * DIMENSIONS + 5;

    /* read puzzle from stdin */
    size_t numCharacters = getline(&line, &size, stdin);

    if (numCharacters != DIMENSIONS * DIMENSIONS + 1) {
        printf("Number of entries != %d\n", DIMENSIONS * DIMENSIONS);
        return 1;
    }

    for (int i = 0; i < DIMENSIONS * DIMENSIONS; i++) {
        char elem[2];
        elem[0] = line[i];
        elem[1] = 0;

        int row = i / DIMENSIONS;
        int column = i % DIMENSIONS;

        grid[row][column] = atoi(elem);
    }

    if (!compact) {
        printf("Starting grid:\n\n");
        printGrid(grid);
    }

    solve(grid);

    if (interactive) {
        /* clear teminal */
        printf("%c", 27);
        printf("[2J\n");
    }

    if (compact) {
        printLine(grid);
    }
    else {
        printf("\nSolved grid:\n\n");
        printGrid(grid);
    }

    return 0;
}

sudoku_solver.h

#ifndef SUDOKU_SOLVER_H_
#define SUDOKU_SOLVER_H_

#define DIMENSIONS 9
#define SUB_DIMENSIONS 3

/* represent sudoku grid as 2D array of char */
typedef char sudokuGrid[DIMENSIONS][DIMENSIONS];

/* flag to indicate if intermediate steps are printed */
int interactive = 0;

/* flag to indicate that grid should be printed in one line */
int compact = 0;

int solve(sudokuGrid grid);

void printGrid(sudokuGrid grid);

void printLine(sudokuGrid grid);

void clearTerminalAndPrintGrid(sudokuGrid grid);

#endif /* SUDOKU_SOLVER_H_ */