1

嗨，看看 这个线程已经在处理这个主题而且这个线程可能很有趣。

我正在尝试编写一个函数

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

给了一个数独

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

并且位置 ( type Pos = (Int, Int)) 确定您可以在其中写入的数字，例如在已经包含 (1,2,4,7,9,x,x) 的数独行中，您不能在最后写入任何已经存在的数字排。另一个问题是检查高度和宽度，这样数字就不会出现多次（普通数独规则）。那么关于如何开始的任何建议？

示例：数独>候选人示例 (0,2) [4,8]

4

2 回答 2

5

我记得我在大学的算法课上做过这个项目。我最好的建议是写“自上而下”，特别是对于那些使用 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以及为什么要进行类型检查？它不是一个特殊的关键字；它只是一个预定义的功能。

于 2010-11-29T20:13:24.820 回答
0

Here is a solution using Data.Set. You can use S.elems to get the list, but if you are making a sudoku solver, you might be looking for 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
于 2010-11-29T23:17:22.707 回答