Recursive Backtracking Haskell

Question

Alright so I am attempting to create a Sudoku Solver in Haskell but I'm getting an error saying that I couldn't match the expected type [[Int]] with the actual type IO (). Here is my attempt at the recursive solver, the error message, and other relevant pieces of code:

Recursive Solver Attempt:

test i j q s_board = if ((valid_row i q s_board )&&(valid_column j q s_board)&&  (valid_sub_board i j q s_board)) then (solve (set_value i j q s_board)) else s_board

foo i j s_board = if ((get_value i j s_board) == 0) then [test i j q s_board | q <- [1..9]] else s_board  

solve s_board = if (full_board s_board) then (print_board s_board) else [foo i j s_board | i <- [0..8], j <- [0..8]]

This question would be extremely long if I included all the definitions for the valid column, row, etc. functions, but I've checked to make sure those work. With this code I'm getting the following error message:

 Couldn't match expected type `[[Int]]' with actual type `IO ()'
 In the return type of a call of `print_board'
 In the expression: (print_board s_board)
 In the expression:
   if (full_board s_board) then
       (print_board s_board)
   else
       [foo i j s_board | i <- [0 .. 8], j <- [0 .. 8]]

Also here is the code that I'm using to print my board:

 -- showLine: this function provides formating for a single row 
showLine :: [Int] -> String
showLine = intercalate " | "
         . map unwords
         . chunksOf 3
         . map show

-- showBoad: this function provides formating for the entire board       
showBoard :: [[Int]] -> String
showBoard = intercalate "---------------------\n"
          . map unlines
          . chunksOf 3
          . map showLine


-- print_board: this function is meant to print out the entire board 
print_board :: [[Int]] -> IO ()   
print_board s_board = putStrLn $ showBoard s_board

Do you guys see what's the problem with what I have so far. I'm totally new to Haskell and this is the first real program that I've attempted. Any help would be greatly appreciated.

Daniel Fischer · Accepted Answer · 2012-11-29 04:19:30Z

The two branches of an if must have the same types, but in

if (full_board s_board) then
    (print_board s_board)
else
    [foo i j s_board | i <- [0 .. 8], j <- [0 .. 8]]

the True branch has type IO (), while the False branch is a list of things (boards, in this case probably), so the type is [a], if foo :: Int -> Int -> [[Int]] -> a.

You should separate concerns, the recursive backtracking should give you a list of (full) boards, the printing should be done from another context that calls solve.

My suggestion would be something along the lines of

type Grid = [[Int]]

solve :: Grid -> [Grid]
solve s_board = if full_board s_board
                    then [s_board]    -- full means no branches, singleton list
                    else concat [foo i j s_board | i <- [0 .. 8], j <- [0 .. 8]]

test :: Int -> Int -> Int -> Grid -> [Grid]
test i j q s_board
    | valid_row i q s_board
      && valid_column j q s_board
      && valid_sub_board i j q s_board = solve $ set_value i j q s_board
    | otherwise = []

foo :: Int -> Int -> Grid -> [Grid]
foo i j s_board
    | get_value i j s_board == 0 = concat [test i j q s_board | q <- [1 .. 9]]
    | otherwise                  = []

so each of these functions returns a list of Grids, and a dead-end is pruned by returning an empty list of solutions that can be reached from the current grid. When there is no dead-end yet diagnosed, all allowed combinations are tried.

You could then have

solve_and_print :: Grid -> IO ()
solve_and_print s_board = case solve s_board of
                            [] -> putStrLn "Sorry, that board had no solution."
                            (g:_) -> print_board g

But, that would produce the same solutions multiple times, and be terribly inefficient for an exhaustive search, since evry combination of guesses would be made in all possible orders.

So, let's take a look at how we could make it more efficient. We can prune the permutations and repetitions of solutions in the result list, if we have an algorithm to choose the next position at which we guess a value. The simplest such algorithm is to pick the first free cell. So let s write a function to find the free cells of a grid.

free_cells :: Grid -> [(Int,Int)]
free_cells s_board = [(i,j) | i <- [0 .. 8], j <- [0 .. 8], get_value i j s_board == 0]

With that, we also have a test whether the grid is full, full_board = null . free_cells, by the way. So we can start our solving

solve :: Grid -> [Grid]
solve s_board
    | null frees = [s_board]
    | otherwise  = guesses s_board (head frees)
      where
        frees = free_cells s_board

Next, we find the values we might place in the cell (i,j),

possible_values :: Grid -> (Int, Int) -> [Int]
possible_values s_board (r,c) = [q | q <- [1 .. 9], isPossible s_board q]
  where
    isPossible v = valid_row r v s_board
                   && valid_column c v s_board
                   && valid_sub_board r c v s_board

and place them in the cell and proceed further

guesses :: Grid -> (Int, Int) -> [Grid]
guesses s_board (r,c) = [solution | v <- possible_values s_board (r,c)
                                  , solution <- solve $ set_value r c v s_board]

Faiz · Accepted Answer · 2012-11-29 07:07:08Z

If you're new to Haskell, it's a good idea to take your time before you deal with Monads. And monads are needed for IO.

It would be a good idea to first get a working program together without using the IO monad (putStrLn etc). Just load your program in ghci and simply call your functions. When you get comfortable with that, and you have a function on the REPL that gives you your answer, you can think about printing it to STDOUT (interacting with the 'world' - Haskell demands some understanding of monads for this).

So take your solve function for starters:

Let solve do just that - not more. So instead of doing the IO right here, like:

solve s_board = 
  if (full_board s_board) then (print_board s_board) 
  else [foo i j s_board | i <- [0..8], j <- [0..8]]

The problem is that the if and the else clause do not have the same type. The else returns a [[Int]]; and the if an IO monad (the result of print_board is not [[Int]])

Change it to:

-- sometimes it helps to be explicit - solve takes a puzzle, returns a solved one.
solve :: [[Int]] -> [[Int]]  
solve s_board = 
  if (full_board s_board) then s_board                -- type of s_board is [[Int]]
  else [foo i j s_board | i <- [0..8], j <- [0..8]]   -- and so is this

Simply return the result. Then you mess with solve within ghci, keep fixing your program and re-loading it until it works, and once it does, just write a function to call solve with the desired arguments and print it.

So once you've got the real meat of your program working, you can tackle the distraction of IO:

print_board s_board = putStrLn $ show $ solve s_board

Then this would make a good next step for reading: http://www.haskell.org/tutorial/io.html

Collectives™ on Stack Overflow

Recursive Backtracking Haskell

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related