-- Tiling rectangles by minimal number of squares.
--
-- Inspired by David Radcliffe.
-- Author: Bertram Felgenhauer <int-e@gmx.de>
-- Date: 2012-11-12

module Main (main) where

import Control.Monad

-- Young diagrams are described as lists of valleys.

-- Each valley has a left flank, a right flank,
-- and a lower bound for the size of the square that it contains.
data Valley = V !Int !Int !Int -- left, min square size, right
    deriving Show

infixr `cons`

-- Add a single square to a valley sequence.
extend :: [Valley] -> [[Valley]]
extend [] = []
extend (V a m b:vs) =
    [V (a-s) 1 s `cons` V s 1 (b-s) `cons` vs | s <- [m .. min a b]] ++
    [V a (min a b + 1) b `cons` v' | v' <- extend vs]

-- Prepend a valley to a valley sequence, coalescing flanks if one of the
-- adjacent flanks has length 0. The function `cons` maintains the invariant
-- that only the first valley of a valley sequence may have a zero length
-- flank, which must be a left flank.
cons :: Valley -> [Valley] -> [Valley]
V _ _ 0 `cons` [] = []
V a m 0 `cons` (V a' m' b' : vs) = V (a'+a) m' b' : vs
V a m b `cons` (V 0  m' b' : vs) = V a m (b+b') : vs
v       `cons` vs                = v : vs

-- Depth first search -- given an upper bound on the number of squares
-- required, find number of squares required for actual tilings.
fill :: [Valley] -> Int -> [Int]
fill [] bd = [0]
fill [V 0 _ _] bd = [0]
fill vs bd = do
    vs' <- extend vs
    guard (length vs' <= bd)
    i <- fill vs' (bd-1)
    return (i+1)

-- Look up minimum number of squares in `table`.
bound :: Int -> Int -> Int
bound n m | n < m     = table !! (m-1) !! (n-1)
          | otherwise = table !! (n-1) !! (m-1)

-- Table of minimum numbers of squares required to tile n*m rectangle.
table :: [[Int]]
table = map go [1..] where
    go n = [go' n m | m <- [1..n-1]] ++ [1]
    -- calculate entry for n*m rectangle
    go' n m =
        let -- use previous entries to obtain an upper bound
            bd = minimum $ [bound (n-k) m + bound k m | k <- [1..n-1]] ++
                           [bound n (m-k) + bound n k | k <- [1..m-1]]
            -- iterative flattening search - restart search with new bound
            -- whenever we obtain a better solution
            go'' bd = case fill [V n 1 m] (bd-1) of
                       [] -> bd
                       bd' : _ -> go'' bd'
        in  go'' bd

main :: IO ()
main = do
    mapM_ print $ take 40 table

{-
> ghc --make -O2 Young.hs
> time ./Young
[1]
[2,1]
[3,3,1]
[4,2,4,1]
[5,4,4,5,1]
[6,3,2,3,5,1]
[7,5,5,5,5,5,1]
[8,4,5,2,5,4,7,1]
[9,6,3,6,6,3,6,7,1]
[10,5,6,4,2,4,6,5,6,1]
[11,7,6,6,6,6,6,6,7,6,1]
[12,6,4,3,6,2,6,3,4,5,7,1]
[13,8,7,7,6,6,6,6,7,7,6,7,1]
[14,7,7,5,7,5,2,5,7,5,7,5,7,1]
[15,9,5,7,3,4,8,8,4,3,7,5,8,7,1]
[16,8,8,4,7,5,7,2,7,5,7,4,8,7,7,1]
[17,10,8,8,7,7,7,8,8,7,7,7,8,7,8,8,1]
[18,9,6,6,7,3,7,6,2,6,7,3,7,6,5,7,8,1]
[19,11,9,8,8,7,7,7,7,7,7,7,7,7,7,7,9,7,1]
[20,10,9,5,4,6,7,4,8,2,8,4,7,6,4,5,7,6,9,1]
[21,12,7,9,8,5,3,7,5,7,7,5,7,3,5,8,9,5,7,8,1]
[22,11,10,7,8,6,9,6,8,6,2,6,8,6,8,6,8,7,8,6,8,1]
[23,13,10,9,8,8,8,9,8,8,8,8,8,8,8,8,8,8,9,8,8,8,1]
[24,12,8,6,9,4,8,3,5,6,7,2,7,6,5,3,8,4,9,5,7,7,8,1]
[25,14,11,10,5,8,8,9,8,4,8,8,8,8,4,8,9,8,8,5,8,8,8,8,1]
[26,13,11,8,9,7,8,7,9,6,8,6,2,6,8,6,9,7,8,7,8,6,8,7,8,1]
[27,15,9,10,9,6,8,8,3,8,8,6,8,8,6,8,8,3,8,8,6,8,8,7,10,8,1]
[28,14,12,7,9,7,4,5,8,7,8,5,9,2,8,5,8,7,8,5,4,7,9,5,10,7,8,1]
[29,16,12,11,10,9,10,8,9,8,8,8,9,8,8,9,8,8,8,9,8,9,9,10,10,8,8,9,1]
[30,15,10,9,6,5,9,7,6,3,8,4,9,8,2,8,9,4,8,3,6,7,9,5,5,8,6,7,9,1]
[31,17,13,11,10,9,9,10,9,8,9,8,8,8,8,8,8,8,8,9,8,8,8,8,8,8,10,8,8,8,1]
[32,16,13,8,10,8,9,4,9,7,8,5,8,7,9,2,9,7,8,5,8,7,9,4,9,8,8,7,8,7,9,1]
[33,18,11,12,10,7,9,10,6,9,3,6,8,8,6,9,9,6,8,8,6,3,9,6,10,8,7,8,9,6,9,9,1]
[34,17,14,10,11,8,9,8,9,7,9,7,8,7,8,8,2,8,8,7,8,7,9,7,8,8,9,7,9,8,9,8,9,1]
[35,19,14,12,7,10,5,9,10,5,8,9,9,4,5,8,9,9,8,5,4,9,9,8,5,8,9,5,9,5,8,10,9,8,1]
[36,18,12,9,11,6,11,6,4,7,9,3,9,7,6,6,10,2,10,6,6,7,9,3,9,7,4,6,10,5,10,7,7,8,9,1]
[37,20,15,13,11,10,10,9,9,9,9,9,8,9,9,9,8,8,8,8,9,8,9,8,9,9,9,9,8,9,10,8,9,9,9,9,1]
[38,19,15,11,11,9,10,8,10,8,9,7,9,7,9,7,10,7,2,7,10,7,9,7,9,7,9,7,10,7,9,7,9,9,9,7,9,1]
[39,21,13,13,12,8,10,11,7,9,9,7,3,9,6,9,9,6,10,9,6,9,9,6,9,3,7,9,9,7,9,10,6,9,9,7,9,9,1]
[40,20,16,10,8,9,10,5,10,4,9,6,9,7,5,4,9,8,8,2,8,8,9,4,5,7,9,6,8,4,9,5,9,7,7,6,9,9,9,1]

real    1m39.927s
user    1m38.547s
sys     0m1.120s

more rows:
[41,22,16,14,12,11,10,11,10,9,9,9,10,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,11,9,9,9,9,1]
[42,21,14,12,12,7,6,9,7,8,10,5,10,3,7,7,10,5,10,7,2,7,10,5,10,7,7,3,10,5,10,8,7,9,5,5,9,7,7,8,9,1]
[43,23,17,14,12,11,12,10,10,10,9,9,10,9,9,9,10,9,10,9,9,9,9,9,9,10,9,9,9,9,9,9,9,9,10,10,9,9,9,9,9,9,1]
[44,22,17,11,13,10,11,7,11,8,4,6,9,9,9,6,9,8,9,6,9,2,9,6,9,8,9,6,9,8,9,6,4,8,9,7,9,8,9,6,9,8,9,1]
[45,24,15,15,9,9,11,10,5,6,10,7,9,9,3,10,9,4,9,6,8,9,9,8,6,9,4,9,10,3,9,9,7,9,6,5,9,9,8,7,10,7,9,10,1]
[46,23,18,13,13,10,11,9,10,8,9,8,9,8,9,9,9,8,9,8,9,8,2,8,9,8,9,8,9,8,9,8,9,8,9,8,9,9,9,8,9,8,9,8,9,1]
[47,25,18,15,13,12,11,12,11,10,10,10,9,9,10,9,10,9,9,9,9,9,9,9,9,9,9,9,9,9,9,10,9,9,9,9,9,9,9,9,9,9,11,9,9,9,1]
[48,24,16,12,13,8,11,6,8,9,10,4,10,8,7,3,9,5,9,6,7,7,9,2,9,7,7,6,9,5,9,3,7,8,10,4,10,9,8,5,9,7,9,7,7,8,10,1]
[49,26,19,16,14,12,7,12,11,10,10,10,10,5,9,10,10,9,9,10,5,9,9,9,9,9,9,5,10,9,9,10,10,9,5,9,9,9,9,9,9,5,10,10,9,9,9,9,1]
[50,25,19,14,10,11,13,10,11,5,10,8,9,8,6,9,10,8,9,4,9,8,9,8,2,8,9,8,9,4,9,8,9,9,6,8,9,8,9,5,9,8,9,8,6,8,9,8,10,1]
[51,27,17,16,14,10,12,11,8,10,10,8,10,10,7,9,3,7,9,10,7,10,10,8,9,9,8,10,10,7,10,9,7,3,9,7,10,9,8,10,10,7,9,10,8,10,9,8,10,9,1]
[52,26,20,13,14,11,12,8,11,9,10,7,4,8,10,7,10,9,9,6,9,8,10,6,11,2,11,6,10,8,9,6,9,9,10,7,9,8,4,7,9,8,10,6,10,8,9,7,11,8,10,1]
[53,28,20,17,14,13,12,11,12,11,11,10,10,10,10,10,11,10,9,9,9,9,10,11,11,9,9,11,11,9,9,9,9,9,10,11,10,10,9,10,9,10,11,10,9,10,10,9,11,9,9,10,1]
[54,27,18,15,15,9,12,10,6,9,10,6,11,8,7,8,9,3,9,8,7,8,9,6,11,8,2,8,10,6,9,8,7,8,9,3,9,8,7,8,9,6,9,8,5,8,10,7,9,10,8,8,10,1]
[55,29,21,17,11,13,12,13,11,7,5,10,11,10,6,10,11,9,11,6,9,4,10,9,6,9,9,9,9,6,9,10,4,9,6,10,9,9,9,6,9,10,9,5,7,9,9,9,9,6,10,10,10,10,1]
[56,28,21,14,15,12,8,7,12,9,11,7,11,4,10,5,10,8,9,7,5,8,10,5,9,9,9,2,9,8,9,5,10,8,5,7,9,8,10,5,10,4,11,7,10,9,9,5,7,10,10,7,9,8,9,1]
[57,30,19,18,15,11,14,13,9,11,10,8,10,10,8,10,10,7,3,9,7,10,10,7,10,9,7,10,10,7,9,10,7,9,10,7,9,3,7,10,10,7,10,9,7,9,10,7,10,10,9,9,10,7,10,10,1]
[58,29,22,16,15,12,13,11,12,10,11,9,10,10,10,8,10,9,11,8,10,8,10,8,11,9,11,8,2,8,10,9,10,8,10,8,10,8,11,9,10,8,10,9,10,9,11,10,10,10,10,8,10,8,10,9,10,1]
[59,31,22,18,16,14,13,12,12,11,11,11,10,10,10,10,11,10,9,10,11,9,10,9,9,9,9,9,10,10,9,9,9,9,9,10,9,10,9,9,10,9,9,9,10,9,9,10,10,9,9,9,11,10,9,9,10,10,1]
[60,30,20,15,12,10,13,9,9,6,11,5,10,9,4,7,11,6,10,3,7,8,10,4,6,9,8,8,9,2,9,8,8,9,6,4,10,8,7,3,9,6,11,7,4,9,10,5,10,5,7,8,11,6,7,7,9,9,10,1]
[61,32,23,19,16,14,13,12,12,11,11,11,11,10,10,11,10,10,11,10,9,10,10,9,10,9,10,9,9,9,9,9,9,10,9,10,9,9,10,9,10,10,9,9,10,10,10,10,11,9,10,10,9,9,10,10,10,10,9,10,1]
[62,31,23,17,16,13,13,11,13,10,11,9,11,9,11,10,10,9,11,8,10,9,10,8,10,8,10,8,10,8,2,8,10,8,10,8,10,8,10,9,10,8,11,8,10,8,11,8,11,8,10,8,10,10,10,8,10,8,10,8,10,1]
[63,33,21,19,16,12,9,14,7,12,11,9,10,6,8,10,10,5,10,10,3,10,10,7,10,10,5,6,10,7,10,10,7,10,6,5,10,10,7,10,10,3,10,10,5,10,10,8,6,10,9,10,10,5,10,7,7,10,10,8,10,10,1]
[64,32,24,16,17,13,15,8,12,10,12,8,11,9,10,4,11,9,10,7,10,8,10,5,10,8,10,7,10,9,10,2,10,9,10,7,10,8,10,5,10,8,10,7,10,9,10,4,10,9,10,8,11,8,11,7,10,8,10,7,10,9,10,1]
[65,34,24,20,13,15,14,14,13,8,11,11,5,11,7,11,10,10,10,7,10,10,11,10,6,4,10,10,11,6,10,10,10,10,6,11,10,10,4,6,10,10,10,10,7,10,10,10,11,7,10,5,10,10,6,10,10,10,10,7,10,10,10,10,1]
[66,33,22,18,17,11,14,12,10,10,6,7,11,9,8,10,11,6,10,9,9,3,10,6,10,8,8,8,9,6,9,9,2,9,9,6,9,8,8,8,10,6,10,3,8,9,10,6,9,10,8,8,10,7,5,8,8,9,10,6,10,9,8,9,10,1]
[67,35,25,20,17,15,14,13,13,12,12,11,12,11,11,10,11,10,10,10,10,10,10,10,11,10,10,10,11,10,11,11,10,10,10,10,10,11,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,10,10,10,10,11,10,10,10,10,10,10,1]
[68,34,25,17,17,14,14,10,13,11,11,8,12,9,11,8,4,9,10,7,10,9,10,7,10,8,10,7,10,8,11,8,10,2,10,8,11,8,10,7,10,8,10,7,10,9,10,7,10,8,4,8,10,9,10,7,10,9,10,8,10,9,10,8,10,9,10,1]
[69,36,23,21,18,13,14,13,10,12,12,9,12,11,8,11,11,8,10,11,8,10,3,9,10,11,8,10,9,8,10,9,8,9,9,8,9,10,8,9,9,8,10,10,8,3,10,8,11,10,8,11,11,8,11,10,9,10,10,8,9,10,8,11,10,8,10,10,1]
[70,35,26,19,14,14,10,12,13,7,12,10,11,5,7,9,12,10,10,5,6,8,10,9,7,9,10,4,10,5,10,8,10,9,2,9,10,8,10,5,10,4,10,9,7,9,10,8,6,5,10,8,11,9,7,5,10,9,10,5,10,8,6,10,7,9,10,8,11,1]
[71,37,26,21,18,16,16,15,14,12,12,12,11,11,11,11,10,11,10,11,10,10,10,10,10,10,10,10,11,10,10,11,10,10,10,10,10,10,11,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,10,10,10,12,10,11,10,10,10,10,10,12,10,10,10,1]
[72,36,24,18,18,12,15,9,8,11,12,6,11,11,9,6,12,4,10,7,8,9,10,3,10,9,5,7,10,6,10,6,7,10,10,2,10,10,7,6,10,6,10,7,5,9,10,3,10,9,8,7,10,4,10,6,9,10,10,5,10,10,7,7,10,7,10,8,8,9,10,1]
[73,38,27,22,18,16,15,15,13,13,12,12,11,11,11,11,11,10,10,10,10,11,10,10,10,10,10,10,10,10,11,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,10,10,10,1]
[74,37,27,20,19,15,15,13,14,11,12,10,12,10,11,9,11,9,12,9,10,9,11,9,10,8,10,9,11,9,10,9,10,8,10,8,2,8,10,8,10,9,10,8,11,9,10,8,10,9,10,9,10,9,11,9,10,8,11,9,11,10,10,8,10,9,10,9,10,9,10,9,10,1]
[75,39,25,22,15,14,15,14,11,9,13,10,12,11,5,11,11,8,10,7,8,10,11,9,3,10,8,10,10,4,10,10,8,10,8,8,10,10,8,8,10,8,10,10,4,10,10,8,10,3,9,11,10,8,7,10,8,10,10,5,10,10,8,10,8,8,10,10,8,7,10,8,11,10,1]
[76,38,28,19,19,15,15,11,14,11,12,9,11,10,11,8,12,10,4,8,10,9,11,7,10,9,10,7,10,9,10,7,10,10,10,7,10,2,10,7,10,10,10,7,10,9,10,7,10,9,10,7,10,9,10,7,4,10,10,7,10,9,10,7,10,9,10,9,11,9,10,7,10,9,10,1]
[77,40,28,23,19,17,11,14,14,13,7,12,12,7,12,12,12,11,12,10,6,5,10,12,12,10,10,6,10,10,10,10,5,10,6,12,10,10,10,10,12,6,10,5,10,10,10,10,6,10,10,12,12,10,5,6,10,10,10,12,11,10,7,11,10,5,12,10,10,6,11,10,10,10,10,10,1]
[78,39,26,21,19,13,17,13,11,12,13,8,6,10,9,11,11,7,10,9,8,9,11,7,12,3,9,9,11,6,10,9,8,9,11,6,10,10,2,9,10,6,11,9,8,9,10,6,11,9,9,3,11,7,11,9,8,9,10,7,11,9,8,10,5,6,10,9,8,9,10,7,10,9,8,9,11,1]
[79,41,29,23,20,17,16,16,14,13,12,12,12,12,11,11,11,11,11,11,11,11,11,10,12,10,12,11,10,10,10,11,10,10,10,11,10,10,10,10,10,10,11,10,10,10,11,10,10,10,11,11,10,10,10,10,10,10,10,10,11,10,10,10,10,10,10,11,11,10,10,10,10,11,11,10,10,11,1]
[80,40,29,20,16,16,16,10,15,8,13,9,13,10,8,5,11,10,12,4,12,9,11,6,7,9,10,7,11,5,10,4,10,9,7,8,10,8,10,2,10,8,10,8,7,9,10,4,10,5,11,7,10,9,7,6,10,8,11,4,11,9,10,5,8,9,10,7,12,7,10,6,10,9,7,9,10,9,10,1]
[81,42,27,24,20,15,16,16,9,13,13,10,13,12,9,12,12,6,12,11,8,10,11,8,10,10,3,12,11,8,10,11,8,10,10,6,10,10,8,10,10,8,10,10,6,10,10,8,11,10,8,11,11,3,10,10,8,10,10,8,10,10,6,10,10,8,12,10,8,10,10,7,10,10,10,11,12,8,10,10,1]
[82,41,30,22,20,16,16,14,14,12,13,11,13,10,12,11,11,10,11,9,10,9,11,9,11,10,10,9,12,9,11,9,11,9,10,9,10,9,10,9,2,9,10,9,10,9,10,9,11,9,10,9,11,9,10,9,10,9,10,9,10,9,11,9,10,9,10,9,11,9,11,11,10,9,11,9,11,9,11,9,10,1]
[83,43,30,24,20,18,16,15,15,14,13,13,12,12,12,11,12,11,11,11,11,11,11,10,12,10,10,10,11,10,10,10,10,10,11,10,10,10,10,10,10,10,10,10,10,10,10,11,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,10,10,11,10,10,10,10,10,10,10,10,11,10,10,10,10,10,1]
[84,42,28,21,21,14,12,12,12,12,13,7,12,6,9,9,12,7,11,8,4,10,11,5,10,10,8,3,10,7,10,7,8,10,6,5,10,10,9,7,10,2,10,7,8,10,10,5,6,10,8,7,10,7,10,3,8,10,10,5,11,10,4,8,10,7,10,9,9,5,10,5,10,9,10,7,7,7,10,8,8,9,10,1]
[85,44,31,25,17,18,18,15,15,10,13,13,12,12,8,12,5,11,11,8,11,11,11,10,7,10,12,11,10,7,10,10,10,4,7,10,11,10,10,8,10,10,10,10,8,10,10,11,10,7,4,10,10,10,7,10,11,11,10,7,10,11,11,10,8,10,10,5,11,7,10,10,12,10,8,10,10,11,12,8,10,11,10,10,1]

(55: 28m, 74: 7h28m, 75: 8h5m, 76: 8h41m, 77: 12h10m, 78: < 13h8m, 82: < 23h11m)
-}