推理数独： 将1～9填入空格内，使格内数字满足右侧对应关系：每个圆圈连接的其它数字的和等于右侧对应关系中圆圈内的数字对应的数字。 如右侧为1：30则表示数字1对应线连接的格子中数字的和为30. Neighbourhood:Enter numbers from 1 to 9 once each, into the nine circles. For each number, the sum of all numbers connected to it is given.

Example:

这个问题乍一眼看上去很眼熟，第一感觉可以用拓扑排序来解决。实际上目前也的确用拓扑排序成功解决了几道题。

首先观察这个图的特征，假定所有都是出路，可以观察到

  • 2出路: 4个
  • 3出路: 4个
  • 4出路: 1个

将4出路标记为1，按逆时针递增标记

算法大致是下面这样，只是脑海里按照下面这个思路迭代了几次就能实验出结果了。

1
2
3
4
0. 将图中数字降序排列
1. for 取最大数置于4出路处（即1号位）
2. 	for 取最小数，置于与4出路直连的2个2出路处（即2与7号位）
3. 			迭代求解

答案:

独 数之道的这类题是直接生成了图片再发到浏览器的，看来不能直接读包然后发回结果了。需要进行一下识图了。

参考资料

  1. 独 数之道 锯齿数独->推理数独(需注册登录才能访问)