нужна помощь в написании функции кандидатов в Haskell - PullRequest
Новая
       11

нужна помощь в написании функции кандидатов в Haskell

1 голос
/ 29 ноября 2010

Здравствуйте, взгляните на этот поток, уже обрабатывающий эту тему. А также этот поток может быть интересен.

Я пытаюсь написать функцию 

candidates :: Sudoku -> Pos -> [Int]

, который задан Судоку 

data Sudoku = Sudoku { rows :: [[Maybe Int]] }
 deriving ( Show, Eq )

и позицией (type Pos = (Int, Int)) определяет, какие цифры вы можете написать там, например, в строке судоку, которая уже содержит (1,2,4,7,9, х, х) вы не можете написать ни одно из уже существующих чисел в последнем ряду.Также другой проблемой является проверка высоты и ширины, чтобы числа не встречались более одного раза (обычные правила судоку).Таким образом, какие-либо предложения о том, как начать?

Пример: Судоку> Пример кандидатов (0,2) [4,8]

Ответы [ 2 ]

5 голосов
/ 29 ноября 2010

Я помню, как делал этот проект в моем классе Алгоритмов в колледже. Мой лучший совет, особенно для тех, кто пишет на Haskell для обучения, а не для производства, - писать сверху вниз. Во-первых, спросите себя, что вам нужно сделать, чтобы решить эту проблему? Затем просто запишите это с помощью описательных функций (даже если они еще не существуют). Тогда заглушка в нужных вам функциях. Например, начало может быть: 

candidates :: Sudoku -> Pos -> [Int]
candidates s p = union (rowCands s p) (colCands s p) (blockCands s p)

rowCands :: Sudoku -> Pos -> [Int]
rowCands = undefined
colCands :: Sudoku -> Pos -> [Int]
colCands = undefined
blockCands :: Sudoku -> Pos -> [Int]
blockCands = undefined

С этого момента вы просто начнете описывать сверху вниз, как решить проблему rowCands, пока не ответите на все вопросы. Обратите внимание, что иногда вам захочется написать функцию, похожую на union, но наверняка она уже была написана ранее. Попробуйте проверить http://haskell.org/hoogle. Вы можете искать имена функций или даже печатать подписи. Может быть, где-то уже написано union в стандартных библиотеках?

В качестве интересного вопроса для вас, чтобы ответить на вопрос, какой тип undefined и почему он проверяет тип? Это не специальное ключевое слово; это просто предопределенная функция.

0 голосов
/ 30 ноября 2010

Вот решение, использующее Data.Set. Вы можете использовать S.elems, чтобы получить список, но если вы делаете решение судоку, возможно, вы ищете S.size. 

import qualified Data.Set as S
import Data.Maybe(catMaybes)   

fullSet = S.fromAscList [1..9]

fromJustL = S.fromList . concatMaybes

candidates s x =
  rowSet s x `S.intersection` colSet s x `S.intersection` cellSet s x

rowSet s (i,_) = fullSet `S.difference` fromJustL (s !! i)
colSet s (_,i) = fullSet `S.difference` fromJustL (map (!!i) s)
cellSet s (i,j) = fullSet `S.difference` fromJustL (concatMap (g j) (g i s))
  where
  g i | i < 3     = take 3 
      | i < 6     = take 3 . drop 3
      | otherwise = take 3 . drop 6
...