/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2009 by Doina Logofatu

in C#: Michael Gärtner
************************************************/

using System;
using System.IO;

namespace Logofatu
{
    class P14SantaClaus
    {
        private static String FileOutputName = "nikolaus.out";

        private int[][] a = new int[5][]
            { 
                  new int[] {0,1,1,0,1},
                  new int[] {1,0,1,0,1},
                  new int[] {1,1,0,1,1},
                  new int[] {0,0,1,0,1},
                  new int[] {1,1,1,1,0}
            };
        private int[] b = new int[9];
        private int sol = 0;
        private StreamWriter sw;

        private P14SantaClaus(StreamWriter sw)
        {
            this.sw = sw;
        }

        private void run()
        {
            back(1);
        }

        private void writeSol()
        {
            sw.Write("Loesung ");
            sw.Write(++sol);
            sw.Write(": ");
            for ( int i = 0; i < 9; i++ )
            {
                sw.Write(b[i] + 1);
                sw.Write(' ');
            }
            sw.WriteLine();
        }

        private void back(int k)
        {
            int i;
            if ( 9 == k )
            {
                writeSol();
            }
            else
                for ( i = 0; i < 5; i++ )
                {
                    if ( a[i][b[k - 1]] == 1 && i != b[k - 1] )
                    {
                        b[k] = i;
                        a[i][b[k - 1]] = 0;
                        a[b[k - 1]][i] = 0;
                        back(k + 1);
                        a[i][b[k - 1]] = 1;
                        a[b[k - 1]][i] = 1;
                    }
                }
        }

        static void Main(string[] args)
        {
            StreamWriter sw = new StreamWriter(FileOutputName);
            try
            {
                new P14SantaClaus(sw).run();
            }
            catch ( IOException ex )
            {
                Console.WriteLine("Fehler bei der Dateiverarbeitung!\n" + ex.ToString());
            }
            finally
            {
                sw.Close();
            }
        }
    }
}