当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

sudoku solver in Haskell

发表于: 2012-02-21   作者:bookjovi   来源:转载   浏览:
摘要: 这几天没太多的事做,想着用函数式语言来写点实用的程序,像fib和prime之类的就不想提了(就一行代码的事),写什么程序呢?在网上闲逛时发现sudoku游戏,sudoku十几年前就知道了,学生生涯时也想过用C/Java来实现个智能求解,但到最后往往没写成,主要是用C/Java写的话会很麻烦。   现在写程序,本人总是有一种思维惯性,总是想把程序写的更紧凑,更精致,代码行数最少,所以现

这几天没太多的事做,想着用函数式语言来写点实用的程序,像fib和prime之类的就不想提了(就一行代码的事),写什么程序呢?在网上闲逛时发现sudoku游戏,sudoku十几年前就知道了,学生生涯时也想过用C/Java来实现个智能求解,但到最后往往没写成,主要是用C/Java写的话会很麻烦。

 

现在写程序,本人总是有一种思维惯性,总是想把程序写的更紧凑,更精致,代码行数最少,所以现在解决实际问题时慢慢的不会再用C的思维去看问题了,很多现实中的问题用C去考虑的话会非常复杂,像这个数独,原因是C不具有太强大的抽象能力吧。那OO呢?像Java/Python?很多Java程序员遇到啥问题就直接上面向对象,然后开始疯狂的抽象一大堆类,接着翻开设计模式那本书,从中找几个模式出来,如singleton,factory等,能用上的都用上。OO确实把很多问题模块化了,那模块里面呢?顺着这种思维下去,OO的继承和多态又上来了。结果写出来的程序极为冗长。在这里不是说OO不好,只是不要把OO当做解决一切问题的方法和思维,个人认为OO并不具有强大的抽象能力,像C/++/Java/Python/Ruby等OO语言,本质上还是顺着C的思维走了。

 

说到这里就不能不说FP了,关于FP不想多说,花了几天时间用haskell写了个数独求解程序,可以和C/C++做个比较,如代码行数,可维护性。写这个程序的目的不仅只是好玩,还有就希望用最少的代码行数解决数独,scheme括号太多,C/C++/Java太繁琐,最后决定用haskell来试试,看看haskell的数独版本用了几行代码,结果用了17行(除去空行,board数值定义)

 

 

board = [0,3,4,1,7,0,5,0,0,
         0,6,0,0,0,8,3,0,1,
         7,0,0,3,0,0,0,0,6,
         5,0,0,6,4,0,8,0,7,
         0,1,0,9,0,0,0,6,0,
         3,0,6,0,0,2,0,0,4,
         8,0,0,0,0,9,0,0,2,
         1,0,3,7,0,0,0,9,0,
         0,0,9,0,3,1,7,4,0]



nodup x = (length y) == (length $ nub y) where y = filter (/=0) x
boardlen = round.sqrt.fromIntegral $ length board
pointnum bd answernum = length.last.filter (\x->sum x == answernum) $ inits $ map (\x -> if x /= 0 then 0 else 1) bd

newboard (0:xs) (y:ys) = y:newboard xs ys
newboard (x:xs) s      = x:newboard xs s
newboard s []          = s

pointcheck (row, col) bd = all nodup [map (\x->bd!!(row*9+x)) [0..8], map (\x->bd!!(x*9+col)) [0..8], smallgrid bd] where
                                rowmin = row `div` 3 * 3
                                colmin = col `div` 3 * 3
                                smallgrid bd = [bd !! (row*9+col) | row <- [rowmin..(rowmin+2)], col <- [colmin..(colmin+2)]]

nextanswer answer = filter (pointcheck (row,col) . newboard board) $ map (\x->answer++[x]) [1..boardlen] where
                        point = pointnum board $ length answer
                        (row, col) = divMod point boardlen

sudokuIterate = iterate (concatMap $ nextanswer) [[]]

divide bd = unfoldr (\x -> if x == [] then Nothing else Just (splitAt 9 x)) bd

sudoku = mapM_ (\x -> sequence [putStrLn "answer:", mapM_ print (divide $ newboard board x), putStrLn ""])
                        $ sudokuIterate !! length (filter (== 0) board)

main = sudoku

 

总共17行的haskell代码就搞定了sudoku问题,当然这个版本不是初始版本,是经过了很多次的修改而成的简练版,在网上找了C/C++还有Erlang的版本,代码行数无一少于20行的,那些最少的都有40来行。连Prolog版的往往都20多行。

 

运行结果:

 

*Main> :l algorithm.hs
[1 of 1] Compiling Main             ( algorithm.hs, interpreted )
Ok, modules loaded: Main.
*Main> sudoku         
answer:
[2,3,4,1,7,6,5,8,9]
[9,6,5,4,2,8,3,7,1]
[7,8,1,3,9,5,4,2,6]
[5,9,2,6,4,3,8,1,7]
[4,1,8,9,5,7,2,6,3]
[3,7,6,8,1,2,9,5,4]
[8,4,7,5,6,9,1,3,2]
[1,2,3,7,8,4,6,9,5]
[6,5,9,2,3,1,7,4,8]
 

 

有空还会继续优化上面的程序,看看能否再精简点!(很遗憾,有人竟用了12行haskell代码就解决了)

 

注:用haskell来写sudoku求解除了FP的强大抽象能力外,最主要的就是haskell的lazy特性。

 

 

 

sudoku solver in Haskell

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicate
早就见过数独的题了,一看就头疼,也没认真看过,这里遇见了,好似久违的敌人和朋友,终于可以切磋
一.题目描述 Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells
题目如下: Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells a
LeetCode解题之Sudoku Solver 原题 通过程序来解决数独问题。 注意点: 有且只有唯一解 例子: 输入
翻译 写一个程序来通过填充空格求解数独。 空格用'.'表示。 你可以假定这里只有唯一解。 (示例图片
Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicate
Question: The Sudoku board could be partially filled, where empty cells are filled with the c
一.题目 Valid Sudoku Total Accepted: 29804 Total Submissions: 109584My Submissions Determine
在 Haskell 中是用空格来将函数名与参数分隔的 常用库函数 min 接受两个可比较大小的参数,并返回较
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号