/************************************************************************\
* Programa: knight.cpp                                                   *
* Descripción: programa que resuelve el tour del caballo                 *
* Autor: Pedro Corcuera                                                  *
* Revisión: 1.0 2/02/2008                                                *
\************************************************************************/
#include <iostream>
#include <iomanip>
using namespace std;

const int N=6;
const int NSQ=36;
int intentar(int i,int x,int y);

int h[N][N];

int main(void)
{
 int i,j,q;

 for(i=0;i<N;i++)
  for(j=0;j<N;j++)
   h[i][j]=0;
 h[0][0]=1;     // initial position
 q=intentar(2,0,0);
 if(q)
 {
  for(i=0;i<N;i++)
  {
   for(j=0;j<N;j++)
     cout << setw(3) << h[i][j];
   cout << endl;
  }
 }
}

int a[]={2,1,-1,-2,-2,-1,1,2};
int b[]={1,2,2,1,-1,-2,-2,-1};
int intentar(int i,int x,int y)
{
 int k,u,v;
 bool q1;

 k=0;
 do
 {
  q1=false;
  u=x+a[k];  v=y+b[k];
  k++;
  if ((u>=0 && u<N)&&(v>=0 && v<N))
   if (h[u][v]==0)
   {
    h[u][v]=i;
    if(i<NSQ)
    {
     q1=intentar(i+1,u,v);
     if (!q1)
      h[u][v]=0;
    }
    else
     q1=true;
   }
 } while(!q1 && k<8);
 return q1;
}