object Solution { def main(args: Array[String]) { val M = 15 type Matrix = List[List[Int]] type State = (List[List[Int]], Int) //(matrix, cost) val GOALS = Set[Matrix]( List(List(8,1,6),List(3,5,7),List(4,9,2)), List(List(6,1,8),List(7,5,3),List(2,9,4)), List(List(8,3,4),List(1,5,9),List(6,7,2)), List(List(4,3,8),List(9,5,1),List(2,7,6)), List(List(6,7,2),List(1,5,9),List(8,3,4)), List(List(2,7,6),List(9,5,1),List(4,3,8)), List(List(4,9,2),List(3,5,7),List(8,1,6)), List(List(2,9,4),List(7,5,3),List(6,1,8)) ) def diff(m1: Matrix, m2: Matrix): Matrix = { for (i <- 0 to 2) yield { for (j <- 0 to 2) yield Math.abs(m1(i)(j) - m2(i)(j)) }.toList }.toList def findClosest(matrix: Matrix): (Matrix, Matrix) = {for (goal <- GOALS) yield (goal, diff(matrix, goal))}.minBy(p => p._2.flatten.sum) def process(in: java.io.InputStream) = { val sc = new java.util.Scanner(in) val matrix = {for (i <- 0 to 2) yield {for (j <- 0 to 2) yield sc.nextInt()}.toList}.toList val (goal, diff) = findClosest(matrix) //System.out.println(goal.mkString("\n")) System.out.println(diff.flatten.sum) } process(System.in) } }