A Number Puzzle

My friend came up with a new puzzle. Given a 3x3 matrix, fill it with the numbers 1 through 9, without repetition, in such a way that adding the three digits from any line, column or diagonal will yield exactly the same result.

This time I went for conciseness. Instead of laying out a 3x3 array -- or what have you -- I'll take a list of 9 elements, and assume the elements are laid out left to right, then top to down, so that the third element of the second line is the sixth element of the list, for example. Now, before I try to solve it, I have to devise a way to test the conditions. First, let's create a list of list of indices for each line, column of diagonal possible. This can be done programmatically, of course, like this:

 
val cols = List.range(0,3)
val lines = cols map (_ * 3)
val allLines = lines map (l => cols map (l + _))
val allCols = cols map (c => lines map (c + _))
val diagLR = lines zip cols map Function.tupled(_+_)
val diagRL = lines zip cols.reverse map Function.tupled(_+_)
val indices = diagLR :: diagRL :: allLines ::: allCols

I decided just to enter it by hand, though:

 
val indices = List(List(0,1,2), List(3,4,5), List(6,7,8), List(0,3,6), List(1,4,7), List(2,5,8), List(0,4,8), List(2,4,6))

Now, I want to test this. Suppose I have a list of numbers representing the solution. I can replace the indices by the corresponding number like this:

 
indices map (_ map (solution(_)))

from which is quite easy to compute how much each line, column and diagonal adds to:

 
indices map (_ map (solution(_)) sum)

One way, then, to check if all numbers are equal is to simply compare them:

 
indices map (_ map (solution(_)) sum) match { case head :: tail => tail forall (_ == head) }

Not concise enough for me, though. I prefer this:

 
(indices map (_ map (solution(_)) sum) removeDuplicates).size == 1

Our test function, then, is:

 
def test(solution: List[Int]) = (indices map (_ map (solution(_)) sum) removeDuplicates).size == 1

Now, how to compute the solutions? We can do it recursively with lists, recursions, filters, etc. Too much work. Let's just enumerate the possible solutions. The first element can be represented by the index over a nine-elements list of a "seed" solution. The second element can be represented by an index over the eight-element list of remaining elements, and so on. We can disambiguate the first index from the second by multiplying the second by 9, and add both. We can repeat this over and over for every other element in the list. So, to go from a number representing the solution, plus a seed list, to the solution, we can write this function:

 
def numToIndices(n: Int, l: List[Int]): List[Int] =
  if (l.isEmpty) Nil else l(n % l.size) :: numToIndices(n / l.size, l filter (_ != l(n % l.size)))

Now, given this representation of the solutions of this problem, it should be clear that the number of solutions is the factorial of 9, so there are solutions from 0 to 9! - 1. So, let's create a seed, and, non-strictly (to avoid out of memory errors), generate our possible solutions:

 
val seed = 1 to 9 toList
val possibleSolutions = Stream.range(0, seed reduceLeft (_*_)) map (numToIndices(_, seed))

Keeping the head of a stream is not a good idea, though. We need to filter for the actual solutions before assigning it to any val. Which, of course, we'll give you the final solutions:

 
val solutions = (0 until seed.reduceLeft(_*_)).toStream map (numToIndices(_, seed)) filter (test(_)) toList

Not particularly efficient, but the line count is good:

 
val indices = List(List(0,1,2), List(3,4,5), List(6,7,8), List(0,3,6), List(1,4,7), List(2,5,8), List(0,4,8), List(2,4,6))
def test(solution: List[Int]) = (indices map (_ map (solution(_)) sum) removeDuplicates).size == 1
def numToIndices(n: Int, l: List[Int]): List[Int] =
  if (l.isEmpty) Nil else l(n % l.size) :: numToIndices(n / l.size, l filter (_ != l(n % l.size)))
val seed = 1 to 9 toList
val solutions = (0 until seed.reduceLeft(_*_)).toStream map (numToIndices(_, seed)) filter (test(_)) toList

Which we can then print with:

 
println(solutions map (_.iterator grouped 3 map (_ mkString) mkString "\n") mkString "\n")