/************************************************************************\
* Programa: sudoku1.cpp                                                  *
* Descripción: Programa que resuelve un sudoku que se lee desde fichero  *
* Autor: Pedro Corcuera                                                  *
* Revisión: 1.0 2/02/2008                                                *
\************************************************************************/
#include <iostream>
#include <iomanip>
using namespace std;

int sudoku[9][9];

void leeSudoku(void);
void resSudoku(int, int);
bool buscaCeldaVacia(int *, int *);
bool puedoColocar(int, int, int);
void impSudoku(void);

int main(void)
{
    leeSudoku();
	resSudoku(0,0);

	return 0;
}

void resSudoku(int x, int y)
{
 int nro, hayVacia;

 hayVacia=buscaCeldaVacia(&x, &y);

 if ( !hayVacia ) impSudoku();
 else
 {
  for(nro=1; nro<=9; nro++)
   if ( puedoColocar(x, y, nro) )
   {
    sudoku[x][y]=nro; // lo coloco
    resSudoku(x,y+1); // tomo el sgte
    sudoku[x][y]=0; // lo quito
   }
 }
}

bool buscaCeldaVacia(int *x, int *y)
{
 for( ; *x<9; (*x)++)
 {
  for( ; *y<9; (*y)++)
    if( sudoku[*x][*y]==0 )
      return true;
  *y=0;
 }
 return false;
}

bool puedoColocar(int f, int c, int nro)
{
 int i, j, iniFil, finFil, iniCol, finCol;
 // comprueba fila
 for(j=0; j<9; j++)
 if(sudoku[f][j]==nro)
   return false;
 // comprueba columna
 for(i=0; i<9; i++)
 if(sudoku[i][c]==nro)
   return false;
// comprueba subcuadrado
 iniCol = (c/3) *3;
 finCol = iniCol+3;
 iniFil = (f/3) *3;
 finFil = iniFil+3;
 for(i=iniFil; i<finFil; i++)
  for(j=iniCol; j<finCol; j++)
   if(sudoku[i][j]==nro)
     return false;
   return true;
}

void impSudoku(void)
{
 int i, j;

 cout << "SOLUCION:\n ========\n\n";
// printf("SOLUCION:\n");
// printf("========\n\n");
 for(i=0; i<9; i++)
 {
   for(j=0; j<9; j++)
   {
     cout << setw(2)<< sudoku[i][j];
//     printf("%d",sudoku[i][j]);
     if ( j==2 || j==5 )
        cout << " | ";
//        printf(" | ");
   }
   cout << endl;
//  printf("\n");
  if ( i==2 || i==5 )
    cout << "--- | --- | ---\n";
//    printf("--- | --- | ---\n");
 }
 cout << endl;
// printf("\n");
}

void leeSudoku(void)
{
 int i, j;

 cout << "Introduce SUDOKU (valor seguido de espacio para cada fila,\n";
 cout << "                 (0 para indicar celda vacia):\n\n";

// printf("Introduce SUDOKU (valor seguido de espacio para cada fila,\n");
// printf("                 (0 para indicar celda vacia):\n");
// printf("\n");
 for(i=0; i<9; i++)
 {
     cout << "Fila " << i+1 <<": ";
//     printf("Fila %d : ",i+1);
   for(j=0; j<9; j++)
    cin >> sudoku[i][j];
//     scanf("%d",&sudoku[i][j]);
 }

}