import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ String[] strings = new String[3]; Scanner scan = new Scanner(System.in); strings[0] = scan.nextLine(); strings[1] = scan.nextLine(); strings[2] = scan.nextLine(); int[][] square = new int[3][3]; prepareSquare(square, strings); boolean[] used = new boolean[9]; Arrays.fill(used, false); System.out.println(findSol(square, 0, used, 0)); } public static Integer findSol(int[][] square, Integer curCost, boolean[] used, int index) { if (index == 9) { if (isSolution(square)) { // System.out.println("///////////////////////// TEST ///////////////////////////"); // System.out.println("Found solution with cost: " + curCost); // for (int i = 0; i < 3; i++) { // System.out.println(Arrays.toString(square[i])); // } return curCost; } else return null; } int col = index % 3; int row = index / 3; int original = square[row][col]; int lowestCost = 1000; for (int i = 1; i <= used.length; i++) { // System.out.println("running"); // System.out.println(used[i]); if (!used[i - 1]) { // System.out.println("running"); square[row][col] = i; used[i - 1] = true; int costAdded = Math.abs(original - i); Integer check = findSol(square, curCost + costAdded, used, index + 1); if (check != null) { lowestCost = Math.min(lowestCost, check); } used[i - 1] = false; } } square[row][col] = original; return lowestCost; } public static void prepareSquare(int[][] square, String[] strings) { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { square[i][j] = Integer.parseInt(strings[i].substring(j * 2, (j * 2) + 1)); } } } public static boolean isSolution(int[][] square) { int rowSum = 0; int colSum = 0; int diag1Sum = 0; int diag2Sum = 0; for (int i = 0; i < square.length; i++) { for (int j = 0; j < square.length; j++) { rowSum += square[i][j]; colSum += square[j][i]; } if (rowSum != 15 || colSum != 15) return false; rowSum = 0; colSum = 0; diag1Sum += square[i][i]; diag2Sum += square[i][2 - i]; } if (diag1Sum != 15 || diag2Sum != 15) return false; return true; } }