{- |
Description: Sudoku
Maintainer: dev@chungyc.org

Part of Ninety-Nine Haskell "Problems".  Some solutions are in "Solutions.P97".
-}
module Problems.P97 (sudoku, sudokuPuzzle, printSudoku) where

import qualified Solutions.P97 as Solution

{- |
A Sudoku puzzle looks like this:

$\begin{array}{|ccc|ccc|ccc|} \hline . & . & 4 & 8 & . & . & . & 1 & 7 \\ 6 & 7 & . & 9 & . & . & . & . & . \\ 5 & . & 8 & . & 3 & . & . & 2 & 4 \\ \hline 3 & . & . & 7 & 4 & . & 1 & . & . \\ . & 6 & 9 & . & . & . & 7 & 8 & . \\ . & . & 1 & . & 6 & 9 & . & . & 5 \\ \hline 1 & . & . & . & 8 & . & 3 & . & . \\ . & . & . & . & . & 6 & . & 9 & 1 \\ 2 & 4 & . & . & . & 1 & 5 & . & . \\ \hline \end{array}$

The solution for the above is:

$\begin{array}{|ccc|ccc|ccc|} \hline 9 & 3 & 4 & 8 & 2 & 5 & 6 & 1 & 7 \\ 6 & 7 & 2 & 9 & 1 & 4 & 8 & 5 & 3 \\ 5 & 1 & 8 & 6 & 3 & 7 & 9 & 2 & 4 \\ \hline 3 & 2 & 5 & 7 & 4 & 8 & 1 & 6 & 9 \\ 4 & 6 & 9 & 1 & 5 & 3 & 7 & 8 & 2 \\ 7 & 8 & 1 & 2 & 6 & 9 & 4 & 3 & 5 \\ \hline 1 & 9 & 7 & 5 & 8 & 2 & 3 & 4 & 6 \\ 8 & 5 & 3 & 4 & 7 & 6 & 2 & 9 & 1 \\ 2 & 4 & 6 & 3 & 9 & 1 & 5 & 7 & 8 \\ \hline \end{array}$

Every spot in the puzzle on a $$9 \times 9$$ board belongs to a row and a column,
as well as to one single $$3 \times 3$$ square, which we will simply call "square" for short.
At the beginning, some of the spots carry a single-digit number from 1 to 9.
The problem is to fill the missing spots with digits in such a way that every number
between 1 and 9 appears exactly once in each row, in each column, and in each square.

Write a function which returns a solution given a Sudoku puzzle.
Both will be expressed as a list of 9 rows.
Each row will be a list of 9 numbers from 0 to 9, where 0 signifies a blank spot.

=== Examples

>>> printSudoku \$ sudoku sudokuPuzzle
9 3 4 8 2 5 6 1 7
6 7 2 9 1 4 8 5 3
5 1 8 6 3 7 9 2 4
3 2 5 7 4 8 1 6 9
4 6 9 1 5 3 7 8 2
7 8 1 2 6 9 4 3 5
1 9 7 5 8 2 3 4 6
8 5 3 4 7 6 2 9 1
2 4 6 3 9 1 5 7 8
-}
sudoku :: [[Int]] -> Maybe [[Int]]
sudoku :: [[Int]] -> Maybe [[Int]]
sudoku = [[Int]] -> Maybe [[Int]]
Solution.sudoku

-- | An example Sudoku puzzle which can be fed into 'sudoku'.
sudokuPuzzle :: [[Int]]
sudokuPuzzle :: [[Int]]
sudokuPuzzle =
[ [ Int
0, Int
0, Int
4, Int
8, Int
0, Int
0, Int
0, Int
1, Int
7 ]
, [ Int
6, Int
7, Int
0, Int
9, Int
0, Int
0, Int
0, Int
0, Int
0 ]
, [ Int
5, Int
0, Int
8, Int
0, Int
3, Int
0, Int
0, Int
2, Int
4 ]
, [ Int
3, Int
0, Int
0, Int
7, Int
4, Int
0, Int
1, Int
0, Int
0 ]
, [ Int
0, Int
6, Int
9, Int
0, Int
0, Int
0, Int
7, Int
8, Int
0 ]
, [ Int
0, Int
0, Int
1, Int
0, Int
6, Int
9, Int
0, Int
0, Int
5 ]
, [ Int
1, Int
0, Int
0, Int
0, Int
8, Int
0, Int
3, Int
0, Int
0 ]
, [ Int
0, Int
0, Int
0, Int
0, Int
0, Int
6, Int
0, Int
9, Int
1 ]
, [ Int
2, Int
4, Int
0, Int
0, Int
0, Int
1, Int
5, Int
0, Int
0 ]
]

-- | Prints a puzzle or solution for 'sudoku' in tabular form.
printSudoku :: Maybe [[Int]] -> IO ()
printSudoku :: Maybe [[Int]] -> IO ()
printSudoku Maybe [[Int]]
Nothing = forall (m :: * -> *) a. Monad m => a -> m a
return ()
printSudoku (Just [[Int]]
solution) = forall (t :: * -> *) (m :: * -> *) a b.
(a -> m b) -> t a -> m ()
mapM_ String -> IO ()
putStrLn [String]
outputLines
where outputLines :: [String]
outputLines = forall a b. (a -> b) -> [a] -> [b]
map ([String] -> String
unwords forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map forall {a}. (Eq a, Num a, Show a) => a -> String
showInt) [[Int]]
solution
showInt :: a -> String
showInt a
0 = String
"."
showInt a
n = forall a. Show a => a -> String
show a
n