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

import java.io.*;

public class P14SantaClaus {
  private static final String FileOutputName = "nikolaus.out";

  private int a[][] = { 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 PrintStream out;

  P14SantaClaus(PrintStream out) {
    this.out = out;
  }

  void run() {
    back(1);
  }

  private void writeSol() {
    out.print("Solutia ");
    out.print(++sol);
    out.print(": ");
    for (int i = 0; i < 9; i++) {
      out.print(b[i] + 1);
      out.print(' ');
    }
    out.println();
  }

  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;
        }
  }

  public static void main(String[] args) throws IOException {
    PrintStream out = new PrintStream(new File(FileOutputName));
    try {
      new P14SantaClaus(out).run();
    } finally {
      out.close();
    }
  }
}