/*
Problem konika (skoczka) szachowego
www.algorytm.org
Adam Mika, Tomasz Lubinski (c) 2008

Algorytm podaje pierwsze dopuszczalne rozwiązanie problemu dla podanego punktu startowego
pod warunkiem, że takie rozwiązanie istnieje.
*/
using System;

namespace Konik
{
	/// <summary>
	/// Problem konika (skoczka) szachowego
	/// </summary>
	class ProblemKonika
	{
		/// <summary>
		/// Algorytm podaje pierwsze dopuszczalne rozwiązanie problemu dla podanego
		/// punktu startowego pod warunkiem, że takie rozwiązanie istnieje.
		/// </summary>
		[STAThread]
		static void Main(string[] args)
		{
		   int max = 8;	//rozmiar problemu - wymiar szachownicy
		   int[,] tab = new int[max,max];
		      
		   for(int i=0 ; i<max ; i++)
		      for(int j=0 ; j<max ; j++)
		         tab[i,j] = 0;
		   
		   if (skoczek(tab, max, 0, 0, 1) == true)
		   {
			   	for(int i=0 ; i<max ; i++)
			   	{
			   		for(int j=0 ; j<max ; j++)
			   			Console.Write(tab[j,i] + " ");
			   		Console.WriteLine();
			   	}
		   }
		}

		private static bool ruch(int[,] tab, int N, int wariant, int x, int y, ref int nx, ref int ny)
		{
			switch (wariant) {
			case 1: 
					nx = x+1; 
					ny = y-2;
					break;
		    case 2:
		           nx = x+2;
			       ny = y-1;
				   break;
		    case 3:
		           nx = x+2;
			       ny = y+1;
				   break;
		    case 4: 
		           nx = x+1;
			       ny = y+2;
				   break;
		    case 5:
		           nx = x-1;
			       ny = y+2;
				   break;
		    case 6:
		           nx = x-2;
			       ny = y+1;
				   break;
		    case 7:
		           nx = x-2;
			       ny = y-1;
				   break;
		    case 8:
		           nx = x-1;
				   ny = y-2;
			       break;
			}   
		    if (0<=nx && nx<N && 0<=ny && ny<N && tab[nx,ny]==0)
		       return true;
		    return false;                            
		}   

		public static bool skoczek(int[,] tab, int n, int x, int y, int ktory)
		{
		   int nx, ny;
	   
		   nx = 0;
		   ny = 0;
		   tab[x,y] = ktory;
	   
		   if(ktory == n*n)
		   { 
		      return true;
		   }   
		   else
		   {
		      for(int w=1 ; w<9 ; w++)
			    if(ruch(tab, n, w, x, y, ref nx, ref ny) == true)
				  if (skoczek(tab, n, nx, ny, ktory+1) == true)
	        		return true;
			 tab[x,y] = 0;
		   }
		   return false;
		} 
	}
}