/*
 *  Solitaire.java
 *  Copyright (C) 2002  Frank Buß (fb@frank-buss.de)
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You can get the GNU General Public License at
 *  http://www.gnu.org/licenses/gpl.html
 */

public class Solitaire {
	private static int start[][] = {
		{ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 },
		{ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 },
		{ 8, 8, 8, 8, 0, 0, 0, 8, 8, 8, 8 },
		{ 8, 8, 8, 8, 1, 0, 1, 8, 8, 8, 8 },
		{ 8, 8, 0, 1, 0, 1, 0, 1, 0, 8, 8 },
		{ 8, 8, 1, 0, 0, 1, 0, 0, 1, 8, 8 },
		{ 8, 8, 1, 0, 0, 1, 0, 0, 1, 8, 8 },
		{ 8, 8, 8, 8, 0, 1, 0, 8, 8, 8, 8 },
		{ 8, 8, 8, 8, 1, 1, 1, 8, 8, 8, 8 },
		{ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 },
		{ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 }
	};

	private final static int end[][] = {
		{ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 },
		{ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 },
		{ 8, 8, 8, 8, 1, 1, 1, 8, 8, 8, 8 },
		{ 8, 8, 8, 8, 1, 1, 1, 8, 8, 8, 8 },
		{ 8, 8, 1, 1, 1, 1, 1, 1, 1, 8, 8 },
		{ 8, 8, 1, 1, 1, 0, 1, 1, 1, 8, 8 },
		{ 8, 8, 1, 1, 1, 1, 1, 1, 1, 8, 8 },
		{ 8, 8, 8, 8, 1, 1, 1, 8, 8, 8, 8 },
		{ 8, 8, 8, 8, 1, 1, 1, 8, 8, 8, 8 },
		{ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 },
		{ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 }
	};

	private static int equal = 0;

	private static void printBoard() {
		for (int y = 2; y < 9; y++) {
			for (int x = 2; x < 9; x++) {
				switch (start[y][x]) {
					case 8:
						System.out.print(" ");
						break;
					case 1:
						System.out.print("*");
						break;
					case 0:
						System.out.print("O");
						break;
				}
			}
			System.out.println();
		}
		System.out.println();
	}
	
	private static boolean check() {
		if (equal == 49) {
			System.out.println("eine Lösung gefunden:");
			System.out.println();
			printBoard();
			return true;
		}
		for (int x = 2; x < 9; x++) {
			for (int y = 2; y < 9; y++) {
				if (start[y][x] == 0) {
					if (start[y + 1][x] == 0 && start[y + 2][x] == 1) {
						int d = 0;
						if (start[y][x] == end[y][x])
							d++;
						if (start[y + 1][x] == end[y + 1][x])
							d++;
						if (start[y + 2][x] == end[y + 2][x])
							d++;
						d = 3 - d - d;
						equal += d;
						start[y][x] = 1;
						start[y + 1][x] = 1;
						start[y + 2][x] = 0;
						boolean result = check();
						equal -= d;
						start[y][x] = 0;
						start[y + 1][x] = 0;
						start[y + 2][x] = 1;
						if (result) {
							printBoard();
							return true;
						}
					}
					if (start[y - 1][x] == 0 && start[y - 2][x] == 1) {
						int d = 0;
						if (start[y][x] == end[y][x])
							d++;
						if (start[y - 1][x] == end[y - 1][x])
							d++;
						if (start[y - 2][x] == end[y - 2][x])
							d++;
						d = 3 - d - d;
						equal += d;
						start[y][x] = 1;
						start[y - 1][x] = 1;
						start[y - 2][x] = 0;
						boolean result = check();
						equal -= d;
						start[y][x] = 0;
						start[y - 1][x] = 0;
						start[y - 2][x] = 1;
						if (result) {
							printBoard();
							return true;
						}
					}
					if (start[y][x + 1] == 0 && start[y][x + 2] == 1) {
						int d = 0;
						if (start[y][x] == end[y][x])
							d++;
						if (start[y][x + 1] == end[y][x + 1])
							d++;
						if (start[y][x + 2] == end[y][x + 2])
							d++;
						d = 3 - d - d;
						equal += d;
						start[y][x] = 1;
						start[y][x + 1] = 1;
						start[y][x + 2] = 0;
						boolean result = check();
						equal -= d;
						start[y][x] = 0;
						start[y][x + 1] = 0;
						start[y][x + 2] = 1;
						if (result) {
							printBoard();
							return true;
						}
					}
					if (start[y][x - 1] == 0 && start[y][x - 2] == 1) {
						int d = 0;
						if (start[y][x] == end[y][x])
							d++;
						if (start[y][x - 1] == end[y][x - 1])
							d++;
						if (start[y][x - 2] == end[y][x - 2])
							d++;
						d = 3 - d - d;
						equal += d;
						start[y][x] = 1;
						start[y][x - 1] = 1;
						start[y][x - 2] = 0;
						boolean result = check();
						equal -= d;
						start[y][x] = 0;
						start[y][x - 1] = 0;
						start[y][x - 2] = 1;
						if (result) {
							printBoard();
							return true;
						}
					}
				}
			}
		}
		return false;
	}

	public static void main(String args[]) {
		for (int x = 2; x < 9; x++) {
			for (int y = 2; y < 9; y++) {
				if (start[y][x] == end[y][x])
					equal++;
			}
		}
		if (!check()) {
			System.out.println("keine Lösung gefunden");
			System.out.println();
		}
	}
}