kakuro.c

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

typedef struct constraint {
    struct constraint *next;
    int sum;
    unsigned count;
    unsigned index[];
} constraint;

typedef struct kakuro {
    unsigned width;
    unsigned height;
    constraint *constraints;
    int cell[];
} kakuro;

static kakuro *
kakuro_load(FILE *in)
{
    char line[1024];
    unsigned width, height;
    fgets(line, sizeof(line), in);
    sscanf(line, "%u %u", &width, &height);
    kakuro *k = malloc(sizeof(*k) + sizeof(k->cell[0]) * width * height);
    k->width = width;
    k->height = height;
    k->constraints = NULL;
    for (unsigned i = 0; i < width * height; i++)
        k->cell[i] = -1;
    /* Read in each constraint. */
    while (fgets(line, sizeof(line), in)) {
        unsigned count = 0;
        for (char *p = line; *p; p++)
            if (*p == ' ')
                count++;
        constraint *c = malloc(sizeof(*c) + sizeof(c->index[0]) * count);
        c->next = k->constraints;
        c->count = count;
        char *p;
        c->sum = strtol(line, &p, 10);
        for (unsigned i = 0; i < count; i++) {
            unsigned x = p[1] - 'A';
            unsigned y = strtol(p + 2, &p, 10) - 1;
            unsigned index = y * width + x;
            c->index[i] = index;
            k->cell[index] = 0;
        }
        k->constraints = c;
    }
    return k;
}

static void
kakuro_free(kakuro *k)
{
    while (k->constraints) {
        constraint *dead = k->constraints;
        k->constraints = dead->next;
        free(dead);
    }
    free(k);
}

static bool
kakuro_is_valid(const kakuro *k)
{
    for (constraint *c = k->constraints; c; c = c->next) {
        int sum = 0;
        int set[10] = {1};
        for (unsigned j = 0; j < c->count; j++) {
            int value = k->cell[c->index[j]];
            if (set[value])
                return false;
            set[value] = 1;
            sum += value;
        }
        if (sum != c->sum)
            return false;
    }
    return true;
}

static void
kakuro_solve(kakuro *k, unsigned cell, void(*cb)(kakuro *, void *), void *arg)
{
    if (cell >= k->width * k->height) {
        if (kakuro_is_valid(k))
            cb(k, arg);
    } else if (k->cell[cell] < 0) {
        kakuro_solve(k, cell + 1, cb, arg); // skip
    } else {
        for (int i = 1; i < 9; i++) {
            k->cell[cell] = i;
            kakuro_solve(k, cell + 1, cb, arg);
        }
        k->cell[cell] = 0;
    }
}

static void
kakuro_draw(const kakuro *k, FILE *out)
{
    /* Initialize grid */
    int grid[k->width + 1][k->height + 1][2];
    for (unsigned y = 0; y < k->height + 1; y++)
        for (unsigned x = 0; x < k->width + 1; x++)
            grid[x][y][0] = grid[x][y][1] = -1;
    /* Fill in constraints */
    for (const constraint *c = k->constraints; c; c = c->next) {
        for (unsigned i = 0; i < c->count; i++) {
            unsigned x = c->index[i] % k->width;
            unsigned y = c->index[i] / k->width;
            grid[x + 1][y + 1][0] = 0;
            grid[x + 1][y + 1][1] = 0;
        }
        unsigned x0 = c->index[0] % k->width;
        unsigned y0 = c->index[0] / k->width;
        unsigned x1 = c->index[1] % k->width;
        if (x0 == x1)
            grid[x0 + 1][y0][1] = c->sum;
        else
            grid[x0][y0 + 1][0] = c->sum;
    }

    unsigned cellsize = 100;
    fprintf(out, "<svg width='%u' height='%u'>\n",
            (k->width + 1) * cellsize, (k->height + 1) * cellsize);
    /* Place triangles/squares */
    for (unsigned y = 0; y < k->height + 1; y++)
        for (unsigned x = 0; x < k->width + 1; x++) {
            if (grid[x][y][0] == 0 && grid[x][y][1] == 0) {
                fprintf(out, "<rect x='%u' y='%u' width='%u' height='%u' "
                        "style='fill: white; stroke: black'/>\n",
                        x * cellsize, y * cellsize,
                        cellsize, cellsize);
            } else {
                for (int s = 0; s < 2; s++) {
                    const char *style;
                    if (grid[x][y][s] == -1) {
                        style = "fill: black; stroke: black";
                    } else {
                        style = "fill: white; stroke: black";
                    }
                    fprintf(out,
                            "<polygon points='%u,%u %u,%u %u,%u' "
                            "style='%s'/>\n",
                            (x + 0) * cellsize, (y + 0) * cellsize,
                            (x + 1 - s) * cellsize, (y + s * 1) * cellsize,
                            (x + 1) * cellsize, (y + 1) * cellsize,
                            style);
                }
            }
        }
    /* Place text labels */
    for (unsigned y = 0; y < k->height + 1; y++)
        for (unsigned x = 0; x < k->width + 1; x++) {
            unsigned i = (y - 1) * k->width + (x - 1);
            if (x > 0 && y > 0 && k->cell[i] > 0) {
                fprintf(out, "<text x='%u' y='%u' "
                        "style='font-size: %u; "
                               "fill: darkred; "
                               "font-family: sans-serif' "
                        "text-anchor='middle'>%u</text>\n",
                        x * cellsize + cellsize / 2,
                        (y + 1) * cellsize - cellsize / 4,
                        2 * cellsize / 3,
                        k->cell[i]);
            }
            for (int s = 0; s < 2; s++) {
                if (grid[x][y][s] > 0) {
                    fprintf(out, "<text x='%u' y='%u' "
                            "style='font-size: %upx; font-family: sans-serif' "
                            "text-anchor='%s'>%u</text>",
                            x * cellsize +
                              (s ? (cellsize / 10) : cellsize - cellsize / 10),
                            (y + 1) * cellsize -
                              (s ? cellsize / 10 : (2 * cellsize) / 3),
                            cellsize / 3,
                            s ? "start" : "end",
                            grid[x][y][s]);
                }
            }
        }
    fprintf(out, "</svg>\n");
}

int
main(void)
{
    kakuro *k = kakuro_load(stdin);
    kakuro_solve(k, 0, (void *)kakuro_draw, stdout);
    kakuro_free(k);
    return 0;
}