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 (ys:yss) i = ys !! i : selectColumn yss 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 = squareHelp rss c s s
    where s = intRoot (length (head xss))
          r = ceiling ((fromIntegral (i+1) / fromIntegral s)-1) * s
          c = mod i s * s
          rss = removeRows xss r

squareHelp :: [[Int]] -> Int -> Int -> Int -> [Int]
squareHelp _ _ 0 _ = []
squareHelp xss i r s = select (head xss) (i+s) s ++ squareHelp (tail xss) i (r - 1) s

removeRows :: [[Int]] -> Int -> [[Int]]
removeRows xss r | r <= 0 = xss
removeRows (_:xss) r = removeRows xss (r-1)

select :: [Int] -> Int -> Int -> [Int]
select _ _ 0 = []
select xs i c = xs !! (i - c) : select xs i (c-1)

-- HA 3.1b)
isValidSubsection :: [Int] -> [Int] -> Bool
isValidSubsection (x:xs) nbs = (x `elem` nbs || x == 0) && isValidSubsection xs [n | n <- nbs, n /= x]
isValidSubsection [] _ = True

isValidSudoku :: [[Int]] -> Bool
isValidSudoku xss = validRows xss && validColumns xss s && validSubsections xss s
    where s = length (head xss)

validRows :: [[Int]] -> Bool
validRows (xs:xss) = isValidSubsection xs [1..(length xs)] && validRows xss
validRows _ = True

validColumns :: [[Int]] -> Int -> Bool
validColumns xss i | i /= 0 = isValidSubsection (selectColumn xss (i-1)) [1..(length (head xss))] && validColumns xss (i-1)
                   | i == 0 = True

validSubsections :: [[Int]] -> Int -> Bool
validSubsections xss i | i /= 0 = isValidSubsection (selectSquare xss (i-1)) [1..(length (head xss))] && validSubsections xss (i-1)
                       | i == 0 = True

-- HA 3.1c)
setCell :: [[Int]] -> (Int,Int) -> Int -> [[Int]]
setCell (xs:xss) (j, k) x | j /= 0 = xs:setCell xss (j-1,k) x
                          | otherwise = setColumn xs k x:xss

setColumn :: [Int] -> Int -> Int -> [Int]
setColumn (x:xs) i n | i /= 0 = x:setColumn xs (i-1) n
                     | otherwise = n:xs

-- HA 3.1d)
{-WETT-}
solveSudoku :: [[Int]] -> [[Int]]
solveSudoku xss
    | not (isValidSudoku xss) = []
    | otherwise = solve xss (0,0) (length (head xss) - 1)

solve :: [[Int]] -> (Int, Int) -> Int -> [[Int]]
solve xss (x,y) size
    | val /= 0 = if y < size then solve xss (x,y+1) size else
                 if x < size then solve xss (x+1,0) size
                 else if solved then xss else []
    | null cs = []
    | y <= size && x <= size = try xss (x,y) cs size
    | x == size && y == size + 1 = if solved then xss else []
    where cs = candidates xss (x,y)
          val = (xss !! x) !! y
          solved = isSolved xss

try :: [[Int]] -> (Int,Int) -> [Int] -> Int -> [[Int]]
try xss pos (c:cs) s = if null yss then try xss pos cs s else yss where yss = solve (setCell xss pos c) (0,0) s
try _ _ [] _ = []

candidates :: [[Int]] -> (Int,Int) -> [Int]
candidates xss (j,k) = cs
    where us = selectRow xss j ++ selectColumn xss k ++ selectSquare xss (square (j,k) (intRoot (length (head xss))))
          cs = [n | n <- [1..(length (head xss))], n `notElem` us]

square :: (Int,Int) -> Int -> Int
square (j,k) s = div k s + div j s * s

isSolved :: [[Int]] -> Bool
isSolved (xs:xss) = 0 `notElem` xs && isSolved xss
isSolved _ = True
{-TTEW-}

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)