sudoku_solver.c

//
//  main.c
//  Sodoku
//
//  Created by Kent Miller on 4/7/20.
//  Copyright © 2020 Kent Miller. All rights reserved.
//

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

char *puz[] = {
    "000300028200600000070008090010760009007000100900015040020900050000001007840006000",  //original puzzle
    "002080050000021040000500702075000900010903070009000310604008000080230000020090400",  //original puzzle 2
    "300400107000890003050000008000040500560903014007050000700000030900032000205004001",  //iron sudoku sept 19
    "016400000200009000400000062070230100100000003003087040960000005000800007000006820",
    "049008605003007000000000030000400800060815020001009000010000000000600400804500390",
    "760500000000060008000000403200400800080000030005001007809000000600010000000003041",
    "000605000003020800045090270500000001062000540400000007098060450006040700000203000",
    "409000705000010000006207800200000009003704200800000004002801500000060000905000406",
    "000010030040070501002008006680000003000302000300000045200500800801040020090020000",
    "080070030260050018000000400000602000390010086000709000004000800810040052050090070",
    "000093006000800900020006100000080053006000200370050000002500040001009000700130000",
    NULL
};

void PrintPuzzle(int8_t *puzzle)
{
    for (int y=0; y<9; y++)
    {
        int8_t* b = &puzzle[y*9];
        char  c[9];
        for (int x=0; x<9;x++)
        {
            c[x] = b[x] ? '0' + b[x] : '.';
        }
        printf("%c %c %c  %c %c %c  %c %c %c\n",
            c[0], c[1], c[2],
            c[3], c[4], c[5],
            c[6], c[7], c[8]);
        if ((y == 2) || (y == 5))
            printf("\n");
    }
}

int PuzzleErrors(int8_t *puzzle)
{
    //check row
    for (int y=0; y<9; y++)
    {
        int8_t seen[10] = {0};
        for (int x=0; x<9; x++)
        {
            int8_t num = puzzle[y*9+x];
            if (num != 0)
            {
                if (seen[num] != 0)
                    return 1;
                else
                    seen[num] = 1;
            }
        }
    }

    //check col
    for (int x=0; x<9; x++)
    {
        int8_t seen[10] = {0};
        for (int y=0; y<9; y++)
        {
            int8_t num = puzzle[y*9+x];
            if (num != 0)
            {
                if (seen[num] != 0)
                    return 2;
                else
                    seen[num] = 1;
            }
        }
    }

    //check minisquare
    {
        for (int y=0; y<9; y+=3)
        {
            for (int x=0; x<9; x+=3)
            {
                int8_t seen[10] = {0};
                for (int YY=0; YY<3; YY++)
                {
                    for (int XX=0; XX<3; XX++)
                    {
                        int8_t num = puzzle[(y+YY)*9+(XX+x)];
                        if (num != 0)
                        {
                            if (seen[num] != 0)
                                return 3;
                            else
                                seen[num] = 1;
                        }
                    }
                }
            }
        }
    }
    return 0;
}

uint64_t itr = 0;
int Solved(int8_t *puzzle)
{
    for (int II=0; II<81; II++)
    {
        if (puzzle[II] == 0)
            return 0;
    }
    if (0 == PuzzleErrors(puzzle))
    {
        printf("Solved!\n");
        PrintPuzzle(puzzle);
        printf("%"PRIu64" Iterations\n",itr);
        return 1;
    }
    return 0;
}

#define DEBUGPRINT 0

int Solve(int8_t *puzzle, int *solved)
{
    if (*solved)
    {
        return 0;
    }
    else
    {
        *solved = Solved(puzzle);
        if (*solved)
            return 0;
    }

    int err = PuzzleErrors(puzzle);
    itr++;
#if DEBUGPRINT
    printf("Iteration %"PRIu64"\n", itr);
    PrintPuzzle(puzzle);
    switch (err)
    {
        case 0:   printf("Still OK\n"); break;
        case 1:   printf("Row error\n"); break;
        case 2:   printf("Column error\n"); break;
        case 3:   printf("Square error\n"); break;
    }
#endif
    if (err)
        return err;

    int trypos=-1;
    //Look for a position to try
    for (int II=0; II<81; II++)
    {
        if (puzzle[II] == 0)
        {
            trypos = II;
            break;
        }
    }
    if (trypos == -1)
    {
        Solved(puzzle);
    }
    else
    {
#if DEBUGPRINT
        printf("Trying position %d\n", trypos);
#endif
        for (int II=1; II <= 9; II++)
        {
            puzzle[trypos] = II;
            Solve(puzzle, solved);
        }
        puzzle[trypos] = 0;
    }

    return 0;
}


int main(int argc, const char * argv[]) {
    int PPP = 0;
    while (1)
    {
        int solved = 0;

        if (puz[PPP] == NULL)
            break;
        char *ps = puz[PPP];

        int8_t puzzle[9*9];
        for (int j = 0; j < 9*9; j++)
        {
            puzzle[j] = ps[j] - '0';
        }
        PrintPuzzle(puzzle);
        printf("\n\n\n");
        Solve(puzzle, &solved);
        printf("************\n\n\n");

        PPP++;
    }

    return 0;
}