/*
  Problema 28 (Sudoku).  Escreva um programa que resolve o Sudoku:

  https://en.wikipedia.org/wiki/Sudoku

  (exemplos de execução abaixo)
 */

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

#define R   9
#define N   81  /* N = R * R */

#define LMAX 2 

#define TRUE 1
#define FALSE 0

/* With global variables, for simplicity */

int board[N];

/*
  There are R rows, R columns and R blocks.
  r[i][j] is TRUE iff row i contains integer j
  c[i][j] is TRUE iff column i contains integer j
  b[i][j] is TRUE iff block i contains integer j
 */
int r[R][R + 1]; 
int c[R][R + 1]; 
int b[R][R + 1]; 

/*  
  M[cell][0] = the row that contains cell 
  M[cell][1] = the column that contains cell 
  M[cell][2] = the block that contains cell 
 */
int M[N][3];

int T;

int verbose;

/* function prototypes */

void print_board();
void read_board();

void solve(int cell);

int should_btrack(int cell, int i);

void setupM();

/**************************************************************/

int main(int argc, char *argv[])
{
  verbose = argc > 1;

  setupM();

  read_board();
  solve(0);

  if (T == 1) 
    printf("Solucao unica\n");
  else
    printf("%d solucoes\n", T);
  
  return 0;
}

/**************************************************************/

void print_board()
{
  int i; 
  for (i = 0; i < N; i++) {
    if (board[i] == 0) printf(". ");
    else printf("%d ", board[i]);
    if (i % R == R - 1)
      printf("\n");
  }
  printf("\n");
}

void read_board()
{
  int i;
  for (i = 0; i < N; i++) {
    char t[LMAX];
    scanf("%s", t);
    if (strcmp(t, ".") == 0) board[i] = 0;
    else {
      int u = atoi(t);
      if (r[M[i][0]][u]
	  || c[M[i][1]][u]
	  || b[M[i][2]][u]) {
	printf("Entrada invalida\n");
	exit(0);
      }
      board[i] = u;
      r[M[i][0]][u] = TRUE;
      c[M[i][1]][u] = TRUE;
      b[M[i][2]][u] = TRUE;
    }
  }
}

void solve(int cell)
{
  int i;
  if (cell == N) {
    T++;
    if (verbose) print_board();
    return;
  }
  if (board[cell] != 0) {
    solve(cell + 1);
    return;
  }
	
  for (i = 1; i <= R; i++)
    if (!should_btrack(cell, i)) {
      board[cell] = i;
      r[M[cell][0]][i] = TRUE;
      c[M[cell][1]][i] = TRUE;
      b[M[cell][2]][i] = TRUE;
      solve(cell + 1);
      board[cell] = 0;
      r[M[cell][0]][i] = FALSE; 
      c[M[cell][1]][i] = FALSE;
      b[M[cell][2]][i] = FALSE;
    }
}

int should_btrack(int cell, int i)
{
  return 
    r[M[cell][0]][i] ||
    c[M[cell][1]][i] ||
    b[M[cell][2]][i];
}

void setupM()
{
  int i;
  for (i = 0; i < N; i++) {
    int a = i / R;
    int b = i % R;
    M[i][0] = a;
    M[i][1] = b;
    M[i][2] = b / 3 + 3 * (a / 3);
  }
}

/*
$ cat DATA/in0.txt
7 . 8 . . . 3 . .
. . . 2 . 1 . . .
5 . . . . . . . .
. 4 . . . . . 2 6
3 . . . 8 . . . .
. . . 1 . . . 9 .
. 9 . 6 . . . . 4
. . . . 7 . 5 . .
. . . . . . . . .
$ p28 < DATA/in0.txt
Solucao unica
$ p28 . < DATA/in0.txt
7 2 8 9 4 6 3 1 5 
9 3 4 2 5 1 6 7 8 
5 1 6 7 3 8 2 4 9 
1 4 7 5 9 3 8 2 6 
3 6 9 4 8 2 1 5 7 
8 5 2 1 6 7 4 9 3 
2 9 3 6 1 5 7 8 4 
4 8 1 3 7 9 5 6 2 
6 7 5 8 2 4 9 3 1 

Solucao unica
$ p28 < DATA/in1.txt
Solucao unica
$ p28 < DATA/in2.txt
10 solucoes
$ p28 . < DATA/in2.txt > in2.out
$ head -n25 in2.out
7 3 8 2 6 1 9 4 5 
6 2 4 9 5 3 7 1 8 
9 5 1 7 4 8 3 2 6 
5 1 9 6 8 4 2 3 7 
2 6 3 1 9 7 5 8 4 
8 4 7 5 3 2 6 9 1 
3 8 2 4 7 5 1 6 9 
4 9 5 3 1 6 8 7 2 
1 7 6 8 2 9 4 5 3 

8 3 9 2 6 1 4 7 5 
6 2 4 7 5 3 8 1 9 
5 7 1 9 4 8 3 2 6 
2 5 8 6 9 4 1 3 7 
9 6 3 1 8 7 5 4 2 
1 4 7 5 3 2 6 9 8 
3 8 2 4 7 5 9 6 1 
7 9 5 3 1 6 2 8 4 
4 1 6 8 2 9 7 5 3 

8 3 9 2 6 1 4 7 5 
6 2 4 7 5 3 8 1 9 
5 7 1 9 4 8 3 2 6 
2 5 8 6 9 4 1 3 7 
9 6 3 1 8 7 5 4 2 
$ p28 < DATA/in3.txt
Entrada invalida
$ 
 */