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

を使った解決方法はこちら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
于 2010-11-29T23:17:22.707 に答える