-- Sudoku Solver

row n  = [ i | i <- [((div n 9)*9)..((div n 9)*9+8)]]

col n = [ i | i <- [(mod n 9), ((mod n 9)+9) .. (mod n 9)+72]]

box n 
    | ((mod n 9) < 3) && (n < 27) = [0,1,2,9,10,11,18,19,20]
    | ((mod n 9) >= 3) && ((mod n 9) < 6) && (n < 27) = [3,4,5,12,13,14,21,22,23]
    | ((mod n 9) >= 6) && (n < 27) = [6,7,8,15,16,17,24,25,26]
    | ((mod n 9) < 3) && (n >= 27) && (n < 54) = [27,28,29,36,37,38,45,46,47]
    | ((mod n 9) >= 3) && ((mod n 9) < 6) && (n >= 27) && (n < 54) =
      	  [30,31,32,39,40,41,48,49,50]
    | ((mod n 9) >= 6) && (n >= 27) && (n < 54) =
      	  [33,34,35,42,43,44,51,52,53]
    | ((mod n 9) < 3) && (n >= 54) =
      	  [54,55,56,63,64,65,72,73,74]
    | ((mod n 9) >= 3) && ((mod n 9) < 6) && (n >= 54) =
      	  [57,58,59,66,67,68,75,76,77]
    | ((mod n 9) >= 6) && (n >= 54) =
      	  [60,61,62,69,70,71,78,79,80]

-- replace xs!!i with x; procedurally xs[i] = x
-- functionally, create a copy of xs with xs[i] replaced by x

replace i x xs = take i xs ++ x:(drop (i+1) xs)

----------------------------------------------------

-- Hint: take initial board b and create a list of boards [b]
-- for each board b and each position i:
-- a.  if b!!i /= 0, do nothing; i.e., add b to output list of boards
-- b.  otherwise, substitue x <- [1..9] for the 0 if the substitution
--     is safe (i.e., x not in row, col, box), potentially creating
--     9 new boards.
-- Note: for all j < i, for all b, b!!j /= 0 and safe
-- for debugging purposes, may wish n to be a parameter; 
-- stop after i >= n

-- sudoku easy1 81  -- call 


----------------------------------------------------

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

          0,0,0,  0,5,0,  6,8,4,        --  3,7,2,  9,5,1,  6,8,4,
          0,0,0,  7,0,2,  0,0,0,        --  8,5,6,  7,4,2,  9,1,3,
          4,1,9,  0,3,0,  0,0,0,        --  4,1,9,  8,3,6,  5,2,7,

          0,0,5,  3,0,8,  0,4,0,        --  1,9,5,  3,2,8,  7,4,6,
          6,0,0,  0,0,7,  0,9,8,        --  6,4,3,  5,1,7,  2,9,8,
          2,0,0,  4,6,0,  3,5,0]        --  2,8,7,  4,6,9,  3,5,1

----------------------------------------------------

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

    2,0,0,  0,0,0,  0,1,8,      -- 2,5,4,  3,6,7,  9,1,8,
    0,6,1,  4,0,2,  5,3,0,      -- 9,6,1,  4,8,2,  5,3,7,
    8,3,0,  0,0,0,  0,0,6,      -- 8,3,7,  9,5,1,  4,2,6,

    1,0,5,  2,0,0,  0,0,0,      -- 1,7,5,  2,3,8,  6,9,4,
    6,0,9,  0,0,0,  3,0,0,      -- 6,8,9,  5,1,4,  3,7,2,
    0,0,0,  6,7,0,  0,0,0       -- 3,4,2,  6,7,9,  8,5,1
    ]

--Read in the game board from the user (into the board parameter).

sudoku :: [Int]->[[Int]]
sudoku board = firstRun 0 [board]

--After reading in the board - firstRun is called - which checks for all elements that are == 0 (elements that can be replaced). Once we have checked all 81 board blocks (0-80), we're done

firstRun :: Int->[[Int]]->[[Int]]
firstRun n s 
	| n > 80 = s
	| (s!!0)!!n == 0 = firstRun (n+1) (buildOK n s)
	| otherwise = firstRun (n+1) s

-- firstRun then calls buildOK -- which esentially makes the a list (of boards), so, when it is finished -- all possible solutions will be returned.

buildOK :: Int->[[Int]]->[[Int]]
buildOK n s = if ((length s) > 1) then (secondRun n (head s))++(buildOK n (tail s)) else (secondRun n (head s))

-- To assist buildOK - secondRun is called, which esentially does the hard "guesswork" of checking to see if we can really place an integer value 1-9 in the current box that we are at. However, buildOK continues passing control down further. secondRun will remove invalid (empty) solutions.

secondRun :: Int->[Int]->[[Int]]
secondRun n s = filter (not . null) [(fitsHere n v s) | v <- [1..9]]

-- Determine if the numbers 1-9 (from above) can fit into any of the board's rows or columns, if it can, replace that spot with the valid solution.

fitsHere :: Int->Int->[Int]->[Int]
fitsHere n v s 
	|(and[(check n v i s)  | i <- [0..8]]) = (replace n v s)
	| otherwise = []

-- Does the number actually fit here?

check :: Int->Int->Int->[Int]->Bool
check n v i s = (s!!((row n)!!i) /= v && s!!((col n)!!i) /= v && s!!((box n)!!i) /= v)

-- FOR ALL FUNCTIONS, n = current board (or position in board in the lowest functions). v = current value. i= possible values, s = master board (solution set in high functions, or current "guess" in lower functions.)