sudoku/sudoku.c

#include <stdio.h>
#include <stdbool.h>

#define UNDEFINED -1
#define MULTIPLE -2
#define FIELD_UNDEFINED UNDEFINED
#define FIELD_MULTIPLE MULTIPLE

#define VALUE_UNDEFINED UNDEFINED
#define VALUE_MULTIPLE MULTIPLE
#define VALUE_ALREADY_SET -3


// https://en.wikipedia.org/wiki/Sudoku#/media/File:Sudoku_Puzzle_by_L2G-20050714_standardized_layout.svg
/*
int sudoku[9][9] = {
    {5,3,VALUE_UNDEFINED,6,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,9,8},
    {VALUE_UNDEFINED,7,VALUE_UNDEFINED,1,9,5,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED},
    {VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,6,VALUE_UNDEFINED},
    {8,VALUE_UNDEFINED,VALUE_UNDEFINED,4,VALUE_UNDEFINED,VALUE_UNDEFINED,7,VALUE_UNDEFINED,VALUE_UNDEFINED},
    {VALUE_UNDEFINED,6,VALUE_UNDEFINED,8,VALUE_UNDEFINED,3,VALUE_UNDEFINED,2,VALUE_UNDEFINED},
    {VALUE_UNDEFINED,VALUE_UNDEFINED,3,VALUE_UNDEFINED,VALUE_UNDEFINED,1,VALUE_UNDEFINED,VALUE_UNDEFINED,6},
    {VALUE_UNDEFINED,6,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED},
    {VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,4,1,9,VALUE_UNDEFINED,8,VALUE_UNDEFINED},
    {2,8,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,5,VALUE_UNDEFINED,7,9}
};
*/

// https://www.free-sudoku.com/sudoku.php?dchoix=evil
int sudoku[9][9] = {
    {VALUE_UNDEFINED,1,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED},
    {3,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,8,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED},
    {VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,4,VALUE_UNDEFINED,VALUE_UNDEFINED,7,VALUE_UNDEFINED},
    {4,VALUE_UNDEFINED,5,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,8,VALUE_UNDEFINED,VALUE_UNDEFINED},
    {VALUE_UNDEFINED,7,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,2,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED},
    {VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,1,VALUE_UNDEFINED,VALUE_UNDEFINED,3,VALUE_UNDEFINED,VALUE_UNDEFINED},
    {VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,7,VALUE_UNDEFINED,VALUE_UNDEFINED},
    {1,VALUE_UNDEFINED,VALUE_UNDEFINED,6,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED},
    {5,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,8,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED,VALUE_UNDEFINED}
};

void readQ(int num) {
    printf("Enter every number of Q%d from left top to right bottom. Use `0` if on no initial value:\n", num + 1);
    for (int i = 0; i < 9; i++) {
        scanf("%d", &sudoku[num][i]);
    }
}

int calculateQuadrat(int row, int col) {
    return (row / 3) * 3 + col / 3;
}

int calculateField(int row, int col) {
    return (row % 3) * 3 + col % 3;
}

int calculateRow(int q, int f) {
    return (q / 3) * 3 + (f / 3);
}

int calculateCol(int q, int f) {
    return (q % 3) * 3 + (f % 3);
}

void printDumpSudoku() {
    for (int row = 0; row < 9; row++) {
        if (row % 3 == 0) {
            printf("+-------+-------+-------+\n");
        }
        for (int col = 0; col < 9; col++) {
            if (col % 3 == 0) {
                if (col != 0) {
                    printf(" ");
                }
                printf("|");
            }

            int q = calculateQuadrat(row, col);
            int f = calculateField(row, col);
            if (sudoku[q][f] > VALUE_UNDEFINED) {
                printf(" %d", sudoku[q][f]);
            } else {
                printf(" -");
            }
        }
        printf(" |\n");
    }
    printf("+-------+-------+-------+\n");
}

// checks if this value is present anywhere in the row
bool isInRow(int row, int val) {
    for (int col = 0; col < 9; col++) {
        int q = calculateQuadrat(row, col);
        int f = calculateField(row, col);

        if (sudoku[q][f] == val) {
            return true;
        }
    }

    return false;
}

// checks if this value is present anywhere in the col
bool isInCol(int col, int val) {
    for (int row = 0; row < 9; row++) {
        int q = calculateQuadrat(row, col);
        int f = calculateField(row, col);

        if (sudoku[q][f] == val) {
            return true;
        }
    }

    return false;
}

// special version of isInRow where it checks if the value
// has to be in the row in special quadrat except the one
// we are currently looking at
bool isOnlyInOneRowQuadrat(int notThisQuadrat, int row, int val) {
    int initQ = calculateQuadrat(row, 0);

    for (int q = initQ; q < initQ + 3; q++) {
        if (q == notThisQuadrat) {
            continue;
        }

        bool skipQuadrat = false;
        bool possibleRowFound = false;
        for (int f = 0; f < 9 && !skipQuadrat; f++) {
            int r = calculateRow(q, f);
            int c = calculateCol(q, f);

            if (sudoku[q][f] == val) {
                if (r == row) {
                    return true;
                } else {
                    skipQuadrat = true;
                    continue;
                }
            } else if (sudoku[q][f] <= VALUE_UNDEFINED && !isInRow(r, val) && !isInCol(c, val)) {
                if (r != row) {
                    return false;
                } else {
                    possibleRowFound = true;
                }
            } else {
                // field is either already set to another value or value is present in current row or col
                // either way, this field is not a possible option for the value
            }
        }

        if (!skipQuadrat && possibleRowFound) {
            // we found a possible field in row which may be filled with val
            // and we didn't hit any abort condition for current quadrat
            return true;
        }
    }

    // we didn't found a possible field in row and we didn't hit any
    // abort condition. This is may happen if val is already set in bot
    // quadrats but not in searched row
    return false;
}

// special version of isInCol where it checks if the value
// has to be in the col in special quadrat except the one
// we are currently looking at
bool isOnlyInOneColQuadrat(int notThisQuadrat, int col, int val) {
    int initQ = calculateQuadrat(0, col);

    for (int q = initQ; q <= initQ + 6; q += 3) {
        if (q == notThisQuadrat) {
            continue;
        }

        bool skipQuadrat = false;
        bool possibleColFound = false;
        for (int f = 0; f < 9 && !skipQuadrat; f++) {
            int r = calculateRow(q, f);
            int c = calculateCol(q, f);

            if (sudoku[q][f] == val) {
                if (c == col) {
                    return true;
                } else {
                    skipQuadrat = true;
                    continue;
                }
            } else if (sudoku[q][f] <= VALUE_UNDEFINED && !isInRow(r, val) && !isInCol(c, val)) {
                if (c != col) {
                    return false;
                } else {
                    possibleColFound = true;
                }
            } else {
                // field is either already set to another value or value is present in current row or col
                // either way, this field is not a possible option for the value
            }
        }

        if (!skipQuadrat && possibleColFound) {
            // we found a possible field in row which may be filled with val
            // and we didn't hit any abort condition for current quadrat
            return true;
        }
    }

    // we didn't found a possible field in row and we didn't hit any
    // abort condition. This is may happen if val is already set in bot
    // quadrats but not in searched row
    return false;
}

// checks if this value is present anywhere in the quadrat
bool isInQuadrat(int q, int val) {
    for (int f = 0; f < 9; f++) {
        if (sudoku[q][f] == val) {
            return true;
        }
    }

    return false;
}

void setValue(int q, int f, int val) {
    sudoku[q][f] = val;
    printf("=> setting %d in Q %d; F %d\n", val, q, f);
    //printDumpSudoku();
}

bool checkSolution() {
    bool foundError = false;

    for (int val = 1; val <= 9; val++) {
        // check for val every quadrat
        for (int q = 0; q < 9; q++) {
            if (!isInQuadrat(q, val)) {
                foundError = true;
                fprintf(stderr, "Value %d not found in Q %d\n", val, q);
            }
        }

        // check for val in every row
        for (int r = 0; r < 9; r++) {
            if (!isInRow(r, val)) {
                foundError = true;
                fprintf(stderr, "Value %d not found in row %d\n", val, r);
            }
        }

        // check for val in every col
        for (int c = 0; c < 9; c++) {
            if (!isInCol(c, val)) {
                foundError = true;
                fprintf(stderr, "Value %d not found in col %d\n", val, c);
            }
        }
    }

    return !foundError;
}

int main() {
    printDumpSudoku();
    bool somethingChanged;
    do {
        somethingChanged = false;
        for (int q = 0; q < 9; q++) {
            int possbileVal[9] = {
                VALUE_UNDEFINED, VALUE_UNDEFINED, VALUE_UNDEFINED,
                VALUE_UNDEFINED, VALUE_UNDEFINED, VALUE_UNDEFINED,
                VALUE_UNDEFINED, VALUE_UNDEFINED, VALUE_UNDEFINED
            };

            for (int val = 1; val <= 9; val++) {
                if (isInQuadrat(q, val)) {
                    continue;
                }

                int possibleField = FIELD_UNDEFINED;
                for (int f = 0; f < 9; f++) {
                    int row = calculateRow(q, f);
                    int col = calculateCol(q, f);

                    // look for val in every row and col
                    // cache evaluation of isInRow and isInCol
                    if (sudoku[q][f] <= VALUE_UNDEFINED
                            && !(isInRow(row, val) || isOnlyInOneRowQuadrat(q, row, val))
                            && !(isInCol(col, val) || isOnlyInOneColQuadrat(q, col, val))) {
                            // && !isInRow(row, val)
                            // && !isInCol(col, val)) {
                        if (possibleField == FIELD_UNDEFINED) {
                            possibleField = f;
                        } else {
                            possibleField = FIELD_MULTIPLE;
                        }

                        if (possbileVal[f] == VALUE_UNDEFINED) {
                            possbileVal[f] = val;
                        } else if (possbileVal[f] > VALUE_UNDEFINED) {
                            possbileVal[f] = VALUE_MULTIPLE;
                        } else {
                            // already set to multiple or any other meta information
                        }
                    }
                }

                // found possible field? set val
                if (possibleField > FIELD_UNDEFINED) {
                    setValue(q, possibleField, val);
                    somethingChanged = true;
                }
            }

            // check if only one field is left undefined -> hast to be the one special value
            for (int f = 0; f < 9; f++) {
                // keep in mind that sudoku array might have changed since evaluation
                // -> ignore already set values
                if (sudoku[q][f] > VALUE_UNDEFINED) {
                    continue;
                }

                if (possbileVal[f] > VALUE_UNDEFINED) {
                    setValue(q, f, possbileVal[f]);
                    somethingChanged = true;
                } else {
                    // set to undefined, multiple or any other meta information
                }
            }
        }
    } while (somethingChanged);

    printDumpSudoku();

    checkSolution();
}