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

public class Niklaushaus
{
	static int corner = 5;
	static int line = 8;
	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()
	{
		InOut.println("\n\n" + solution + ". LOESUNG\n");
		InOut.println("       k 1   k 2   k 3   k 4   k 5   k 6   k 7   k 8");
		InOut.println("     |-----|-----|-----|-----|-----|-----|-----|-----|");
		for(int lines = 0; lines < inzidenz.length; lines++)
		{
			InOut.print(" p "+(lines+1)+" |");
			for(int cols = 0; cols < inzidenz[0].length; cols++)
			{
				if(inzidenz[lines][cols] == -1)
				{
					InOut.print(" "+inzidenz[lines][cols]+"  |");
				}
				else
				{
					InOut.print("  "+inzidenz[lines][cols]+"  |");
				}
			}
			InOut.println("");
			InOut.println("     |-----|-----|-----|-----|-----|-----|-----|-----|");
		}
	}
		
        public static void setAdjazent()
	{
		for (int i = 0; i < adjazent.length; i++)
		{
			adjazent[i][i] = -1;
		}
		adjazent[0][4] = -1;
		adjazent[1][4] = -1;
		adjazent[4][0] = -1;
		adjazent[4][1] = -1;
	}
}