Найдите 9 блоков 3x3 на доске судоку (Haskell)

Я изучаю Haskell, и я решил заняться небольшим решателем судоку в качестве проекта. Я использовал это задание в качестве guide, и я недавно столкнулся с подзадачей D2, которая заключается в создании функции, которая будет генерировать блоки судоку (9 сеток 3x3) из доски судоку (сетка 9x9).

Я начал писать следующий код, но быстро понял, что это ужасная идея. Это неуклюжий код, который не является идиоматичным Haskell (на мой взгляд) и полностью нарушает принцип DRY.

type Block = [Maybe Int]
data Sudoku = Sudoku [[Maybe Int]]

blocks :: Sudoku -> [Block]
blocks (Sudoku rs) = block1 : block2 : block3 : block4 : block5 : block6 : block7 : block8 : block9 : []
  where block1 = [(rs!!0)!!0] ++ [(rs!!0)!!1] ++ [(rs!!0)!!2] ++ [(rs!!1)!!0] ++ [(rs!!1)!!1] ++ [(rs!!1)!!2]++ [(rs!!2)!!0] ++ [(rs!!2)!!1] ++ [(rs!!2)!!2]  
        block2 = ...
        block3 = ...
        ...

Мне было интересно, как написать более краткую и идиоматическую функцию для выполнения задачи? Как бы вы ее реализовали? Любые идеи приветствуются!

Я также консультировался с этим предыдущим и, возможно, связанный с этим вопрос SO, но я не был уверен, как преобразовать pythonic-решение в Haskell и нужно ли мне вообще это делать. Я также видел этот вопрос, но я по-другому структурировал свою доску судоку.

Весь мой текущий код можно найти здесь. Кроме того, дайте мне знать, если я могу что-то уточнить.


haskell sudoku
person 2016rshah    schedule 11.07.2015    source источник

Ответы (3)


arrow_upward
3
arrow_downward

Сначала напишите функцию groupBy3, которая группирует список по трем элементам:

groupBy3 :: [a] -> [[a]]

Затем используйте следующую цепочку операций:

  • map groupBy3
  • transpose
  • concat
  • groupBy3
  • map concat

Написано на моем телефоне, поэтому не проверено, но должно быть близко.

Обновление: я проверил, что это работает:

groupBy3 (a:b:c:ds) = [a,b,c] : groupBy3 ds
groupBy3 []         = []
groupBy3 as         = [ as ]  -- won't happen

boxes =  map concat . groupBy3 . concat . transpose . map groupBy3

grid = [ [ [i,j] | j <- ['1'..'9'] ] | i <- ['a'..'i'] ]

test1 = boxes grid
person ErikR    schedule 11.07.2015
comment
Хорошо, отлично, код работает, но не могли бы вы добавить немного пояснений к вашему решению? - person 2016rshah; 12.07.2015
comment
Просто проследите выполнение — сначала посмотрите на map groupBy3 boxes, затем на transpose $ map groupBy3 boxes, затем на concat $ transpose $ map groupBy3 boxes и т. д., и вы увидите, как это работает. И если вы нашли этот ответ полезным, мы будем признательны за голосование. - person ErikR; 12.07.2015
comment
Спасибо, я собираюсь добавить редактирование с подписями типов и кодом, который я действительно использовал, и всем остальным, если вы не возражаете. - person 2016rshah; 12.07.2015

arrow_upward
0
arrow_downward

Не точный ответ для этой проблемы, но вам гораздо лучше использовать массивы, а не списки. Поскольку вам нужно изменить элементы, вы, вероятно, захотите использовать изменяемые массивы.

Затем вы можете реализовать блоки как «представления» базового массива, просто применяя различные смещения к операциям с индексами, нет необходимости их копировать.

person Clinton    schedule 12.07.2015
comment
Решатели судоку — это одна из проблемных областей, где Data.Map обычно обеспечивает лучшую производительность, чем изменяемые массивы (поскольку некоторые головоломки судоку не могут быть решены без проб и ошибок, и в целом, чем проще решатель, тем больше проб и ошибок он будет использовать на данная головоломка) - person Jeremy List; 15.07.2015

arrow_upward
0
arrow_downward

Другой подход, хотя, возможно, и не такой элегантный, как принятый ответ:

map concat [(map  (take 3 . drop i) . (take 3 . drop j)) grid | i <- [0, 3, 6], j <- [0, 3, 6]]

где grid — сетка судоку 9x9.

person Aky    schedule 06.01.2017