/*
    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>

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 init()
{
    for (int i = 0; i < 81; i++) {
        possible[i] = 0x1FFu;
        selected[i] = 0;
    }
}

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);
            }
        }
}

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;
}

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()
{
    srand(time(0));
    int tries = 0;
    do {
        init();
        tries++;
        addNumbers();
    } while (!checkValid());
    for (int i = 0; i < 81; i++)
        printf("%i",selected[i]);
    printf("\n");
//    prettyPrint();
//    printf("tried: %i times\n", tries);
//    printf("%s\n", checkValid()?"valid":"invalid");

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

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