module Exercise03 where

import Text.Printf (printf)
import Data.List (intercalate)
{-WETT-}
-- HA 3.1a) i
selectRow :: [[Int]] -> Int -> [Int]
selectRow xss i = xss !! i

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

-- 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 =
  let dim = length xss
      sl = intRoot dim
  in concat [take sl (drop (sl* mod i sl) xs)| xs <- take sl (drop (sl * div i sl) xss)]

-- HA 3.1b)
isValidSubsection :: [Int] -> Bool
isValidSubsection xs
              |length xs==1 = True
              |otherwise = ((head xs `notElem` tail xs)|| (head xs==0)) && isValidSubsection (tail xs) 
 
isValidSudoku :: [[Int]] -> Bool
isValidSudoku xss = totalKNF xss (length xss-1) where
  totalKNF :: [[Int]] -> Int -> Bool
  totalKNF xss 0 = isValidSubsection(selectColumn xss 0) && isValidSubsection(selectRow xss 0) && isValidSubsection(selectSquare xss 0)
  totalKNF xss i = isValidSubsection(selectColumn xss i) && isValidSubsection(selectRow xss i) && isValidSubsection(selectSquare xss i) && totalKNF xss (i-1)
-- HA 3.1c)
setCell :: [[Int]] -> (Int,Int) -> Int -> [[Int]]
setCell xss (j, k) x = concat [take j xss, [newRow (xss !! j) k x]  ,drop (j+1) xss] where
  newRow :: [Int] -> Int -> Int -> [Int]
  newRow xs k x = concat [take k  xs, [x] , drop (k+1) xs]


-- HA 3.1d)
solveSudoku :: [[Int]] -> [[Int]]
solveSudoku xss
            |not (isValidSudoku xss) = []
            |next xss (0,0)== (-1,0) = xss
            |otherwise = solveCell xss (next xss(0,0))

solveCell:: [[Int]]->(Int,Int)->[[Int]]
solveCell xss (r,c) 
              |null(findPossible xss (r,c)) = []
              |otherwise = backtrackPossible xss (r,c) (findPossible xss (r,c))
              
backtrackPossible::[[Int]]->(Int,Int)->[Int]->[[Int]]
backtrackPossible xss (r,c) possible 
              |null possible = []
              |otherwise = if  nextWinning /= [] then nextWinning else backtrackPossible xss (r,c) (tail possible)
              where nextWinning = checkWinning (setCell xss (r,c)(head possible)) (r,c)

checkWinning::[[Int]]->(Int,Int)->[[Int]]
checkWinning xss (r,c)=
              let n = next xss (r,c)
              in if n==(-1,0) then xss else solveCell xss n

next ::[[Int]]->(Int,Int)->(Int,Int)
next xss (r,c)= searchZero xss (r,c) where
  searchZero::[[Int]]->(Int,Int)->(Int,Int) 
  searchZero xss (r,c)
              | r==length xss= (-1,0)
              | c+1==length xss= if (xss!!r)!!c == 0 then (r,c) else searchZero xss (r+1,0)
              | otherwise = if (xss!!r)!!c == 0 then (r,c) else searchZero xss (r,c+1)

findPossible::[[Int]]->(Int,Int)->[Int]
findPossible xss (r,c) = 
            let dim = length xss
                sl  = intRoot dim
                row = selectRow xss r
                col = selectColumn xss c
                sqr = selectSquare xss ((div r sl*sl)+div c sl)
            in [n|n<- [1..dim], n `notElem` row && n `notElem`col && n `notElem` sqr]
{-TTEW-}


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

emptySudoku :: [[Int]]
emptySudoku = [[0,0,0,0],
               [0,0,0,0],
               [0,0,0,0],
               [0,0,0,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)