Sudoku Zipper

I will post about an interesting idiom in Functional Programming , that I came across recently – Zipper. zipper provides us with
the ability to traverse pure functional programming data structures with surprising agility and efficiency , without losing the purity.

module Main where

import Sudoku.Parser as P

import Sudoku.Data as D

import System.Environment(getArgs)

import Data.Tree

import Data.Tree.Zipper

The imports are similar to the earlier one but with an additional module loaded – the zipper.

There’s just a minor change in the main, we pass the sudoku to zipperSol, which solves the sudoku and prints the solution.

main = do args <- getArgs

          case args of

            (f:[])   -> do x <- parseSudokuFromFile f

                           zipperSol x

            _        -> do usage

usage = do print "Usage:"

           print "STest <file>"

We create the tree the way we did earlier.

sudokuTree s = Node s (map sudokuTree (explore s))

explore s =  case (getUnfilledCell s) of

               Just (c,pos) -> filter validSudoku [ (fillSudoku s pos val) |  val <- getCells c ]

               Nothing      -> []

getCells (Ttv  lst) = map Sld lst

getCells  x =     [x]

Then, pass it on to the fromTree function of Data.Tree.Zipper module to get a zipper. Thus the below function takes a Sudoku and
constructs a zipper out of it.

sudokuZipper s = fromTree $ sudokuTree s

Now the solution is using Depth First Search. Search for nodes in the tree in depth first manner and if a solution is found, print it and otherwise
report inability.

zipperSol s = case (dfs $ sudokuZipper s) of

                Nothing -> do print "No solution found   "

                (Just x) ->do print  x

The function to perform depth first search is simple too. Given a treeLocation, we check if it is a leaf. If it is a leaf, we need to handle it differently.
Otherwise, we call dfs on the first child of the tree in a recursive manner.
The different handling of the leaf node is this: see, if it is a solution. If it is, report it. Otherwise, delete this leaf and perform the depth first
search on the new tree formed.
Data.Tree.Zipper.delete function returns a May be TreeLoc. The new location will be the right sibling of the treeLoc that we deleted or, if
there’s no right sibling, the parent (which will become a leaf).
it is a leaf node.

dfs :: TreeLoc Sudoku -> Maybe Sudoku

dfs treeLoc = case firstChild treeLoc of

                 Nothing  -> handleLeafNode treeLoc

                 Just x   -> dfs x

handleLeafNode treeLoc =

    case (solvedLoc treeLoc) of

      Just solution -> Just solution

      Nothing ->  case (delete treeLoc) of

                   Nothing -> Nothing

                   (Just x) -> dfs x

solvedLoc :: TreeLoc Sudoku -> Maybe Sudoku

solvedLoc (Loc (Node x _) _ _ _) = if (hasEmptyCells x) then

                                      Nothing

                                   else (Just x)

hasEmptyCells s = case (getUnfilledCell s) of

                    Nothing  -> False

                    Just _   -> True

Elegant and cool. This program is slightly slower than my earlier one ( it takes 9 seconds to solve a sudoku that was solved in 8 seconds by the
earlier, tree based one) and the memory consumption is slightly on the higher side as well. However I can choose my search strategy.
I would be able to move from depth first search to breadth first search or best first search without breaking a sweat.