-- (c) David F. Place 2006
module Main where
import Data.List 
import Data.Bits
import Data.Array
import Data.Char
import System.IO
import System
import Text.ParserCombinators.Parsec
import Control.Monad

type Sudoku = [[Int]]
type SudokuSets = ([Set],[Set],[Set])
type Blank = (Int,Int,[Int])
type Set = Int

{-

Usage: runghc sudoku.hs [line|grid] 
Input from stdin.  Output to stdout.

line format example:

600500700000060040000003092003002010900000004020100500860300000050010000009004003

grid format example:

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

-}

main :: IO ()
main =
    do 
      args <- getArgs
      input <- hGetContents stdin
      let s = readSudoku args input
      unless (isPossibleSudoku s) 
                 $ error "Input is not a possible sudoku puzzle."
      sudoku s

readSudoku format input =
    case parseSudoku format input of
      Left message -> error (show message)
      Right parse -> parse
    where 
      parseSudoku ["line"] input = 
          parse parseLineFormat "" input
      parseSudoku _ input = 
          parse parseGridFormat "" input

parseValue :: Parser Int
parseValue =
    do 
      ch <- digit
      return $ digitToInt ch

parseLineRow :: Parser [Int]
parseLineRow =
    do 
      digits <- count 9 parseValue
      return digits

parseLineFormat :: Parser Sudoku
parseLineFormat =
    do 
      rows <- count 9 parseLineRow
      return rows

parseGridRow :: Parser [Int]
parseGridRow =
    do 
      digits <- count 9 (do 
                           skipMany space
                           parseValue)
      return digits

parseGridFormat :: Parser Sudoku
parseGridFormat =
    do 
      rows <- count 9 parseGridRow
      return rows

sudoku :: Sudoku -> IO ()
sudoku s = ((mapM_ putStrLn) . (check s) . (take 1) . solveSudoku) s

solveSudoku :: Sudoku -> [Sudoku]
solveSudoku s = maybe (vetSolution s) f $ findBlank s
    where 
      f (_,_,[]) = [] 
      f (r,c,ns) = concatMap (solveSudoku . (replace s r c)) ns 

vetSolution :: Sudoku -> [Sudoku]
vetSolution s 
    | isSolution s = [s]
    | otherwise = []

replace :: Sudoku -> Int -> Int -> Int -> Sudoku
replace s r c x = above++((left++(x:right)):below)
    where
      (above,row:below) = splitAt r s
      (left,_:right) = splitAt c row

findBlank :: Sudoku -> Maybe Blank
findBlank s = case mapBlanks f s of
                [] -> Nothing
                bs -> Just $ minimumBy comp bs 
    where 
      comp (_,_,a) (_,_,b) = compareLength a b
      f r c = (r,c,toList $ blankSet sets r c)
      sets = sudokuSets s

mapBlanks :: (Int -> Int -> a) -> Sudoku -> [a]
mapBlanks f s = concatMap g $ ix s
    where 
      ix xs = zip [0..8] xs
      g (r,row) = concatMap (h r) $ ix row
      h r (c,x) = if x==0
                     then [f r c]
                     else []

compareLength :: [a] -> [a] -> Ordering
compareLength [] [] = EQ
compareLength _  [] = GT
compareLength [] _  = LT
compareLength (_:xs) (_:ys) = 
    compareLength xs ys

sudokuSets :: Sudoku -> SudokuSets                               
sudokuSets s = (rows,columns,cells)
    where 
      rows = map fromList s
      columns = map fromList $ transpose s
      cells = map fromList $ cellContents s

universe :: Set
universe = fromList [1..9]

blankSet :: SudokuSets -> Int -> Int -> Set
blankSet (rows,columns,cells) r c = universe `xor` constraints
    where 
      constraints = (cells !! (cIx r c)) .|. (rows !! r) .|. (columns !! c)

cellContents :: Sudoku -> [[Int]]
cellContents s = concatMap f $ h s
    where 
      f [a,b,c] = zipWith3 g (h a) (h b) (h c)
      g a b c = a++b++c
      h = takeBy 3

cIx :: Int -> Int -> Int
cIx r c = cells ! (r,c)

cells :: Array (Int, Int) Int
cells = array ((0,0),(8,8)) inits
    where 
      inits = [((r,c),cellIndex r c) | r <- ns, c <- ns]
      ns = [0..8]

cellIndex r c = 3 * (div r 3) + (div c 3)

showSudoku :: Sudoku -> String
showSudoku s = stretch . (intersperse ["---+---+---\n"]) . (stitch knot) . gather $ s
    where 
      sewRow = stretch . (intersperse ["|"]) . (stitch show) . gather
      knot r = (sewRow r)++['\n']
      stretch = concat . concat
      stitch f = map (map f)
      gather = takeBy 3

check puzzle [] = [showSudoku puzzle,"No solutions."]
check puzzle [solution]
      | solution `solves` puzzle = 
          ["Puzzle:",showSudoku puzzle,"Solution:",showSudoku solution]
      | otherwise = ["Program Error.  Incorrect Solution!"]

empty :: Set
empty = 0

fromList :: [Int] -> Set
fromList xs = foldl' setBit empty xs

toList :: Set -> [Int]
toList set = foldl' f [] [9,8..1]
    where
      f z x
        | testBit set x = x:z
        | otherwise = z

solvedSudokuSets :: SudokuSets
solvedSudokuSets = (sets,sets,sets)
    where 
      sets = replicate 9 universe

isSolution :: Sudoku -> Bool
isSolution s = (sudokuSets s) == solvedSudokuSets

isPossibleSudoku :: Sudoku -> Bool
isPossibleSudoku s = rows && columns && cells
    where
      rows = all noReps s
      columns = all noReps $ transpose s
      cells = all noReps $ cellContents s
      noReps xs = snd $ foldl' f (empty,True) xs
      f z@(_,False) _ = z
      f z 0 = z
      f (set,_) x | testBit set x = (set,False)
                  | otherwise = (setBit set x,True)

solves :: Sudoku -> Sudoku -> Bool
solves a b = isSolution a && comp a b
    where 
      comp a b = all p $ zip (concat a) (concat b)
      p (_,0) = True
      p (solution,puzzle) = solution == puzzle

takeBy :: Int -> [a] -> [[a]]
takeBy n xs = unfoldr f xs
    where 
      f [] = Nothing
      f xs = Just $ splitAt n xs
