////////////////////////////////////////
// SuDoKu by the Maze
// 
// algorithm by D. Wren 
// code by C. Wren 
// October 8 2005
//
// Copyright 2005 C. Wren
// All Rights Reserved
////////////////////////////////////////

#include <iostream>
#include <string>
#include <cstdlib>

typedef struct _element
{
  bool option[9];
  int freedom;
  int value;
} element;

typedef struct _square
{
  element el[9][9];
  element *sets[29][9];
  bool diagonal;
  int rules;
  int freedom;
} square;

square *make_square(bool diagonal)
{
  square *sq = new square;
  sq->diagonal = diagonal;

  for(int i=0; i<9; i++)
    for(int j=0; j<9; j++)
      for(int k=0; k<9; k++)
      {
	sq->el[i][j].option[k] = 1;
      }
  
  // rows
  int s=0;
  for(int i=0; i<9; i++)
    {
      for(int j=0; j<9; j++)
	sq->sets[s][j] = &(sq->el[i][j]);
      s++;
    }

  // columns
  for(int i=0; i<9; i++)
    {
      for(int j=0; j<9; j++)
	sq->sets[s][j] = &(sq->el[j][i]);
      s++;
    }

  // chunks 
  for(int i=0; i<9; i+=3)
    for(int j=0; j<9; j+=3)
      {
	int k=0;
	for(int di=0; di<3; di++)
	  for(int dj=0; dj<3; dj++)
	    sq->sets[s][k++] = &(sq->el[i+di][j+dj]);
	s++;
      }
  
  // diagonals
  if(sq->diagonal)
    for(int d=0; d<2; d++, s++)
      for(int i=0; i<9; i++)
	{
	  int j=i;
	  if(d==1)
	    j=9-i-1;
	  sq->sets[s][i] = &(sq->el[i][j]);
	}
  else
    for(int d=0; d<2; d++)
      for(int i=0; i<9; i+=3)
	sq->sets[s+d][i] = NULL;

  sq->rules = s;
  return(sq);
}

void elt_freedom(element *elt)
{
  elt->value = -1;
  elt->freedom = 0;
  for(int k=0; k<9; k++)
    if (elt->option[k]==1)
      {
	elt->value = k;
	elt->freedom++;
      }
}

void sq_freedom(square *sq)
{
  sq->freedom = 0;
  for(int i=0; i<9; i++)
    for(int j=0; j<9; j++)
      {
	elt_freedom(&(sq->el[i][j]));
	sq->freedom += sq->el[i][j].freedom;
	if(sq->el[i][j].freedom == 0)
	  {
	    sq->freedom = 0;
	    return;
	  }
      }
}

square *copy_square(square *sq)
{
  square *copy = make_square(sq->diagonal);

  for(int i=0; i<9; i++)
    for(int j=0; j<9; j++)
	{
	  copy->el[i][j].freedom = sq->el[i][j].freedom;
	  copy->el[i][j].value = sq->el[i][j].value;
	  for(int k=0; k<9; k++)
	    copy->el[i][j].option[k] = sq->el[i][j].option[k];
	}
  copy->freedom = sq->freedom;
  return(copy);
}

std::ostream &operator<<(std::ostream &os, square &sq)
{
  sq_freedom(&sq);
  for(int i=0; i<9; i++)
    {
      for(int j=0; j<9; j++)
	{
	  element elt = sq.el[i][j];
	  if (elt.freedom == 0)
	    os << "X" << " ";
	  else if (elt.freedom == 1)
	    os << elt.value+1 << " " ;
	  else
	    os << "." << " ";
	  
	  if (((j+1)%3) == 0)
	    os << " ";
	}
      
      os << std::endl;
      if ((i<8) && ((i+1)%3) == 0)
	os << std::endl;
    }
  return(os);
}

std::istream &operator>>(std::istream &is, square &sq)
{
  std::string input;
  std::string line;
  while(input.length() < 81)
    {
      std::getline(is, line);
      if(line[line.length()-1] == '\r')
	line = line.substr(0,line.length()-1);
      input += line;
    }
  
  for(int i=0; i<9; i++)
    for(int j=0; j<9; j++)
      {
	char digit[2];
	digit[0] = input[9*i+j];
	digit[1] = 0;
	int val = atoi(digit);
	if(val!=0)
	  for(int k=0; k<9; k++)
	    {
	      if ((k+1)!=val)
		sq.el[i][j].option[k] = 0;
	    }
      }
  
  sq_freedom(&sq);
  return(is);
}

void eval_rules(square *sq)
{
  for(int s=0; s<sq->rules; s++)
    for(int i=0; i<9; i++)
      {
	element *elt = sq->sets[s][i];
	if (elt->freedom == 0)
	  sq->freedom = 0;
	
	if (elt->freedom == 1)
	  for(int j=0; j<9; j++)
	    if (i != j)
	      {
		sq->sets[s][j]->option[elt->value] = 0;
		elt_freedom(sq->sets[s][j]);
	      }
      }
  sq_freedom(sq);
}

int search(square *sq)
{
  // reduce
  int last = 9*9*9;
  while (sq->freedom < last)
    {
      eval_rules(sq);
      last = sq->freedom;
    }

  eval_rules(sq);

  if (sq->freedom == 81)
   {
     std::cerr << "found solution" << std::endl;
     std::cout << *sq << std::endl;
     return(1);
   }

  if (sq->freedom < 81)
    return(0); // dead-end

  // find pivot
  int min_freedom = 10;
  int min_i = -1;
  int min_j = -1;
  for(int i=0; i<9; i++)
    for(int j=0; j<9; j++)
      {
	element *elt = &(sq->el[i][j]);
	if (elt->freedom>1 && elt->freedom<min_freedom)
	  {
	    min_freedom = elt->freedom;
	    min_i = i;
	    min_j = j;
	  }
      }

  // recurse
  element elt = sq->el[min_i][min_j];
  int solutions = 0;
  for(int k=0; k<9; k++)
    if (sq->el[min_i][min_j].option[k])
      {
	square *copy = copy_square(sq);
	copy->el[min_i][min_j].option[k] = 0;
	sq_freedom(copy);
	solutions += search(copy);
    	delete copy;
      }
  return(solutions);
}

#include <getopt.h>

void usage()
{
  std::cerr << "squares [-d] < puzzle.txt" << std::endl;
  std::cerr << "  -?         This message." << std::endl;
  std::cerr << "  -d         Include main diagonals" << std::endl;
}

int main (int argc, char*argv[])
{
  bool diagonal = false;

  char c;
  while((c = getopt(argc, argv, "?d"))!=-1)
    {
      switch(c)
	{
	case 'd':
	  diagonal=true;
	  break;
	  
	case '?':
	default:
	  usage();
	  return 1;
	}
    } 

  square *sq = make_square(diagonal);
  std::cin >> *sq;

  int solutions = search(sq);
  if (solutions == 0)
    std::cerr << *sq << "unsolvable " << std::endl;
  else
    std::cerr << "found " << solutions << " solutions." << std::endl;
}