Tag Archives: math

Simplicity

zen-garden-983809

Programming Praxis 4: Sudoku Solution

Sudoku problems can be perceived as quite complex. Counter-intuitively and from a mathematical standpoint, the solution is actually quite simple. I wrote this solution a while back in Python by pulling together algorithms from a number of sources. But by translating it into Haskell again, I think its acheived a certain Zen-like simplicity and elegance. Or maybe its the homebrew talking.

import Data.List
import Data.Maybe

check :: Int -> Int -> Bool
check i j
	| (f i)/9 == (f j)/9 = True
	| mod (i-j) 9 == 0 = True
	| (f i)/27 == (f j)/27 && (f $ mod i 9)/3 == (f $ mod j 9)/3 = True
	| otherwise = False
	where
		f = fromIntegral

solve :: [Int] -> [Int]
solve s
	| elem 0 s = solve $ a ++ [n | n <- [1..9], elem n e == False] ++ b
	| otherwise = s
	where
		a = take i s
		b = drop (i + 1) s
		i = fromJust $ elemIndex 0 s
		e = [s !! j | j <- [0..80], check i j]
		
main = print $ solve [7,0,0,1,0,0,0,0,0,0,2,0,0,0,0,0,1,5,0,0,0,0,0,6,3,9,0,2,
        0,0,0,1,8,0,0,0,0,4,0,0,9,0,0,7,0,0,0,0,7,5,0,0,0,3,0,7,8,5,0,0,0,0,0,
        5,6,0,0,0,0,0,4,0,0,0,0,0,0,1,0,0,2]