21 Apr

数独的自动推理

写在前面:作为离散数学的实验作业,我选择了研究数独。经过测试发现,数独的自动推理还不算难,我把两种常规的推理思路转化为了计算机代码,并结合了随机性推导,得到了一个解题能力还不错的数独程序。事实上,本文的程序还可以进一步优化,以得到更高能力的数独程序(只需要整理一下代码,加上几个循环和判断即可),但是我实在太懒,没有动力继续弄下去了,就这样先和大家分享吧。最后,笔者认为本文的算法是更接近我们的思维的算法。

数独简介

历史

相传数独源起于拉丁方阵(Latin Square),1970年代在美国发展,改名为数字拼图(Number Place)、之后流传至日本并发扬光大,以数学智力游戏智力拼图游戏发表。在1984年一本游戏杂志《パズル通信ニコリ》正式把它命名为数独,意思是“在每一格只有一个数字”。后来一位前任香港高等法院的新西兰籍法官高乐德(Wayne Gould)在1997年3月到日本东京旅游时,无意中发现了。他首先在英国的《泰晤士报》上发表,不久其他报纸也发表,很快便风靡全英国,之后他用了6年时间编写了电脑程式,并将它放在网站上,使这个游戏很快在全世界流行。

台湾于2005年5月由“中国时报”首度引进, 且每日连载, 亦造成很大的回响。台湾数独发展协会(Taiwan Sudoku Association, 简称 TSA)亦为世界解谜联盟会员。香港是在2005年7月30日由AM730在创刊时引入数独。中国大陆是在2007年2月28日正式引入数独。北京晚报智力休闲数独俱乐部(数独联盟前身)在新闻大厦举行加入世界谜题联合会的颁证仪式,成为世界谜题联合会的39个成员之一。(引用自“中文维基百科”: http://zh.wikipedia.org/wiki/数独

点击阅读全文...

25 Apr

傅里叶变换:只需要异想天开?

在对数学或物理进行事后分析,往往会发现一些奇怪的现象,也有可能得到一些更为深刻有趣的结果。比如本文所要谈及的傅里叶变换,可以由一种“异想天开”的思路得来。

洛朗展式

我们知道,在原点处形态良好的函数,可以展开为泰勒级数
$$f(x)=\sum_{n=0}^{\infty}a_n x^n$$
我们发现,上面的幂都是正的,为什么不能包含$x$的负数次幂呢?比如$\frac{\sin z}{z^2}$展开为
$$\frac{1}{z}-\frac{z}{6}+\frac{z^3}{120}\dots$$
显然也是一件合理的事情。于是,结合复变函数,我们得到解析函数的洛朗展式
$$f(z)=\sum_{n=-\infty}^{+\infty}a_n z^n$$
这是函数的双边展开。其中

点击阅读全文...

30 Apr

当概率遇上复变:随机游走基本公式

笔者发现,有很多概率问题,尤其是独立重复实验问题,如果用生成函数的方法来做,会显得特别方便。本文要讲的“随机游走”问题便是其中一例,它又被形象地叫做“醉汉问题”,其本质上是一个二项分布,但是由于取了极限,出现了很多新的性质和应用。我们先考虑如下问题:

考虑实数轴上的一个粒子,在$t=0$时刻它位于原点,每过一秒,它要不向前移动一格(+1),要不就向后移动一格(-1),问$n$秒后它所处位置的概率分布。

点击阅读全文...

4 May

[问题解答]运煤车的最大路程(更正)

刚刚在浏览卢昌海大师的微博时,发现他微博上有一道比较有趣的题目,于是饶有兴致地思考了一翻,构思了一个答案,希望读者们看看这个答案有问题不?

五一”长假微博很闷,出一道题给博友们解闷:

用重载列车运煤,每次可装1万吨,每行驶1公里耗煤1吨,起点处共有N万吨煤(简单起见N为正整数),请问最远可运至何处(是国营煤老板,成本不计,只要运到的数量大于0就算成功)?并求$N\to\infty$时的渐进形式。

点击阅读全文...

4 Jun

当概率遇上复变:随机游走与路径积分

我们在上一篇文章中已经看到,随机游走的概率分布是正态的,而在概率论中可以了解到正态分布(几乎)是最重要的一种分布了。随机游走模型和正态分布的应用都很广,我们或许可以思考一个问题,究竟是随机游走造就了正态分布,还是正态分布造就了随机游走?换句话说,哪个更本质些?个人就自己目前所阅读到的内容来看,随机游走更本质些,随机游走正好对应着普遍存在的随机不确定性(比如每次测量的误差),它的分布正好就是正态分布,所以正态分布才应用得如此广泛——因为随机不确定性无处不在。

下面我们来考虑随机游走的另外一种描述方式,原则上来说,它更广泛,更深刻,其大名曰“路径积分”。

点击阅读全文...

4 Jun

【备忘】访问Google的方法(更新)

6月13日:更新了一个新的可用IP,不知道能够用多久。

以前大家顶多看到利用这个技巧访问facebook、youtube之类的网站,现在无奈到连Google都得用这个方法访问了。

近日,笔者发现直接输入http://www.google.com.hk无法访问Google搜索,要知道对于学术来说,没有Google是多么严重的事情,很多有用的学术资料,尤其是外文资料,都得靠Google来搜。主观性来说,在学术方面,百度不可能赶得上Google,望其项背都不可能。

点击阅读全文...

10 Jun

两百万前素数之和与前两百万素数之和

标题说了两道比较好玩的编程题,如果读者觉得标题绕的让人眩晕的话,那么让我再说得清晰一点:

两百万前素数之和指的是所有不超过两百万的素数的和;
前两百万素数之和指的是前两百万个素数的和。

我是从子谋的blog中看到这道题目的,前一道题目是Project Euler的第10题,后一道则是我跟子谋探索着玩的。关于子谋的研究和代码,大家可以去他的blog上学习。本文分享一下我自己的想法。

点击阅读全文...

15 Jul

《新理解矩阵6》:为什么只有方阵有行列式?

学过线性代数的朋友都知道,方阵和非方阵的一个明显不同是,对于方阵我们可以计算它的行列式,如果不是方阵的话,就没有行列式这个概念了。在追求统一和谐的数学系统中,为什么非方阵却没有行列式?也许对于这个问题最恰当的回答是——因为不够美。对于非方阵,其实也可以类似地定义它的行列式,定义出来的东西,跟方阵的行列式具有同样的性质,比如某行乘上一个常数,行列式值也就乘以一个常数,等等;而且还可以把其几何意义保留下来。但是,非方阵的行列式是不够美的,因为对于一个一般的整数元素的方阵,我们的行列式是一个整数;而对于一个一般的整数元素的非方阵,却导致了一个无理数的行列式值。另外,一个也比较重要的原因是,单单是方阵的行列式也够用了。综合以上两个理由,非方阵的行列式就被舍弃不用了。

非方阵的行列式不够漂亮

$n$阶方阵的行列式是每个向量的线性函数,它代表着向量之间的线性相关性;从几何上来讲,它就是向量组成的平行n维体的(有向)体积。我们当然期望非方阵的行列式也保留这些性质,因为只有这样,方阵行列式的那些运算性质才得以保留,比如上面说的,行列式的一行乘上一个常数,行列式值也乘上一个常数。我们考虑$m\times n$的矩阵,其中$ m < n $,我们将它看成是$m$个$n$维向量的组合。最简单的,我们先考虑$1\times 2$矩阵的行列式,也就是二维向量$(a,b)$的行列式。

点击阅读全文...