title: Knight in n, part 3: rings
subtitle: How many ways are there to move a knight on a chessboard from a to b?
date: 2008-12-04
tags: haskell, knight-in-n
sourcelink: This post is literate Haskell, click here to download the source code.
Previously in this series:
* part 1: moves
* part 2: combinatorics
In this third installment, we will look at how to use various types as numbers, i.e. how to make them an instance of the @Num@ type class.
The solution the Knight-moves-problem will emerge at the end, almost as if by magic. $:)$
> -- HIDDEN
> {-# LANGUAGE NoMonomorphismRestriction #-}
> module Knight3 where
> import Knight1
> import Data.Array
== Tangent: Things as numbers ==
Many types can be used as if they are numbers. Haskell-wise this means they can be an instance of the @Num@ type class. Mathematically it means that these types are rings.
-- Pairs as numbers --
Let's start with a @Num@ instance for pairs @(α,β)@.
In general, our only choice is to do everything pointwise.
So for all operations ⊗ (i.e. @(+)@, @(-)@ and @(*)@:
FORMULA: knight/pointwise_tuple
\begin{pmatrix}a\\b\end{pmatrix}
\otimes
\begin{pmatrix}c\\d\end{pmatrix}
=
\begin{pmatrix}a\otimes c\\b \otimes d\end{pmatrix}
In ring theory this is called the ''direct product''. In Haskell we can write it as:
> instance (Num α, Num β) => Num (α,β) where
> (a,b) + (c,d) = (a+c,b+d)
> (a,b) - (c,d) = (a-c,b-d)
> (a,b) * (c,d) = (a*c,b*d)
> fromInteger i = (fromInteger i, fromInteger i)
> abs (a,b) = (abs a, abs b)
> signum (a,b) = (signum a, signum b)
We could also make instances for triples, quadruples and other tuples this way, but those are not needed for the rest of the story.
-- Arrays as numbers --
A more general kind of tuple is an array; which is somewhat like a tuple of arbitrary size.
Of course, that is not quite true, since two arrays with the same type can have a ''different'' size.
One way around this problem is to treat all arrays as if they are infinite, by taking values outside the bounds to be equal to $0$. So
]> -- EXAMPLE
]> listArray (0,0) [1] == listArray (-!!!∞!!!,!!!∞!!!) [..,0,0,1,0,0,..] -- pseudocode
That way we can still do addition pointwise,
FORMULA: knight/pointwise_add_array
\begin{pmatrix}a\\b\\\vdots\end{pmatrix}
+
\begin{pmatrix}c\\d\\\vdots\end{pmatrix}
=
\begin{pmatrix}a+c\\b+d\\\vdots\end{pmatrix}
The @accumArray@ function can help with the missing elements by setting them to @0@ by default:
> addArray a b = accumArray (+) 0 (min a__lo b__lo, max a__hi b__hi) (assocs a ++ assocs b)
> where (a__lo,a__hi) = bounds a
> (b__lo,b__hi) = bounds b
Next up is the @fromInteger@ function.
@fromInteger 0@ is easy; there are two options for other values
.# @fromInteger i@ is an infinite array of values @i@.
.# @fromInteger i@ is an array with values @i@ at some single point.
The first choice mimics the definition for tuples, @fromInteger i = (fromInteger i, fromInteger i)@.
But for arrays this has the slight problem of requiring an infinite array.
For the second alternative we need to pick the index where to put the number @i@. The obvious choice is to put @i@ at 'the origin', index @0@:
> intArray i = listArray (0,0) [fromInteger i]
Finally, multiplication. As you have learned in school, multiplication can be seen as repeated addition, In our Haskell world that means that we expect the law @a + a = fromInteger 2 * a@ to hold.
If we had used the first choice for @fromInteger@ then multiplication could be done pointwise as it was for tuples. But we have made a different choice, so now @fromInteger 2@ is an array that contains the value @2@ at index @0@ (and is implicitly zero everywhere else). When calculating @fromInteger 2 * a@, this @2@ should by multiplied with ''all'' elements of the array @a@.
The operation that does the right thing is ''convolution''. It looks like this:
FORMULA: knight/pointwise_mul_array
\begin{pmatrix}a\\b\\c\end{pmatrix}
*
\begin{pmatrix}d\\e\\f\end{pmatrix}
\; = \;
\raisebox{5mm }{$a\begin{pmatrix}d\\e\\f\end{pmatrix}$} +
\raisebox{0mm }{$b\begin{pmatrix}d\\e\\f\end{pmatrix}$} +
\raisebox{-5mm}{$c\begin{pmatrix}d\\e\\f\end{pmatrix}$}
\; = \;
\left(\begin{array}{@{}c@{}c@{}c@{}c@{}c@{}}
ad&&&&\\ae&+&bd&&\\af&+&be&+&cd\\&&bf&+&ce\\&&&&cf
\end{array}\right)
So for each element @v@ at index @i@ in the first array, we shift a copy of the second array so that its origin becomes @i@. This copy is multiplied by @v@ and all these copies are added.
If one of the arrays is @fromInteger v@ (i.e. a scalar), then this corresponds to multiplying all elements in the other array by @v@; exactly what we wanted.
Convolution can be implemented with @accumArray@ as:
> mulArray a b
> = accumArray (+) 0 (bounds a + bounds b)
> [ (i+j, x*y) | (i,x) <- assocs a, (j,y) <- assocs b ]
Notice that we use the @Num (α,β)@ instance for the bounds, and that this definition is nicely symmetrical.
Putting it all together, we get the following instance:
> instance (Ix i, Num i, Num a) => Num (Array i a) where
> fromInteger = intArray
> (+) = addArray
> (*) = mulArray
> negate = fmap negate
> abs = fmap abs
> signum = fmap signum
In mathematical terms, what we constructed here is called a ''group ring''. There is a group ring $G[R]$ for any group $G$ and ring $R$, which corresponds to an instance @Num (Array g r)@ when @g@ is a group (i.e. an instance of @Num@) and @r@ is a ring (also an instance of @Num@).
-- Arrays as polynomials --
Another way to interpret the above instance, is by treating arrays as polynomials over some variable $x$. The array @array [(i,a),(j,b),(k,c),..]@ then represents the polynomial $ax^i+bx^j+cx^k+...$. The addition and multiplication defined above now have the expected meaning, for example:
]> > let a = listArray (0,2) [2,3,4] -- 2 + 3x + 4x^2
]> > let b = listArray (1,2) [5,6] -- 5x + 6x^2
]> > a + b
]> array (0,2) [(0,2),(1,8),(2,10)] -- 2 + 8x + 10x^2
]> > a * b
]> array (1,4) [(1,10),(2,27),(3,38),(4,24)] -- 10x + 27x^2 + 38x^3 + 24x^4
We can make this even more suggestive by defining:
> x = listArray (1,1) [1]
]> > (2 + 3*x + 4*x^2) * (5*x + 6*x^2) == 10*x + 27*x^2 + 38*x^3 + 24*x^4
]> True
If you are interested in this interpretation,
sigfpe wrote an interesting blog post about convolutions, polynomials and power series.
== It's magic! ==
Now, let's go back to our original problem, the moves of a chess knight.
The positions reachable in a single move can be put into a two dimensional array (i.e. a matrix).
> moveMatrix :: Array (Int,Int) Integer
> moveMatrix = accumArray (+) 0 ((-2,-2),(2,2)) [ (m,1) | m <- moves ]
This is the familiar ''move matrix'', which we already saw in part 1.
]> Knight3> printMatrix moveMatrix
] 0 1 0 1 0
] 1 0 0 0 1
] 0 0 0 0 0
] 1 0 0 0 1
] 0 1 0 1 0
Now the magic.
We defined multiplication of two arrays @a@ and @b@ as adding copies of @b@ for each value in @a@.
If we use the move matrix as @b@, then this means we add all possible destinations of a knight making one move from each place it can reach. Repeating this $n$ times gives us our answer. Since repeated multiplication is exponentiation:
> allPaths__conv n = moveMatrix ^ n
For example, for $n=2$:

If we are interested in just a single point there is the array indexing operator (!!) to help us,
> paths__conv n ij
> | inRange (bounds m) ij = m ! ij
> | otherwise = 0
> where m = allPaths__conv n
This convolutional algorithm can count the number of paths in $O(n^3)$, but not just for a single end point, but for ''all'' end points at once! The program is also a lot simpler than the
The @paths__conv@ algorithm is pretty good, but we can ''still'' do better.
Next time I will show how the algorithm from part 3 can be improved further, and curiously, how it will start to look more like the algorithm from part 2.