Editing Sudoku (section)

== Chaining style Solver ==
  
  by jinjing

It uses [http://github.com/nfjinjing/projectt/tree/master/T/Snippets.hs some snippets] and the [http://github.com/nfjinjing/projectt/tree/master/T/Hack/Dot.hs dot hack]

<haskell>
import Prelude hiding ((.))
import T.T
import List
import Data.Maybe
import Data.Char
import Data.Map(keys, elems)
import qualified Data.Map as Map

row i = i `div` 9
col i = i `mod` 9
row_list i positions = positions.select(on_i_row) where
  on_i_row pos = pos.row  == i.row
col_list i positions = positions.select(on_i_col) where
  on_i_col pos = pos.col == i.col

grid_list i positions = positions.select(on_same_grid i)

on_same_grid i j = on_same_row_grid i j && on_same_col_grid i j

on_same_row_grid i j = ( i.row.mod.send_to(3) - j.row.mod.send_to(3) ) == i.row - j.row
on_same_col_grid i j = ( i.col.mod.send_to(3) - j.col.mod.send_to(3) ) == i.col - j.col

board = 0.upto 80
choices = 1.upto 9

related i positions = 
  positions.row_list(i) ++ positions.col_list(i) ++ positions.grid_list(i)
values moves positions = positions.mapMaybe (moves.let_receive Map.lookup)

possible_moves i moves = 
  let positions = moves.keys in
    choices \\ positions.related(i).values(moves)
  
sudoku_move moves = 
  let i = moves.next_pos in
    moves.possible_moves(i).map(Map.insert i).map_send_to(moves)

next_pos moves = (board \\ moves.keys)
  .label_by(choice_size).sort.first.snd where
    choice_size i = moves.possible_moves(i).length

solve solutions 0 = solutions
solve solutions n = solve next_solutions (n-1) where
  next_solutions = solutions.map(sudoku_move).concat

parse_input line = line.words.join("")
  .map(\c -> if '1' <= c && c <= '9' then c else '0')
  .map(digitToInt).zip([0..]).reject((==0).snd).Map.fromList

pretty_output solution = solution.elems.map(show).in_group_of(9)
  .map(unwords).unlines

sudoku line = solve [given] (81 - given.Map.size).first.pretty_output
  where given = parse_input line
</haskell>