{- |
Description: Sudoku
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
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 = () -> IO ()
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return ()
printSudoku (Just [[Int]]
solution) = (String -> IO ()) -> [String] -> IO ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ String -> IO ()
putStrLn [String]
outputLines
  where outputLines :: [String]
outputLines = ([Int] -> String) -> [[Int]] -> [String]
forall a b. (a -> b) -> [a] -> [b]
map ([String] -> String
unwords ([String] -> String) -> ([Int] -> [String]) -> [Int] -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> String) -> [Int] -> [String]
forall a b. (a -> b) -> [a] -> [b]
map Int -> String
forall {a}. (Eq a, Num a, Show a) => a -> String
showInt) [[Int]]
solution
        showInt :: a -> String
showInt a
0 = String
"."
        showInt a
n = a -> String
forall a. Show a => a -> String
show a
n