#include <stdio.h>

static int b[9][9] = {
/*
{0,5,9, 0,0,0, 0,0,0},
{0,0,0, 6,3,0, 0,0,0},
{8,4,0, 0,0,7, 2,0,0},
{0,0,5, 7,0,0, 0,4,3},
{0,0,0, 0,0,0, 0,0,0},
{6,1,0, 0,0,2, 8,0,0},
{0,0,1, 8,0,0, 0,9,6},
{0,0,0, 0,5,9, 0,0,0},
{0,0,0, 0,0,0, 4,8,0},
*/
/*
{0,2,1, 0,0,0, 0,7,8},
{5,0,0, 2,0,0, 4,0,0},
{3,0,0, 0,0,1, 0,0,0},
{0,1,0, 0,0,3, 0,0,0},
{0,0,7, 0,0,0, 5,0,0},
{0,0,0, 1,0,0, 0,9,0},
{0,0,0, 4,0,0, 0,0,2},
{0,0,2, 0,0,5, 0,0,7},
{9,5,0, 0,0,0, 6,4,0},
*/

{0,0,0, 0,5,1, 8,0,0},
{0,2,0, 0,0,0, 0,5,0},
{0,0,0, 4,0,7, 6,0,3},
{0,0,9, 0,0,8, 7,0,2},
{8,0,0, 0,0,0, 0,0,9},
{3,0,1, 6,0,0, 5,0,0},
{5,0,4, 8,0,3, 0,0,0},
{0,6,0, 0,0,0, 0,1,0},
{0,0,7, 9,2,0, 0,0,0}

/*
    {0,0,6, 0,0,0, 0,0,1},
    {0,7,0, 0,6,0, 0,5,0},
    {8,0,0, 1,0,3, 2,0,0},
    {0,0,5, 0,4,0, 8,0,0},
    {0,4,0, 7,0,2, 0,9,0},
    {0,0,8, 0,1,0, 7,0,0},
    {0,0,1, 2,0,5, 0,0,3},
    {0,6,0, 0,7,0, 0,8,0},
    {2,0,0, 0,0,0, 4,0,0},
*/
};
static int *bp;
static int count;

void print_board() {
    int i, j;
    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            printf("%d ", b[i][j]);
        }
        puts("");
    }
}

int can_put(int x, int y, int v) {
    int i, j;
    for (i = 0; i < 9; i++) {
        if (v == b[y][i] || v == b[i][x]) return 0;
    }
    x = (x / 3) * 3;
    y = (y / 3) * 3;
    for (i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
            if (b[y+j][x+i] == v) return 0;
        }
    }
    return 1;
}

int solve(int d) {
    int i, x, y;

    count++;

    if (d == 0) {
        return 1;
    }
//    printf("%d\n", d);
//    print_board();

    int m = 10;
    int mx = -1, my = -1;
    for (y = 0; y < 9; y++) {
        for (x = 0; x < 9; x++) {
            int s = 0;
            if (b[y][x]) continue;
            for (i = 1; i <= 9; i++) {
                if (can_put(x, y, i)) s++;
            }
            if (m > s) {
                m = s;
                mx = x;
                my = y;
            }
        }
    }

    for (i = 1; i <= 9; i++) {
        if (can_put(mx, my, i)) {
            b[my][mx] = i;
            if (solve(d-1)) return 1;
            b[my][mx] = 0;
        }
    }
    return 0;
}

int main() {
    int depth = 81;
    int i;
    int ok;

    bp = (int*)b;
    for (i = 0; i < 81; i++) {
        if (bp[i]) depth--;
    }

    printf("%d depth\n", depth);
    ok = solve(depth);
    puts("result:");
    if (ok) {
        printf("%d times\n", count);
        print_board();
    }
    else {
        printf("toke nai yo!\n");
    }

    return 0;
}