-- 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.)