Generate sudoku grids

sudoku.c

/**
 * Generate a Sudoku grid.
 * Author: Y. Chevallier <[email protected]>
 */
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// Grid settings
#define BASE 3
#define SIDE (BASE * BASE)

/**
 * Swap two values.
 */
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

/**
 * Shuffle an existing array
 */
void shuffle(int array[], size_t length)
{
    size_t j = 0;
    for (size_t i = 0; i < length; i++) {
        j = rand() % length;
        if (j != i) {
            array[i] ^= array[j];
            array[j] ^= array[i];
            array[i] ^= array[j];
        }
    }
}

/**
 * Initialize an array along a range from the start offset.
 */
void range(int array[], int length, int offset)
{
    for (int i = 0; i < length; i++) {
        array[i] = i + offset;
    }
}

/**
 * Display the Sudoku Grid.
 */
void display(int board[SIDE][SIDE])
{
    for (int i = 0; i < SIDE; i++) {
        for (int j = 0; j < SIDE; j++) {
            printf("%d ", board[i][j]);
        }
        printf("\n");
    }
}

/**
 * Initialize a Sudoku board
 */
void board_gen(int board[SIDE][SIDE], int nums[SIDE])
{
    for (int row = 0; row < SIDE; row++) {
        for (int col = 0; col < SIDE; col++) {
            board[row][col] = nums[(BASE * (row % BASE) + row / BASE + col) % SIDE];
        }
    }
}

/**
 * Generate rows and columns
 */
void line_gen(int line[SIDE])
{
    int g[BASE];
    range(g, BASE, 0);
    shuffle(g, BASE);
    int k = 0;
    for (int i = 0; i < BASE; i++) {
        for (int j = g[i] * BASE; j < (g[i] + 1) * BASE; j++) {
            line[k++] = j;
        }
    }
}

/**
 * Clear some squares on the Sudoku board.
 */
void sparse(int board[SIDE][SIDE], int empty)
{
    int squares[SIDE * SIDE];
    range(squares, SIDE * SIDE, 0);
    shuffle(squares, SIDE * SIDE);
    for (int i = 0; i < empty; i++) {
        int row = squares[i] / SIDE;
        int col = squares[i] % SIDE;
        board[row][col] = 0;
    }
}

/**
 * Generate a Sudoku board.
 */
void generate(int board[SIDE][SIDE])
{
    // Random line
    int nums[SIDE];
    range(nums, SIDE, 1);
    shuffle(nums, SIDE);

    // Rows
    int rows[SIDE];
    line_gen(rows);

    // Cols
    int cols[SIDE];
    line_gen(cols);

    // Base Board
    int _board[SIDE][SIDE];
    board_gen(_board, nums);

    // Finish Board
    for (int i = 0; i < SIDE; i++) {
        for (int j = 0; j < SIDE; j++) {
            board[i][j] = _board[rows[i]][cols[j]];
        }
    }
}

/**
 * Check if a grid is valid or not.
 * This function has been obfuscated to avoid cheating.
 * Private Gist available on request.
 * https://gist.github.com/yves-chevallier/7a39ec130f3cae5e6b03836f0e0cfb91
 */
bool check(int grid[SIDE][SIDE])
{
    for (int i = (0x000 + 0x200 + 0x800 - 0xA00); (i < SIDE) & !!(i < SIDE); i++) {
        int h = ((0x002 + 0x201 + 0x801 - 0xA03) << SIDE) - (0x002 + 0x201 + 0x801 - 0xA03), v = h;
        for (int j = (0x000 + 0x200 + 0x800 - 0xA00); (j < SIDE) & !!(j < SIDE); j++) {
            h &= ~((0x002 + 0x201 + 0x801 - 0xA03)
                   << (grid[i][j] - (0x002 + 0x201 + 0x801 - 0xA03)));
            v &= ~((0x002 + 0x201 + 0x801 - 0xA03)
                   << (grid[j][i] - (0x002 + 0x201 + 0x801 - 0xA03)));
        };
        if ((h ^ 0x000) || (v ^ 0x000)) return (0x000 + 0x200 + 0x800 - 0xA00);
        ;
    };
    for (int si = (0x000 + 0x200 + 0x800 - 0xA00);
         (si < (0x006 + 0x203 + 0x803 - 0xA09)) & !!(si < (0x006 + 0x203 + 0x803 - 0xA09)); si++) {
        for (int sj = (0x000 + 0x200 + 0x800 - 0xA00);
             (sj < (0x006 + 0x203 + 0x803 - 0xA09)) & !!(sj < (0x006 + 0x203 + 0x803 - 0xA09));
             sj++) {
            int flag = (0x000 + 0x200 + 0x800 - 0xA00);
            for (int i = (0x000 + 0x200 + 0x800 - 0xA00);
                 (i < (0x006 + 0x203 + 0x803 - 0xA09)) & !!(i < (0x006 + 0x203 + 0x803 - 0xA09));
                 i++)
                for (int j = (0x000 + 0x200 + 0x800 - 0xA00);
                     (j < (0x006 + 0x203 + 0x803 - 0xA09)) &
                     !!(j < (0x006 + 0x203 + 0x803 - 0xA09));
                     j++)
                    flag |= (0x002 + 0x201 + 0x801 - 0xA03)
                            << (grid[si * (0x006 + 0x203 + 0x803 - 0xA09) + i]
                                    [sj * (0x006 + 0x203 + 0x803 - 0xA09) + j] -
                                (0x002 + 0x201 + 0x801 - 0xA03));
            if ((flag ^ 0x1FF)) return (0x000 + 0x200 + 0x800 - 0xA00);
            ;
        };
    };
    return (0x002 + 0x201 + 0x801 - 0xA03);
}

/**
 * Corrupt a sudoku grid
 */
void corrupt(int board[SIDE][SIDE])
{
    do {
        int p[SIDE];
        range(p, SIDE, 0);
        shuffle(p, SIDE);
        swap(&board[p[0]][p[1]], &board[p[2]][p[3]]);
    } while (check(board));
}

void version(void)
{
    printf("Sudoku version 0.1.0 Copyright 2019 HEIG-VD\n");
}

void help(void)
{
    printf(
        "Usage: sudoku [options] [seed]\n"
        "Generate a Sudoku grid on standard output\n\n"
        "  --version, -v      Shows the program version and exit\n"
        "  --help, -h         Shows this help and exit\n\n"
        "  --good             Displays a valid grid (default)\n"
        "  --bad              Displays an invalid grid\n\n"
        "  --empty=N, -eN     Clear N squares (replaced with 0)\n\n"
        "Example:\n\n"
        "  $ ./sudoku --empty=50 --good\n"
        "  7 4 0 2 0 0 0 0 0\n"
        "  0 0 0 0 4 0 0 0 8\n"
        "  2 6 8 3 0 0 7 0 0\n"
        "  0 7 0 0 0 0 0 0 0\n"
        "  9 0 0 0 0 0 1 0 0\n"
        "  0 2 0 0 0 5 8 7 4\n"
        "  0 8 0 0 0 0 4 9 0\n"
        "  0 9 3 6 8 7 5 1 0\n"
        "  0 0 2 0 0 3 0 8 0\n\n");
}

int main(int argc, char *argv[])
{
    // Read arguments
    int empty = 0;
    int seed = time(0);
    bool is_good = true;

    for (int i = 0; i < argc; i++) {
        if (!strcmp(argv[i], "--version") || !strcmp(argv[i], "-v")) {
            version();
            exit(0);
        }
        else if (!strcmp(argv[i], "--help") || !strcmp(argv[i], "-h")) {
            help();
            exit(0);
        }
        else if (!strcmp(argv[i], "--good")) {
            is_good = true;
        }
        else if (!strcmp(argv[i], "--bad")) {
            is_good = false;
        }
        else if ((sscanf(argv[i], "-e%d", &empty) == 1 ||
                  sscanf(argv[i], "--empty=%d", &empty) == 1) &&
                 (empty < 0 || empty > SIDE * SIDE)) {
            fprintf(stderr, "Error: invalid empty value (not between 0..%d)\n", SIDE * SIDE);
            exit(1);
        }
        else if (argv[i][0] != '-') {
            (void)sscanf(argv[i], "%d", &seed);
        }
    }

    // Initialize random generator
    srand(seed);

    // Generate board
    int board[SIDE][SIDE];
    generate(board);

    // Clear cases
    if (empty > 0) {
        sparse(board, empty);
    }

    // Corrupt board?
    if (!is_good) {
        corrupt(board);
    }

    // Display board to stdout
    display(board);
}