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

#define ORDER 4
#define MSUM ((ORDER * (ORDER * ORDER + 1)) >> 1)

typedef unsigned char byte;
typedef enum boolean { false = 0, true } boolean;

static byte board[ORDER][ORDER];
static byte used[ORDER * ORDER + 1];

#ifdef SPINNER
static char spinner[] = "|/-\\";
static byte spin;
#endif

/*
 * a new number n is acceptable if it's not already used
 * and if the sum doesn't overflow the magic sum MSUM
 */
static boolean acceptable_n(byte row, byte col, byte n)
{
    byte        i;
    unsigned int sum1, sum2, d1sum, d2sum;

    if (used[n])
        return false;

    sum1 = sum2 = n;
    for (i = 0; i < ORDER; ++i) {
        sum1 += board[row][i];
        sum2 += board[i][col];
    }
    if (col == ORDER - 1) {
        if (sum1 != MSUM || sum2 > MSUM)
            return false;
    } else {
        if (sum1 > MSUM || sum2 > MSUM)
            return false;
    }

    d1sum = d2sum = 0;
    for (i = 0; i < ORDER; ++i) {
        d1sum += board[i][i];
        d2sum += board[ORDER - 1 - i][i];
    }

    if (d1sum > MSUM || d2sum > MSUM)
        return false;

    return true;
}

/*
 * a solution is one of which all the sums are exactly
 * the magic sum MSUM
 */
static boolean all_ok(void)
{
    byte        row, col, i;
    unsigned int sum, d1sum, d2sum;

    for (row = 0; row < ORDER; ++row) {
        sum = 0;
        for (col = 0; col < ORDER; ++col)
            sum += board[row][col];
        if (sum != MSUM)
            return false;
    }

    for (col = 0; col < ORDER; ++col) {
        sum = 0;
        for (row = 0; row < ORDER; ++row)
            sum += board[row][col];
        if (sum != MSUM)
            return false;
    }

    d1sum = d2sum = 0;
    for (i = 0; i < ORDER; ++i) {
        d1sum += board[i][i];
        d2sum += board[ORDER - 1 - i][i];
    }

    if (d1sum != MSUM || d2sum != MSUM)
        return false;
    return true;
}

static void print_board(void)
{
    byte        row, col;

    for (row = 0; row < ORDER; ++row) {
        for (col = 0; col < ORDER; ++col) {
            printf("%4d", board[row][col]);
        }
        putchar('\n');
    }
}

static boolean solve(byte row, byte col)
{
    byte        n;

    /* we found a solution */
    if (row == ORDER && all_ok())
        return true;

    /*
     * no solution yet, check for an n which fits
     * this position
     */
    for (n = 1; n < ORDER * ORDER + 1; ++n) {
        /* only acceptable n's are tried for speed */
        if (acceptable_n(row, col, n)) {
            board[row][col] = n;
            used[n] = true;
            if (col == ORDER - 1) {
                if (solve(row + 1, 0))
                    return true;
            } else {
                if (solve(row, col + 1))
                    return true;
            }
            /* backtrack: try this one again if above fails */
            board[row][col] = 0;
            used[n] = false;
#ifdef SPINNER
            printf("%c\r", spinner[spin++]);
            if (spin == 4)
                spin = 0;
#endif
        }
    }

    return false;
}

static void reset_board(void)
{
    byte        row, col, i;

    for (row = 0; row < ORDER; ++row)
        for (col = 0; col < ORDER; ++col)
            board[row][col] = 0;

    for (i = 0; i < ORDER * ORDER + 1; ++i)
        used[i] = false;
}
int main(void)
{                               /*int argc, char **argv) */
#if 0
    if (argc != 2) {
        fprintf(stderr, "usage: magic order\n");
        return 1;
    }
#endif

    reset_board();
    if (solve(0, 0))
        print_board();
    else
        printf("There were no solutions for your board\n");

    return 0;
}