はわわーっ

はわわわわっ

数独を解く

数独を解くやつを作ってみた。

import Data.List (intersperse, union)
import System.IO


readBoard :: FilePath -> IO [[Int]]
readBoard file = do
  rows <- fmap lines $ readFile file
  let conv = map (read . (\x -> if x == "." then "0" else x)) . words
  return $ map conv rows

showBoard :: [[Int]] -> IO ()
showBoard []     = return ()
showBoard (r:rs) = do
  let conv = (\x -> if x == "0" then "." else x) . show
  putStrLn $ intersperse ' ' $ concatMap conv r
  showBoard rs


solve :: [[Int]] -> [[Int]]
solve initial = reverse $ head $ solve' 1 []
  where
    solve' 10 rows = [rows]
    solve' i  rows = [rs | r  <- genRows initial rows i,
                           rs <- solve' (i+1) (r:rows)]

genRows :: [[Int]] -> [[Int]] -> Int -> [[Int]]
genRows initial rows i = map reverse $ genRows' 1 []
  where
    genRows' 10 cols = [cols]
    genRows' j  cols = [cs | c  <- if cInit /= 0 then [cInit]
                                   else filter (`notElem` ts) [1..9],
                             cs <- genRows' (j+1) (c:cols)]
      where
        cInit = initial !! (i-1) !! (j-1)
        ts = (initial !! (i-1)) `union` (map (!! (j-1)) initial) `union`
             cols `union` (map (!! (j-1)) rows) `union` boxes
        boxes = concatMap (take 3 . drop (3 * ((j-1) `div` 3))) $
                take 3 . drop (3 * ((i-1) `div` 3)) $ reverse rows


main :: IO ()
main = do
  initial <- readBoard "test.txt"
  showBoard $ solve initial

test.txt

. 8 . . . 3 . . 7
. . 9 . . 5 2 . 4
. 4 2 9 . 6 . 5 .
. 2 6 . 5 . 4 . .
. . 1 8 . . 9 . .
. . 7 4 . 2 8 1 .
. 7 . 5 . 4 1 2 .
5 . 4 6 . . 7 . .
2 . . 3 . . . 4 .

出力結果。

1 8 5 2 4 3 6 9 7
3 6 9 7 1 5 2 8 4
7 4 2 9 8 6 3 5 1
8 2 6 1 5 9 4 7 3
4 5 1 8 3 7 9 6 2
9 3 7 4 6 2 8 1 5
6 7 3 5 9 4 1 2 8
5 1 4 6 2 8 7 3 9
2 9 8 3 7 1 5 4 6