module Exercise03 where

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

-- HA 3.1a) i
selectRow :: [[Int]] -> Int -> [Int]
selectRow [] _ = []
selectRow xss i
  | i < length xss = xss !! i

-- HA 3.1a) ii
selectColumn :: [[Int]] -> Int -> [Int]
selectColumn [] _ = []
selectColumn xss i
  | i < length xss = [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 [] _ = []
selectSquare xss i
  -- i < length xss = [x | xs <- xss, x <- xs, getIndex x xs `elem` columns, getIndex xs xss `elem` rows]
  | i < length xss = [xss !! row !! col | row <- rows, col <- columns]
  where
    rows = [offsetR .. offsetR + root -1]
    offsetR = (i `div` root) * root
    columns = [offsetC .. offsetC + root -1]
    offsetC = (i `mod` root) * root
    root = intRoot (length xss)

--getIndex :: Eq a => a -> [a] -> Int
--getIndex x xs = getIndexAux x xs []

--getIndexAux :: Eq a => a -> [a] -> [a] -> Int
--getIndexAux _ [] _ = -1
--getIndexAux x (y:ys) zs
--  | x == y = length zs
--  | otherwise = getIndexAux x ys (y:zs)

-- HA 3.1b)
isValidSubsection :: [Int] -> Bool
isValidSubsection xs = length l == length (nub l)
  where
    l = [x | x <- xs, x /= 0]

isValidSudoku :: [[Int]] -> Bool
isValidSudoku xss = null [x | x <- [0 .. (length xss -1)], f <- [selectColumn, selectRow, selectSquare], not $ isValidSubsection (f xss x)]

-- HA 3.1c)
setCell :: [[Int]] -> (Int, Int) -> Int -> [[Int]]
setCell xss (j, k) x = [(if j == row then doChange (xss !! row) k x else xss !! row) | row <- [0 .. len -1]]
  where
    len = length xss

doChange :: [Int] -> Int -> Int -> [Int]
doChange xs k n = [(if col == k then n else xs !! col) | col <- [0 .. length xs -1]]

-- HA 3.1d)
{-WETT-}
solveSudoku :: [[Int]] -> [[Int]]
solveSudoku xss
  | not $ isValidSudoku xss = []
  | otherwise = iterOverEmptyCells xss (nextEmptyCell xss (0, 0))

iterOverEmptyCells :: [[Int]] -> (Int, Int) -> [[Int]]
iterOverEmptyCells xss (-1, -1) = xss
iterOverEmptyCells xss (row, col)
  | null possibleNums = []
  | otherwise = possibilitiesHandled --if possibilitiesHandled /= [[-1]] then possibilitiesHandled else []
  where
    possibleNums = getPossibleNums xss (row, col)
    possibilitiesHandled = handlePossibilities xss (row, col) possibleNums 0

handlePossibilities :: [[Int]] -> (Int, Int) -> [Int] -> Int -> [[Int]]
handlePossibilities xss (row, col) possibleNums idx
  | idx == len = []
  | null nextTry = handlePossibilities xss (row, col) possibleNums (idx + 1)
  | otherwise = nextTry
  where
    len = length possibleNums
    nextTry = iterOverEmptyCells nextTrySudoku (nextEmptyCell nextTrySudoku (row, col))
    nextTrySudoku = setCell xss (row, col) (possibleNums !! idx)

nextEmptyCell :: [[Int]] -> (Int, Int) -> (Int, Int)
nextEmptyCell xss (row, col)
  | row == len = (-1, -1) -- no next Cell
  | xss !! row !! col == 0 = (row, col) -- next Cell found at (row,col)
  | otherwise = nextEmptyCell xss (if col == len - 1 then (row + 1, 0) else (row, col + 1))
  where
    len = length xss

getPossibleNums :: [[Int]] -> (Int, Int) -> [Int]
getPossibleNums xss (row, col) = [num | num <- [1 .. len], num `notElem` numsAlreadyThere]
  where
    numsAlreadyThere = nub [x | xs <- [selectRow xss row, selectColumn xss col, selectSquare xss (getSquare (row, col) dimension)], x <- xs, x /= 0]
    dimension = intRoot len
    len = length xss

getSquare :: (Int, Int) -> Int -> Int
getSquare (row, col) dimension = (row `div` dimension) * dimension + (col `div` dimension)

{-TTEW-}

unresolvable :: [[Int]]
unresolvable = 
  [ [2, 0, 0, 1],
    [0, 0, 3, 0],
    [3, 0, 0, 4],
    [0, 1, 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)