/*
    Sudoku Puzzle generator
    (C) Copyright 2007
    John Ryland <jryland@invertedlogic.com>

    ALL RIGHTS RESERVED
*/
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <assert.h>
#include <string.h>

int boxTab[81] = {
    1,1,1,2,2,2,3,3,3,
    1,1,1,2,2,2,3,3,3,
    1,1,1,2,2,2,3,3,3,
    4,4,4,5,5,5,6,6,6,
    4,4,4,5,5,5,6,6,6,
    4,4,4,5,5,5,6,6,6,
    7,7,7,8,8,8,9,9,9,
    7,7,7,8,8,8,9,9,9,
    7,7,7,8,8,8,9,9,9
};

unsigned int selected[81];
unsigned int possible[81];

void prettyPrint()
{
    for (int i = 0; i < 81; i++) {
        if (i % 27 == 0)
            printf("-------------\n");
        if (i % 3 == 0)
            printf("|");
        printf("%i", selected[i]);
        if (i % 9 == 8)
            printf("|\n");
    }
    printf("-------------\n");
}

int onlyOne(int val)
{
    for (unsigned int j = 0; j < 9; j++)
        if (val == (0x1u << j))
            return j + 1;
    return 0;
}

void addValue(int pos, unsigned int val)
{
    unsigned int mask = 0x1u << (val-1);
    if ( (possible[pos] & mask) == 0 )
        return;
    possible[pos] = ~mask;
    selected[pos] = val;
    for (int i = 0; i < 81; i++)
        if ( !selected[i] ) {
            if ( pos/9 == i/9 || pos%9 == i%9 || boxTab[pos] == boxTab[i] ) {
                possible[i] &= ~mask;
                for (unsigned int j = 0; j < 9; j++)
                    if (possible[i] == (0x1u << j))
                        addValue(i, j + 1);
            }
        }
}

/*
// Broken - seems it can't work to do it this way
void init()
{
    for (int i = 0; i < 81; i++) {
        possible[i] = 0x1FFu;
        selected[i] = 0;
    }

    for (int pos = 0; pos < 81; pos++) {
        assert(possible[pos]);
	unsigned int possibles = possible[pos];

	unsigned int bitCount = 0;
	unsigned int vals[10] = { 0 };
	for (unsigned int bit = 0; possibles; bit++, possibles >>= 1) {
		if (possibles & 1) {
			vals[bitCount] = bit + 1;
			bitCount++;
		}
	}
        assert(bitCount >= 1);
        assert(bitCount <= 9);
	bitCount--;
	unsigned int off = 0;
	if (bitCount)
		off = rand() % (bitCount+1);
        assert(off >= 0);
        assert(off <= 8);
	unsigned int val = vals[off];
	//unsigned int val = (bitCount-1) ? vals[rand() % (bitCount - 1)] : vals[0];
        assert(val >= 1);
        assert(val <= 9);
        unsigned int mask = 0x1u << (val-1);
        assert(mask);
        assert(possible[pos] & mask);
        //mask = ~mask;
        selected[pos] = val;
        if (pos != 80)
            for (int i = pos + 1; i < 81; i++)
                if ( pos/9 == i/9 || pos%9 == i%9 || boxTab[pos] == boxTab[i] ) {
                    assert(possible[i]);
                    //assert(possible[i] & mask);
                    if (!(possible[i] & mask)) {
			printf("pos: %u  i: %u  mask: %u\n", pos, i, mask);
                    }
                    possible[i] &= ~mask;
                    assert(possible[i]);
		    for (unsigned int j = 0; j < 9; j++)
		        if (possible[i] == (0x1u << j)) {
			    for (int i2 = pos + 1; i2 < 81; i2++)
				if ( i/9 == i2/9 || pos%9 == i2%9 || boxTab[i] == boxTab[i2] ) {
				    possible[i2] &= ~(1<<j);
				    assert(possible[i2]);
				}
			}
		}
    }
}
*/

bool addNumbers()
{
    for (int i = 0; i < 81; i++) {
        if ( !possible[i] )
            return false;
        while ( selected[i] == 0 )
            addValue(i, (rand() % 9) + 1);
    }
    return true;
}

void init()
{
    for (int i = 0; i < 81; i++) {
        possible[i] = 0x1FFu;
        selected[i] = 0;
    }
    addNumbers();
}

bool checkValid()
{
    for (int j = 0; j < 81; j++)
        for (int i = 0; i < 81; i++)
            if (i != j && selected[i] && selected[j])
                if ( j/9 == i/9 || j%9 == i%9 || boxTab[j] == boxTab[i] )
                    if ( selected[i] == selected[j] )
                        return false;
    return true;
}

unsigned int puzzleVals[81];
unsigned int puzzleMask[81];

void solverAddValue(int pos, unsigned int val)
{
    unsigned int mask = 0x1u << (val-1);
    if ( (puzzleMask[pos] & mask) == 0 )
        return;
    puzzleMask[pos] = ~mask;
    puzzleVals[pos] = val;
    for (int i = 0; i < 81; i++)
        if ( !puzzleVals[i] ) {
            if ( pos/9 == i/9 || pos%9 == i%9 || boxTab[pos] == boxTab[i] ) {
                puzzleMask[i] &= ~mask;
                for (unsigned int j = 0; j < 9; j++)
                    if (puzzleMask[i] == (0x1u << j))
                        solverAddValue(i, j + 1);
            }
        }
}

bool isSolved()
{
    for (int j = 0; j < 81; j++)
        for (int i = 0; i < 81; i++)
            if (i != j)// && puzzleVals[i] && puzzleVals[j])
                if ( j/9 == i/9 || j%9 == i%9 || boxTab[j] == boxTab[i] )
                    if ( puzzleVals[i] == puzzleVals[j] )
                        return false;
    return true;
}

bool canSolve()
{
    for (int i = 0; i < 81; i++) {
        puzzleVals[i] = selected[i];
        puzzleMask[i] = 0x1FFu;
    }
    for (int i = 0; i < 81; i++) {
        if ( puzzleVals[i] ) {
            for (int j = 0; j < 81; j++)
                if ( !puzzleVals[j] ) {
                    if ( j/9 == i/9 || j%9 == i%9 || boxTab[j] == boxTab[i] )
                        puzzleMask[j] &= ~(1 << (puzzleVals[i] - 1));
                } else {
                    puzzleMask[j] = ~(1 << (puzzleVals[i] - 1)); // 0;
                }
        }
    }
    for (int i = 0; i < 81; i++)
        if ( !puzzleVals[i] ) {
            for (unsigned int j = 0; j < 9; j++)
                if (puzzleMask[i] == (0x1u << j))
                    solverAddValue(i, j + 1);
        }
    return isSolved();
}

bool canRemoveCell(int i)
{
    int oldSelected = selected[i];
    selected[i] = 0;
    bool ret = canSolve();
    selected[i] = oldSelected;
    return ret;
}

int removeZigZag[81] = {
    41,51,31,33,49,81, 1,61,21,
    63,19,79, 3,71,11, 9,73,25,
    57,55,27,75, 7,65,17,54,78,
     4,28,48,24,34,58,36,76,52,
    60, 6,46,22,30,44,68,38,14,
    12,20,62,70,42,50,40,32,45,
    77,37, 5,13,29,69,53,15,47,
    67,35,16,56,66,26,43,59,39,
    23,72,80,10, 2, 8,64,18,74
};

int main(int argc, char* argv[])
{
    unsigned int type = 0;        // 0 - random, 1 - daily,  2 - specific seed
    unsigned int difficulty = 0;  // 0 - easy,   1 - medium, 2 - hard, 3 - test
    unsigned int seed = time(0);

    if (argc >= 1) {
      for (int arg = 1; arg < argc; arg++) {
	const char* argStr = argv[arg];
	if (strcmp(argStr,"daily")==0)       { type = 1; seed = time(0) / (60*60*24); }
	else if (strcmp(argStr,"easy")==0)   { difficulty = 0; }
	else if (strcmp(argStr,"medium")==0) { difficulty = 1; }
	else if (strcmp(argStr,"hard")==0)   { difficulty = 2; }
	else if (strcmp(argStr,"test")==0)   { difficulty = 3; }
	else                                 { type = 2; seed = atoi(argv[arg]); }
      }
    }

    // printf("%u\n", seed);
    const char* types[3] = { "random", "daily", "specific" };
    const char* difficulties[4] = { "easy", "medium", "hard", "test" };
    printf("{\n");
    printf(" \"type\" : \"%s\",\n \"difficulty\" : \"%s\",\n \"id\" : %u,\n \"solution\" : \"",
		types[type], difficulties[difficulty], seed);

    srand(seed);
    int tries = 0;
    do {
        init();
        tries++;
    } while (!checkValid());
    for (int i = 0; i < 81; i++)
        printf("%i",selected[i]);

    printf("\",");

    printf("\n");
//    prettyPrint();
//    printf("tried: %i times\n", tries);
//    printf("%s\n", checkValid()?"valid":"invalid");

    int numRemoved = 0;
    for (int i = 0; i < 81; i++) {
        int j = removeZigZag[i] - 1;
        if (canRemoveCell(j)) {
	    numRemoved++;
            selected[j] = 0;
//            prettyPrint();

	    if (difficulty == 3 && numRemoved >= 2) // test
		break;
	    if (difficulty == 0 && numRemoved >= 40) // easy
		break;
	    if (difficulty == 1 && numRemoved >= 48) // medium
		break;
        }
    }

    printf(" \"clues\" : \"");

    for (int i = 0; i < 81; i++)
        printf("%i",selected[i]);

    printf("\"");
    printf("\n");
    printf("}\n");

    return 0;
}