Dark Magus (![[info]](http://p-stat.livejournal.com/img/userinfo.gif){kind=small} _darkus_) wrote,@ 2006-09-29 10:52:00 |
|
| Entry tags: | ФП |
Задача по ФП: Магические квадраты
Один товарищ поинтересовался о том, как на языке Haskell устраивать переборы для, к примеру, решения задачи о построении магического квадрата
module MagicSquare where
(//) :: Eq a => [a] -> a -> [a]
[] // y = []
(x:xs) // y = if (x == y) then xs
else x:(xs // y)
(///) :: Eq a => [a] -> [a] -> [a]
s /// [] = s
s /// (x:xs) = (s // x) /// xs
magicSquares = [[x1, x2, x3, y1, y2, y3, z1, z2, z3] | x1 <- [1..9],
x2 <- [1..9] /// [x1],
x3 <- [1..9] /// [x1, x2],
y1 <- [1..9] /// [x1, x2, x3],
y2 <- [1..9] /// [x1, x2, x3, y1],
y3 <- [1..9] /// [x1, x2, x3, y1, y2],
z1 <- [1..9] /// [x1, x2, x3, y1, y2, y3],
z2 <- [1..9] /// [x1, x2, x3, y1, y2, y3, z1],
z3 <- [1..9] /// [x1, x2, x3, y1, y2, y3, z1, z2],
x1 + x2 + x3 == y1 + y2 + y3,
x1 + x2 + x3 == z1 + z2 + z3,
x1 + x2 + x3 == x1 + y1 + z1,
x1 + x2 + x3 == x2 + y2 + z2,
x1 + x2 + x3 == x3 + y3 + z3,
x1 + x2 + x3 == x1 + y2 + z3,
x1 + x2 + x3 == x3 + y2 + z1]
Вспомогательные операции
(//) и (///) используются для получения списка с исключённым из него элементом и подсписком соответственно. Впрочем, можно видеть, что решение далеко от изящества. Полный перебор из девяти вложенных друг в друга циклов с семью условиями внутри — это жесть. Кроме того, задача решена очень узко — ищутся только магические квадраты размера | 2 | 7 | 6 |
| 9 | 5 | 1 |
| 4 | 3 | 8 |
И вот вам, адепты ФП из моих читателей, задачка для тренировки мозгов. Решить общую задачу по построению магических квадратов. Само собой, что сумма чисел в ячейках по горизонтали, вертикали и диагонали должна совпадать везде. Кроме того, можно добавить изыску в задачу — пра́вила, описывающие «магичность» квадрата, должны задаваться в некоей функции.
Впрочем, имеется алгоритм для построения магических квадратов с нечётным размером стороны. Только мне не известно, является ли построенный по этому алгоритму магический квадрат единственным (с точностью до поворотов и отражений, естественно).
