1.

import java.util.ArrayList;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 291 - The House Of Santa Claus
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=227
*
* @author Christian Posselt
* @author Christian Mitterreiter
* @version 1.0, 04.05.2011
*
* Status: Accepted
* Time: 0.112
*/
public class Main
{

/**
* House of Santa Claus has 5 corners
*/
public static final int maxCorners = 5;

/**
* 8 edges must be run through for a complete house
*/
public static final int maxEdges = 8;

/**
* shows whether an edge is valid.
* E.g. Edge between Corner 1 and 5 is valid,
* but between Corner 1 and 4 is not valid.
*/
public static boolean[][] edgeValid;

/**
* to find valid solutions, it need to be remembered
* which edges are already used
*/
public static boolean[][] edgeUsed;

/**
* Array with the way
*/
public static int[] currentSolution;

/**
* number of currently placed edges
*/
public static int currentlyPlacedAdges;

/**
* all valid solutions
*/
public static ArrayList<String> solution = new ArrayList<String>();


public static void main(String[] args)
{
initialize();

//find all solutions with starting point 1
findSolutions(0);

//print all solutions
for(String single:solution)
System.out.println(single);

}

/**
* initializes the arrays
*/
static void initialize()
{
//initialize amount of edges between corners
edgeValid = new boolean[maxCorners][maxCorners];
edgeUsed = new boolean[maxCorners][maxCorners];

//plus 1 in order to include the start point again at the end
currentSolution = new int[maxEdges+1];

//no edged places so far
currentlyPlacedAdges = 0;

//Set all edges, which are valid, e.g. edge between point 1 and 5.
edgeValid[0][1] = true;
edgeValid[0][2] = true;
edgeValid[0][4] = true;
edgeValid[1][0] = true;
edgeValid[1][2] = true;
edgeValid[1][4] = true;
edgeValid[2][0] = true;
edgeValid[2][1] = true;
edgeValid[2][3] = true;
edgeValid[2][4] = true;
edgeValid[3][2] = true;
edgeValid[3][4] = true;
edgeValid[4][0] = true;
edgeValid[4][1] = true;
edgeValid[4][2] = true;
edgeValid[4][3] = true;

}

/**
* finds all solutions
*
* @param start: int with the starting point.
*/
static void findSolutions(int start)
{
for (int target=0; target<maxCorners; target++)
{
//place an edge if it is valid and not used yet
if(edgeValid[start][target] && !edgeUsed[start][target])
{
placeEdge(start, target);

//keep doing backtracking until all corners are used
if (currentlyPlacedAdges != maxEdges)
findSolutions(target);
else
saveSolution();

deleteEdge(start, target);
}
}
}

/**
* inserts an edge
*
* @param from: int with the starting point
* @param to: int with the end point
*/
static void placeEdge(int from, int to)
{
//place the edge in both directions
edgeUsed[from][to] = true;
edgeUsed[to][from] = true;
currentlyPlacedAdges++;

//set the edge into the solution set
currentSolution[currentlyPlacedAdges-1] = from+1;
currentSolution[currentlyPlacedAdges] = to+1;
}

/**
* deletes an edge
*
* @param from: int with the starting point
* @param to: int with the end point
*/
static void deleteEdge(int from, int to)
{
//delete the edge in both directions
edgeUsed[from][to] = false;
edgeUsed[to][from] = false;
currentlyPlacedAdges--;
}

/**
* saves a valid solution
*/
static void saveSolution()
{
String singleSolution = "";
for (int i=0; i<=maxEdges; i++)
singleSolution += currentSolution[i];

solution.add(singleSolution);
}


}


--------------------------------------------------


1.

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 291 - The House Of Santa Claus
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=4&problem=227&mosmsg=Submission+received+with+ID+8353319
*
* @author Manuel Hager
* @version 1.0, 10/27/2010
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.088
*/

public class Main
{
private static class Point
{
public final String value;
public Point[] neigbors = null;

public Point(String str) {
this.value = str;
}
public void setNeigbors(Point... neigbors) {
this.neigbors = neigbors;
}
@Override public String toString() {
return value;
}
}

private static class Graph
{
private Map<Point, Map<Point, Boolean>> map;

public Graph() {
map = new HashMap<Point, Map<Point, Boolean>>();
}

public void add(Point a, Point b) {
if(map.containsKey(a)) {
Map<Point, Boolean> inside = map.get(a);
if(!inside.containsKey(b)) {
inside.put(b, new Boolean(false));
return;
}
}

else if(map.containsKey(b)){
Map<Point, Boolean> inside = map.get(b);
if(!inside.containsKey(a)) {
inside.put(a, new Boolean(false));
return;
}
}

Map<Point, Boolean> map2 = new HashMap<Point, Boolean>();
map2.put(b, new Boolean(false));
map.put(a, map2);
}

public boolean isUsed(Point a, Point b) {
if(map.containsKey(a)) {
Map<Point, Boolean> inside = map.get(a);
if(inside.containsKey(b))
return inside.get(b);

return isUsed(b, a);
}
else if(map.containsKey(b)) {
Map<Point, Boolean> inside = map.get(b);
if(inside.containsKey(a))
return inside.get(a);

return isUsed(b, a);
}
throw new RuntimeException("Should not happen!");
}

public boolean setUsed(Point a, Point b, boolean value) {
if(map.containsKey(a)) {
Map<Point, Boolean> inside = map.get(a);
if(inside.containsKey(b)) {
return inside.put(b, value);
}
else {
return setUsed(b, a, value);
}
}
else if(map.containsKey(b)) {
Map<Point, Boolean> inside = map.get(b);
if(inside.containsKey(a)) {
return inside.put(a, value);
}
else {
return setUsed(b, a, value);
}
}
throw new RuntimeException("Should not happen!");
}

public boolean isFinished() {
for(Map<Point, Boolean> currMap : map.values()) {
for(Boolean b : currMap.values()) {
if(!b)
return false;
}
}
return true;
}
}

public static void main(String[] args) throws IOException
{
Point p1 = new Point("1");
Point p2 = new Point("2");
Point p3 = new Point("3");
Point p4 = new Point("4");
Point p5 = new Point("5");

p1.setNeigbors(p2, p3, p5);
p2.setNeigbors(p1, p3, p5);
p3.setNeigbors(p1, p2, p4, p5);
p4.setNeigbors(p3, p5);
p5.setNeigbors(p1, p2, p3, p4);

Graph graph = new Graph();
graph.add(p1, p2);
graph.add(p1, p3);
graph.add(p1, p5);
graph.add(p2, p3);
graph.add(p2, p5);
graph.add(p3, p4);
graph.add(p3, p5);
graph.add(p4, p5);

startAt(p1, graph, new ArrayList<Point>());
}

private static boolean startAt(Point start, Graph graph, List<Point> list) {
list.add(start);

for(Point currNeigbor : start.neigbors)
{
if(!graph.isUsed(start, currNeigbor))
{
graph.setUsed(start, currNeigbor, true);
if(startAt(currNeigbor, graph, list))
{
System.out.println(listToString(list));
graph.setUsed(start, currNeigbor, false);
}
else
{
int index = list.lastIndexOf(currNeigbor);
while(list.size() -1 >= index) {
list.remove(index);
}
graph.setUsed(start, currNeigbor, false);
}
}
}
return graph.isFinished() ;
}

private static String listToString(List<Point> list) {
StringBuilder str = new StringBuilder(list.size());
for(Point p : list) {
str.append(p.toString());
}
return str.toString();
}
}

2. Erste Version: JAVA, [2] + Evgeni Pavlidis


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

import java.io.*;

public class Main {
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;

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

void run() {
back(1);
}

private void writeSol() {
for (int i = 0; i < 9; i++) {
out.print(b[i] + 1);
}
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(System.out);
try {
new Main(out).run();
} finally {
out.close();
}
}
}


3.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 291 House of Santa Claus
*
* @author Reichart Robert
*
* Status : Accepted
* Runtime: 0.100
*/

import java.util.*;

class Main{
public static void main(String... args){
int[] number = {123153452,
123453152,
125431532,
132543512,
135234512,
134521532,
152134532,
153213452,
154312532,
123154352,
125135432,
125435132,
135123452,
135432152,
134523512,
152354312,
153254312,
154321352,
123513452,
125134532,
132153452,
135125432,
135432512,
134532152,
152345312,
153452132,
154325312,
123543152,
125315432,
132154352,
135215432,
134512352,
134532512,
153123452,
153452312,
154352132,
123451352,
125345132,
132534512,
134512532,
152135432,
153125432,
154312352,
154352312};
Arrays.sort(number);
for (int i=0;i<number.length;i++){
System.out.println(number[i]);
}

}
}