/*
**************************************************************************
* Dateiname     : DoppelNiklaushaus.java                                 *
* Autor         : Tardy Thomas                                           *
* Datum         : 14. Mai 2003                                           *
* Fach		: Mathematik                                             *
* Bemerkung     : Das Problem wurde mit der Backtracking-Methode gelöst. *
**************************************************************************
*/

public class DoppelNiklaushaus
{
	static int corner = 8;
	static int line = 14;
	static int adjazent[][] = new int[corner][corner];
	static int inzidenz[][] = new int[corner][line];
	static int solution;
	static int edges;
	static boolean print = true;
	
	public static void main(String [] args)
	{
		setAdjazent();
                setHouse(0);
		InOut.println("\n\nTOTAL LOESUNGEN: "+solution+"\n\n");
	}
	
	public static void setHouse(int start)
	{
		for (int end = 0; end < adjazent.length; end++)
		{
			if(setLineOK(start, end))
			{
				adjazent[start][end] = 1;
				inzidenz[start][edges] = 1;
				inzidenz[end][edges] = -1;
				edges++;
				if(edges == inzidenz[0].length)
				{
					solution++;
					if(print)
					{
						drawHouse();
					}
				}
				else
				{
					setHouse(end);
				}
				edges--;
				adjazent[start][end] = 0;
				inzidenz[start][edges] = 0;
				inzidenz[end][edges] = 0;
			}
		}
	}
	
	public static boolean setLineOK(int start, int end)
	{
		for(int tempedges = 0; tempedges < inzidenz[0].length; tempedges++)
		{
			if((Math.abs(inzidenz[start][tempedges]) == 1 && Math.abs(inzidenz[end][tempedges]) == 1) || adjazent[start][end] == -1)
			{
				return false;
			}
		}
		return true;		
	}
	
	public static void drawHouse()
	{
		long path = 0;
		for(int i = 0; i < inzidenz[0].length; i++)
		{
			for( int j = 0; j < inzidenz.length; j++)
			{
				if(inzidenz[j][i] == 1)
				{
					path += ((j+1)*(Math.pow(10,(inzidenz[0].length-i))));
				}
			}
		}
		for(int j = 0; j < inzidenz.length; j++)
		{
			if(inzidenz[j][inzidenz[0].length-1] == -1)
			{
				path+= (j+1);
			}
		}
		InOut.println(path);
	}
		
	public static void setAdjazent()
	{
		for (int i = 0; i < adjazent.length; i++)
		{
			adjazent[i][i] = -1;
		}
		adjazent[0][2] = -1;
		adjazent[0][3] = -1;
		adjazent[0][6] = -1;
		adjazent[0][7] = -1;
                adjazent[1][4] = -1;
                adjazent[1][6] = -1;
                adjazent[1][7] = -1;
                adjazent[2][0] = -1;
                adjazent[2][5] = -1;
                adjazent[2][6] = -1;
                adjazent[2][7] = -1;
                adjazent[3][0] = -1;
                adjazent[3][5] = -1;
                adjazent[3][6] = -1;
                adjazent[4][1] = -1;
                adjazent[5][2] = -1;
                adjazent[5][3] = -1;
                adjazent[5][7] = -1;
                adjazent[6][0] = -1;
                adjazent[6][1] = -1;
                adjazent[6][2] = -1;
                adjazent[6][3] = -1;
                adjazent[6][7] = -1;
                adjazent[7][0] = -1;
                adjazent[7][1] = -1;
                adjazent[7][2] = -1;
                adjazent[7][5] = -1;
                adjazent[7][6] = -1;
	}
}