用DLX解sudoku(数独)

最近在做scala99,其中有一道题目P97是sudoku(数独)。一开始我想到的是列举每个空格的可选数字,选择可选数字最少的的格子开始填写。每次填写,修改关联格子的可选数字。再次尝试填写。这里无解条件是存在没有可选数字的格子。还有就是easy或者normal级别的数独一般可选数字都是1个,分批填写很快就能完成。hard或以上就没有那么幸运了,必须猜测然后验证,存在回溯。

这里描述的算法其实就是搜索+启发。启发是选择性地从最少可选数的格子开始。猜测+验证,感觉这个问题属于NP问题。事实上也确实是,而且可以转化为NP完全的精确覆盖问题(Exact Cover),所以这个问题也是NP完全问题。

P97给的答案有两个,第一个就是搜索+启发,第二个是DLX。DLX是Exact Cover的高效解法。本文就是讲如何用DLX来解数独问题的。考虑到scala99上第二个实现大部分都是可变数据,所以我用Java实现了相应算法。

Read More

finagle简单使用

在看awseome-scala的时候,正好看到了twitter的finagle。自己公司里貌似也有那种关注load balance等的解决方案,不过不是很容易理解。考虑到自己之前几个月都在弄电子技术了,重新弄点网络相关的把。

这次的任务是做了一个thrift+finagle的远程服务调用例子。其实不是很难,如果不是连续碰到finagle的坑的话。finagle是twitter开源出来的一个分布式系统解决方案,毕竟是大公司出来的东西,更新频率特别是文档很低,很多文档基本都是几年前,好在有代码……

Read More

rabbitmq在scala下的使用尝试

最近重拾scala,由于某些原因想要尝试了rabbitmq。于是便有了这块代码
刚才重新看了rabbitmq的官网,上面关于scala的客户端的信息貌似更新了?之前那个lift-amqp太旧了,没法使用。不过没关系,这篇就当做了记录下如何在scala的环境下用rabbitmq的Java客户端。如果你想直接用现成的scala客户端,可以参考这里

首先你要安装rabbitmq,这样之后好测试。mac下用brew安装命令是

Read More