解决最难数独问题

芬兰科学家因卡拉花了3个月设计出最难数独。

据法国媒体19日报道，芬兰数学天才艾托·因卡拉花费3个月为智力游戏爱好者设计了一个号称“全球最难”的数独游戏，即使你是数独高手，也可能花上几个月的下午茶时间破解这个谜题。

因卡拉是一名环境科学家，拥有应用数学博士学位，平时酷爱玩数独游戏。他说“如果玩家能猜中3~4个数字，他就能在15分钟至半个小时内解开谜题，对于这种幸运儿来说，这根本不是什么‘全球最难的数独游戏’。但从理论上来说，人们必须花好几天时间才能摸出头绪。”

在这个九宫格中，81个格子中已给出23个数字，玩家必须在每一个小九宫格中，分别填上1至9的数字，让整个大九宫格每一列、每一行的数字都不重复。就像下棋那样，这个游戏需要玩家具备预先设想好几步棋子下法的能力。因卡拉教授表示，逻辑思考、耐心和谨慎是解开这个数独之谜的关键。

最近也看到很多报道，说用计算机编程求解需要24小时才能得到结果，所以在这里测试一下。

最难数独问题描述如下，”_”为待确定的数字。

[_,_,5,3,_,_,_,_,_,
8,_,_,_,_,_,_,2,_,
_,7,_,_,1,_,5,_,_,
4,_,_,_,_,5,3,_,_,
_,1,_,_,7,_,_,_,6,
_,_,3,2,_,_,_,8,_,
_,6,_,5,_,_,_,_,9,
_,_,4,_,_,_,_,3,_,
_,_,_,_,_,9,7,_,_]

以前看到《七周七语言：理解多种编程范型》介绍，逻辑编程prolog语言能够快捷得解决这类搜索问题。于是找到相关代码运行研究了一下。

$ gprolog
GNU Prolog 1.4.4 (64 bits)
Compiled May 27 2013, 21:05:43 with llvm-gcc
By Daniel Diaz
Copyright (C) 1999-2013 Daniel Diaz
| ?- ['sudoku.pl'].
compiling /Users/wanghangzhou/sudoku.pl for byte code…
/Users/wanghangzhou/sudoku.pl compiled, 80 lines read – 25385 bytes written, 15 ms

(3 ms) yes
| ?- solve(Solution).

Solution = [1,4,5,3,2,7,6,9,8,8,3,9,6,5,4,1,2,7,6,7,2,9,1,8,5,4,3,4,9,6,1,8,5,3,7,2,2,1,8,4,7,3,9,5,6,7,5,3,2,9,6,4,8,1,3,6,7,5,4,2,8,1,9,9,8,4,7,6,1,2,3,5,5,2,1,8,3,9,7,6,4] ?

计算结果瞬间就给出了，格式化之后的结果如下：

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

 

用Prolog语言来求解数独问题，根据《七周七语言：理解多种编程范型》书中4阶的数独问题求解代码，很容易写出9阶数独问题的求解代码。

下面是搜索得到的代码，代码在解决了号称最难数独问题之后，还给出了生成数独表格的代码。

 

/* sukodu.pl 用Prolog求解数独问题*/
sudoku(Puzzle, Solution):-
Solution = Puzzle,
Puzzle = [
S11,S12,S13,S14,S15,S16,S17,S18,S19,
S21,S22,S23,S24,S25,S26,S27,S28,S29,
S31,S32,S33,S34,S35,S36,S37,S38,S39,
S41,S42,S43,S44,S45,S46,S47,S48,S49,
S51,S52,S53,S54,S55,S56,S57,S58,S59,
S61,S62,S63,S64,S65,S66,S67,S68,S69,
S71,S72,S73,S74,S75,S76,S77,S78,S79,
S81,S82,S83,S84,S85,S86,S87,S88,S89,
S91,S92,S93,S94,S95,S96,S97,S98,S99
],
/*限制数字为1..9*/
fd_domain(Solution, 1, 9),
/*检查行*/
fd_all_different([S11,S12,S13,S14,S15,S16,S17,S18,S19]),
fd_all_different([S21,S22,S23,S24,S25,S26,S27,S28,S29]),
fd_all_different([S31,S32,S33,S34,S35,S36,S37,S38,S39]),
fd_all_different([S41,S42,S43,S44,S45,S46,S47,S48,S49]),
fd_all_different([S51,S52,S53,S54,S55,S56,S57,S58,S59]),
fd_all_different([S61,S62,S63,S64,S65,S66,S67,S68,S69]),
fd_all_different([S71,S72,S73,S74,S75,S76,S77,S78,S79]),
fd_all_different([S81,S82,S83,S84,S85,S86,S87,S88,S89]),
fd_all_different([S91,S92,S93,S94,S95,S96,S97,S98,S99]),
/*检查列*/
fd_all_different([S11,S21,S31,S41,S51,S61,S71,S81,S91]),
fd_all_different([S12,S22,S32,S42,S52,S62,S72,S82,S92]),
fd_all_different([S13,S23,S33,S43,S53,S63,S73,S83,S93]),
fd_all_different([S14,S24,S34,S44,S54,S64,S74,S84,S94]),
fd_all_different([S15,S25,S35,S45,S55,S65,S75,S85,S95]),
fd_all_different([S16,S26,S36,S46,S56,S66,S76,S86,S96]),
fd_all_different([S17,S27,S37,S47,S57,S67,S77,S87,S97]),
fd_all_different([S18,S28,S38,S48,S58,S68,S78,S88,S98]),
fd_all_different([S19,S29,S39,S49,S59,S69,S79,S89,S99]),
/*检查每个3*3单元*/
fd_all_different([S11,S12,S13,S21,S22,S23,S31,S32,S33]),
fd_all_different([S14,S15,S16,S24,S25,S26,S34,S35,S36]),
fd_all_different([S17,S18,S19,S27,S28,S29,S37,S38,S39]),
fd_all_different([S41,S42,S43,S51,S52,S53,S61,S62,S63]),
fd_all_different([S44,S45,S46,S54,S55,S56,S64,S65,S66]),
fd_all_different([S47,S48,S49,S57,S58,S59,S67,S68,S69]),
fd_all_different([S71,S72,S73,S81,S82,S83,S91,S92,S93]),
fd_all_different([S74,S75,S76,S84,S85,S86,S94,S95,S96]),
fd_all_different([S77,S78,S79,S87,S88,S89,S97,S98,S99]),

fd_labeling(Solution).

/*解决号称世界上最难的数独*/
solve(Solution) :-
sudoku([
_,_,5,3,_,_,_,_,_,
8,_,_,_,_,_,_,2,_,
_,7,_,_,1,_,5,_,_,
4,_,_,_,_,5,3,_,_,
_,1,_,_,7,_,_,_,6,
_,_,3,2,_,_,_,8,_,
_,6,_,5,_,_,_,_,9,
_,_,4,_,_,_,_,3,_,
_,_,_,_,_,9,7,_,_
],Solution).

/*生成所有的数独*/
gen(Solution) :-
sudoku([
_,_,_,_,_,_,_,_,_,
_,_,_,_,_,_,_,_,_,
_,_,_,_,_,_,_,_,_,
_,_,_,_,_,_,_,_,_,
_,_,_,_,_,_,_,_,_,
_,_,_,_,_,_,_,_,_,
_,_,_,_,_,_,_,_,_,
_,_,_,_,_,_,_,_,_,
_,_,_,_,_,_,_,_,_
],Solution).