module Exercise03 where

import Text.Printf (printf)
import Data.List (intercalate)

-- HA 3.1a) i
selectRow :: [[Int]] -> Int -> [Int]
selectRow xss i = xss !! i

-- HA 3.1a) ii
selectColumn :: [[Int]] -> Int -> [Int]
selectColumn [] _ = []
selectColumn (xs:xss) i = xs !! i : selectColumn xss i  

-- HA 3.1a) iii
intRoot :: Int -> Int
intRoot = floor . sqrt . fromIntegral

--return numbers in square as a list. squares are numbered  from left to right and top to bottom
--e.g. :
--[0,1,2]
--[3,4,5]
--[6,7,8]
selectSquare :: [[Int]] -> Int -> [Int]
selectSquare xss i =  fromLines (take n (drop ((i `div` n) * n) xss))
                  where n = intRoot $ length xss
                        fromLines (x:xs)= take n (drop ((i `mod` n) * n) x) ++ fromLines xs
                        fromLines [] =[]
-- HA 3.1b)
isValidSubsection :: [Int] -> Bool
isValidSubsection xs = fst (foldl (\(y,z) b -> ((b==0 || (b>=1 && b<= length xs && b `notElem` z ))&& y, b:z)) (True,[]) xs)

isValidSudoku :: [[Int]] -> Bool
isValidSudoku xss = and [isValid xss i | i<- [0,1..length xss -1]]
                  where isValid xss i = isValidSubsection (selectRow xss i)
                                        && isValidSubsection (selectColumn xss i)
                                        && isValidSubsection (selectSquare xss i)

-- HA 3.1c)
setCell :: [[Int]] -> (Int,Int) -> Int -> [[Int]]
setCell (xs:xss) (0,k) x = (take k xs ++ (x:drop (k+1) xs)) : xss
setCell (xs:xss) (j, k) x = xs : setCell xss (j-1 , k) x
 
-- HA 3.1d)
{-WETT-}
solveSudoku :: [[Int]] -> [[Int]]
solveSudoku xss 
          | not(isValidSudoku xss) = []
          | otherwise = fill xss (0,0) (empties xss)
          where empties xss = sum [1 | xs<-xss , x<-xs , x == 0]

fill :: [[Int]] -> (Int, Int) -> Int -> [[Int]]
fill xss _ 0 = xss
fill xss (i,j) rem
        | (xss !! i)!! j /=0 = fill xss (newI,newJ) rem
        |otherwise = head' [ returned | y <- possibleAt xss (i,j) , let returned = fill (setCell xss (i,j) y) (newI,newJ) (rem-1) , not $ null returned ]
        where newI = (i + 1) `mod` n
              newJ = if newI == 0 then j+1 else j
              n= length xss
              head' [] = []
              head' x = head x

possibleAt :: [[Int]] -> (Int, Int) -> [Int]
possibleAt xss (i,j) = [x | x<-[1..n] , x `notElem` selectRow xss i , x `notElem` selectColumn xss j, x `notElem` selectSquare xss k]
                    where n = length xss
                          k = (i `div` sqrtn) * sqrtn + (j `div` sqrtn)
                          sqrtn = intRoot n
{-TTEW-}

ezSoduku :: [[Int]]
ezSoduku = [[1,0,2,3],[0,3,0,0],[0,2,4,0],[0,0,3,0]]

hardSudoku :: [[Int]]
hardSudoku = [[8,0,0,0,0,0,0,0,0],
              [0,0,3,6,0,0,0,0,0],
              [0,7,0,0,9,0,2,0,0],
              [0,5,0,0,0,7,0,0,0],
              [0,0,0,0,4,5,7,0,0],
              [0,0,0,1,0,0,0,3,0],
              [0,0,1,0,0,0,0,6,8],
              [0,0,8,5,0,0,0,1,0],
              [0,9,0,0,0,0,4,0,0]]

-- Utility method to show a sudoku
-- show sudoku with
-- >>> putStr (showSudoku sudoku)
showSudoku :: [[Int]] -> String
showSudoku xss = unlines $ intercalate [showDivider] $ chunksOf squareSize $ map showRow xss
  where
    size = length xss
    squareSize = intRoot size 
    numberSize = size `div` 10 + 1

    showRowSection xs = unwords $ map (printf ("%0" ++ show numberSize ++ "d")) xs
    showRow xs = intercalate "|" $ map showRowSection $ chunksOf squareSize xs
    showDivider = intercalate "+" $ replicate squareSize $ replicate ((numberSize + 1) * squareSize - 1) '-'

    chunksOf :: Int -> [e] -> [[e]]
    chunksOf i [] = []
    chunksOf i ls = take i ls : chunksOf i (drop i ls)