tsp

import java.util.Scanner;

public class tsp {
	/**
	 * Reads Sudoku Puzzle from STDIN in the following format. First number, should
	 * be N, which is the value for this board configuration N^2 * N^2 = N^4 size
	 * board Prints answer to STDOUT
	 * <p/>
	 * 4 0 0 0 0 0 0 0 5 0 0 9 4 0 2 8 0 0 0 6 0 0 5 0 0 9 0 0 3 0 0 8 0 0 2 0 0 0 2
	 * 5 0 1 3 0 0 0 9 0 0 4 0 0 7 0 0 1 0 0 6 0 0 5 0 0 0 8 1 0 5 9 0 0 5 0 0 0 0 0
	 * 0 0 7
	 * <p/>
	 * ZEROS represent values that need to be found
	 *
	 * @param args
	 *
	 *
	 */
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int N = 1;
		int SIZE = 7;
		int CELLS = 7;

		int[] puzzle = { 1, 0, 0, 0, 0, 0, 3 };
		int[] puzzle2 = { 1, 0, 0, 0, 0, 0, 2 };

		if (solve(puzzle) && solve(puzzle2)) {
			System.out.println("Puzzle Solved, here is the solution: ");
			for (int i = 0; i < CELLS; i++) {
				System.out.print(" " + puzzle[i]);
				if ((i + 1) % N == 0)
					System.out.print(" |");
				if (i != 0 && (i + 1) % SIZE == 0)
					System.out.println();
				if ((i + 1) % (N * SIZE) == 0)
					System.out.println("----------------------------");
			}
			for (int i = 0; i < CELLS; i++) {
				System.out.print(" " + puzzle2[i]);
				if ((i + 1) % N == 0)
					System.out.print(" |");
				if (i != 0 && (i + 1) % SIZE == 0)
					System.out.println();
				if ((i + 1) % (N * SIZE) == 0)
					System.out.println("----------------------------");
			}
		} else {
			System.out.println("Could not solve this puzzle");
		}
		System.out.println();
	}

	/**
	 * Simple recursive, deterministic, depth first search, backtracking algorithm
	 * for Sudoku Row major format puzzle as input
	 *
	 * @param puzzle
	 *            Row major format puzzle as input
	 * @return
	 */
	public static boolean solve(int[] puzzle) {
		int N = 1;
		int SIZE = 7;
		int CELLS = 7;
		int[][] usablePath = new int[][] {
			{ 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 1, 1, 0, 0, 0, 0 },
			{ 0, 1, 0, 1, 1, 1, 1, 1 },
			{ 0, 1, 1, 0, 1, 1, 1, 1 },
			{ 0, 0, 1, 1, 0, 1, 0, 1 },
			{ 0, 0, 1, 1, 1, 0, 1, 0 },
			{ 0, 0, 1, 1, 0, 1, 0, 0 },
			{ 0, 0, 1, 1, 1, 0, 0, 0 }
		};

		boolean noEmptyCells = true;
		int myRow = 0, myCol = 0;
		for (int i = 0; i < CELLS; i++) {
			if (puzzle[i] == 0) {
				myRow = i / SIZE;
				myCol = i % SIZE;
				noEmptyCells = false;
				break;
			}
		}
		if (noEmptyCells)
			return true;

		for (int choice = 1; choice <= SIZE; choice++) {
			boolean isValid = true;
			int gridCol = 6;

			int j = 0;
			for (; j < SIZE; j++) {
				if (puzzle[j] == choice) {
					isValid = false;
					break;
				}
			}
			boolean theRealValid = false;

			if (isValid) {
				if (usablePath[puzzle[(myRow * SIZE + myCol) - 1]][choice] == 0) {
					isValid = false;
				}
			}
			if (isValid) {
				puzzle[myRow * SIZE + myCol] = choice;
				boolean solved = solve(puzzle);
				if (solved)
					return true;
				else
					puzzle[myRow * SIZE + myCol] = 0;
			}

		}
		return false;
	}
}