从语法到算法:一起来解9×9数独

前言

本文适用于:

  • 程序设计语言初学者
  • 闲得没事想看的神犇

欢迎神犇批评指正。


C++语言程序设计第一学期的课程已经结束了。语法上的东西讲得并不多,只是到指针而已,但是缺乏必要的练习显然是没有效果的——尤其是对于实验课上的一些毒瘤题,确实令人手足无措。

今天我们就通过一个经典的数独问题来介绍回溯搜索,把学到的语法知识转化为算法。

什么是数独

数字(すうじ)は独身(どくしん)に限(かぎ)る。

┌───────┬───────┬───────┐
│ 2 6 3 │ 4 1 8 │ 5 7 9 │
│ 7 8 4 │ 3 5 9 │ 6 2 1 │
│ 9 5 1 │ 6 7 2 │ 4 8 3 │
├───────┼───────┼───────┤
│ 3 9 2 │ 1 4 6 │ 8 5 7 │
│ 6 4 5 │ 8 9 7 │ 3 1 2 │
│ 8 1 7 │ 2 3 5 │ 9 6 4 │
├───────┼───────┼───────┤
│ 5 3 8 │ 7 2 4 │ 1 9 6 │
│ 1 7 9 │ 5 6 3 │ 2 4 8 │
│ 4 2 6 │ 9 8 1 │ 7 3 5 │
└───────┴───────┴───────┘

上图是一个9×9方阵。在这个方阵里,每一行、每一列中都有1~9,每一个3×3的小方阵中也含有不重复的1~9。将这个方阵里面的部分数字挖去,就得到了一个谜题。

为了便于编写程序求解,我们规定被挖去的数字由0表示。那么由上面方阵挖去部分数字而得到的一个数独可能是这样的:

2 0 3 0 0 8 5 0 9
0 0 4 0 0 0 0 0 0
0 0 1 0 0 2 0 0 3
0 9 2 0 4 0 8 0 0
0 0 5 0 0 7 0 1 0
0 0 0 2 0 5 9 0 0
0 0 8 0 0 0 1 0 0
0 7 0 0 0 0 2 0 0
4 0 0 9 0 0 0 0 0

接下来我们就一起来编程解决这个问题。

Continue Reading...

ifanr × SegmentFault 黑客马拉松流水账

引言

9月21日微信弄了个小程序的内测,然后爱范儿就和段错误网一起策划了一场Hackathon,叫做“未来小程序”。

我是九月底被sticnarf撺掇着报名的,在之后的一次微软俱乐部聚会时Democracy343也加入了我们。然后一支队伍就这样组成了。我们在10月5日碰了一次面,分了一下工:我做后端,sticnarf做前后端整合,Democracy343做前端的设计。本来当天准备弄个简单的东西出来试一试,结果项目进度拖着拖着就到了晚上了。就这样我们几乎是啥准备都没做就来到了隔壁一流大学的岛上。

前往爱范儿

6号可以说是起了个大早,乘地铁到了海珠区,一下地铁就能看到广州塔。来到T.I.T.创意园,跟着引导标志一路走就来到了爱范儿广州总部。签到、领取服装和周边,然后就是等待开幕。

T.I.T.创意园大门口
工位上堆放的纪念品

开幕

仪式由爱范儿的CTO何世友主持(后来发现是08级的学长),爱范儿和SF的大佬都做了一番讲话,我们同时也认识了一下参与评审的各位嘉宾。接下来就是愉快的组队时间。由于我们已经组好队,任务就只有起好队名、想好口号和设计队旗了。

最终队伍的名字定为Dog.FOOD,这是我的主意。dogfood在软件工程中指什么想必不用多说。微信搞的这一套私有标准想往原生上面靠,弄得兼容性非常差,并且开发者工具不好用,缺陷也很多。因此dogfood其实是非常切题的。我们的口号呢,是TO BE EXCITED,不论是我们开发者,还是用户,都能EXCITED,这是坠吼的。

爱范儿CTO何世友
我们的队旗

Continue Reading...

给小米手机4更换屏幕

为什么要拆手机

我现在用的小米手机4是很早时候买的。当时米4刚出,还只是支持电信的CDMA2000制式。

这个手机摔过好些次,之前也就是摔出点痕迹来。可到了今年8月某一次摔时,因角度问题摔倒了左上角,屏幕就碎了一小块,并且很奇怪的是下面的3个虚拟按键一块也整齐地没有响应了。

到了9月份,并没有再摔,然而触摸部分的故障变本加厉了起来。首先是最上方有一整条没有响应,接着是中间。到了昨天,可以说超过三分之一的屏幕是按不到的。进开发者工具调出显示触摸坐标,可以看出坏得十分规整。屏幕烂成这样,意味着手机几乎无法使用——想登录一下银行的客户端,都发现输入密码的框我根本点不到。

那么,换屏吧!

Continue Reading...

C++实现的航路计算工具——BravoFinder

前言

很早我就想做一个离线的航路计算程序。

网上有不少模拟飞行航线计算工具,国内有虚航运营网的全球航路查询及飞行计划辅助系统、AIRCN的AIRCN全球航路查询系统,国外有AsaLink的RouteFinder。这些都是大家真切用过的。

全球航路查询及飞行计划辅助系统是老牌了,好用,我接触FS时就是一直用着它来的。然而它的导航数据版本有些老旧,现在还是Cycle 1311。

AIRCN全球航路查询系统是近几年上线的系统,有着全球航路查询及飞行计划辅助系统的影子,且同时支持NAIP和AIRAC数据,用户界面也是体验最好的。AIRCN全球航路查询系统最新的数据版本为Cycle 1606,不能说过时,但也算不上新。

RouteFinder有收费版本,也开放了免费版本。更新得非常勤快,昨天才收到Navigraph发来的数据更新通知邮件,现在它就已经更新到Cycle 1609了。不支持NAIP是一个缺憾之外,也许就是外国网站访问比较慢吧。笑。

这次开工时,看到了GitHub仓库的日期,最后一次提交在2014年。我确实是早有想法的,我想编写一个离线的、用户提供数据的航路查询系统。这一次终于是下定决心,把主要功能完成了。GitHub在这里:Bokjan/BravoFinder。功能还在陆续完善中,我本身提供了一个简陋的CLI方式供大家使用。在编写时考虑到这个小工具可以嵌入其他的项目,有意封装了API,在Intefaces.hpp里。

本项目使用知识共享4.0-署名-非商业性使用国际公共许可证开源。

本文主要对技术方面的细节进行介绍。

数据的导入

概论

考虑到PMDG是使用非常广泛的插件机厂商,程序利用的就是PMDG的数据。

Continue Reading...

免费SSL证书提供商盘点和一些杂谈

前言

近一两年,越来越多的网站采用了全站HTTPS的安全策略。从前,我们感觉使用HTTPS是出于用户安全的考虑;然而现在越来越多地被采用的HTTPS,更多地来说,是为了页面内容的安全。网络劫持的方法可以说是层出不穷,相信不少人都是深受国内运营商困扰,强行插入广告可以说是见怪不怪了。值得一提的是,近两年大家可以发现百度也开始使用HTTPS了,不论是为了用户考虑,还是担心ISP的劫持会影响自己的广告业务,不得不说这个技术啊,是大势所趋。

这个博客其实很长一段时间都是使用HTTPS的,因此本次将要介绍的三家SSL证书提供商的产品我都是真正使用过的。希望论述的内容对大家有所帮助。

本次将要介绍的三家服务商为:

  1. StartCom
  2. WoSign
  3. Let's Encrypt

第二段前言

在正式开始主要内容之前,我还想和大家聊一聊CloudFlare这家公司。大家应该知道,CloudFlare是做CDN的,实力也非常的强大。CloudFlare在提供商业服务的同时,也充分考虑到小网站的需求,提供了免费的方案。CloudFlare的免费方案无疑是成功的,我们能够发现有许多网站都使用了CloudFlare的服务。

Continue Reading...