Life of Asuwill

main=0

八皇后有多少种解？

什么是八皇后问题？

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。——【百度百科】

如下图所示的摆放方式就是一个满足要求的方案：

八皇后有多少种解？

前面引自百科的资料里也有提到，高斯认为有76种方案，还有人解出有92种方案。到底有多少种方案呢？高斯这么厉害的角色也会出错吗？我今天就想用一小段代码来求解这个问题。不过顺便说一句，人家高斯当年计算可没有计算机帮忙啊，能给出76种方案已经是非常人所能匹敌的。

思路

总思想：暴力破解

步骤一：罗列所有可能的摆放方式；

步骤二：检测某种摆放方式是否满足要求；

步骤一

方式一：罗列摆放方式，第一感觉需要一个矩阵来存储一种状态，因为棋盘是个8 * 8的方格，如果用一个8 * 8的矩阵，有皇后的用1表示，没有皇后的用0，然后再判断这个矩阵是否满足任意两个皇后没有处于同一行同一列或者同一个斜线上。这种表示方式直观，但是如果要罗列这个矩阵所有可能的状态，代价就太大了。因为每个格子都有2种可选状态，总共有64个格子，那么一共有 2^64个状态需要判断，明显这条路是走不通了，果断换一条路吧！

方式二：上面那种方式之所以不行，是因为我们没有充分利用限定条件。满足要求的摆放方式保证了每行每列都只有一个皇后，上面很多种罗列方式明显是不满足的。既然每一行都有一个皇后，那么我们用一个数组column_index[8]来存储每一行的皇后所在的列下标。也就是说 column_index[i]表示第i行的皇后所在的列。column_index如何填充呢？，只需看一下上面的图就知道，数组中必然包含0~7八个数字，而且每个数字必然出现一次，也就是说，一个状态就是0~7的一个排列。比如，上面八皇后的摆放用这种方式表示就是:

column_index = [5, 1, 6, 0, 3, 7, 4, 2]

那么有多少种排列就有多少种状态需要判断，很简单，8个不同数字的排列数有8！=40320种，也就是说我们将需要判断的状态从 2^64降到了四万多。好，四万多个状态对于计算机来说判断就很快了。进入下一步吧。

步骤二 判断是否合法

上面的罗列方式已经确保8皇后不在同一行不在同一列，因此只需要判断是否存在两个皇后在同一个对角线，而这个只需要判断 abs(i - j) == abs(column_index[i] - column_index[j])

好最后看一下代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import  itertools

def is_valid_8_quene(col_index):
  for i in range(8):
    for j in range(8):
      if i != j and abs(i-j) == abs(col_index[i] - col_index[j])
        return False
  return True

def count_8_quene_solutions():
  return sum([1 for p in itertools.permutations(range(8)) if is_valid_8_quene(p)])

if __name__ == '__main__':
  print (count_8_quene_solutions())

最后结果是多少呢？ 我不会告诉你是92的

原文地址：http://jiangdapeng.github.io/blog/2014/03/07/eight-queen-problem/
Written by Asuwill posted at http://jiangdapeng.github.io
版权声明：自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0

一分钟搞定搜索提示——freebase初体验

不相信？看完这篇文章，不管你信不信，反正我是信了！

搜索提示是什么东西，相信大家都用过google或者百度或者其他搜索引擎，当你在搜索框中敲入关键字的时候，通常会有一个搜索词推荐列表，如在google中搜索freebase：

这个东西真的能在一分钟内搞定？我的回答是“差不多吧”。所谓差不多吧，实际上就是还有点差距。差距在哪里就等你自己做出来慢慢去比较。下面正式开始实现了，新建一个index.html文件，内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

<!DOCTYPE html>
<html>
    <head>
        <title> search suggest </title>
        <link type="text/css" rel="stylesheet" href="https://www.gstatic.com/freebase/suggest/4_2/suggest.min.css" />
        <script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.7.1/jquery.js"></script>
        <script type="text/javascript" src="https://www.gstatic.com/freebase/suggest/4_2/suggest.min.js"></script>
        <script type="text/javascript">
        $(function() {
          $("#search").suggest({
          key: 'your-api-key-of-freebase',
          lang:'zh'});
        });
        </script>
    </head>

    <body>
    <input type="text" id="search" placeholder="search"> </input>
    </body>

</html>

好了，一切准备就绪了，请用你最喜爱的浏览器打开这个文件，在出现的搜索框里输入一些关键字试试，就比如freebase吧，如果你还不知道这是个什么。现在你相信了我说的没有？

当然，这都是用的别人的现成的东西构建的，算不上什么真本事。但是，你也可能听到过另外一句话，”不要重复造轮子”，有些时候就应该采用拿来主义，把他人的东西纳为己用，这是对别人成果的肯定！所以我今天想在这里推荐的就是别人做好的东西，做的好东西，那就是——freebase。刚才所做的只是一个基于freebase的jquery插件，叫做freebase search widget。

freebase是google knowledge graph的基础，通俗来说，它是一堆事实的网络集合。它‘知道’神偷奶爸是一部动画电影，哪个公司发行的，哪年上映的，还知道这部电影的另外一个名字叫做卑鄙的我。在这里，存储的不再只是纯粹的字符串，这些字符串代表了某个本体，具有一定的属性。更详细的介绍可以参见freebase官网。

今天这个作为一个探索freebase的开始，后续我将继续深入了解freebase及其它所代表的新一代基于知识的搜索引擎。

原文地址：http://jiangdapeng.github.io/blog/2014/02/17/freebase-search-widget/
Written by Asuwill posted at http://jiangdapeng.github.io
版权声明：自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0

说一说python中的yield

yield是什么？

yield能做什么？

如何用yield

参考文献

  1. 提高你的Python: 解释‘yield’和‘Generators（生成器） http://www.oschina.net/translate/improve-your-python-yield-and-generators-explained

  2. python yield浅析 https://www.ibm.com/developerworks/cn/opensource/os-cn-python-yield/

  3. python关键字yield的解释 https://pyzh.readthedocs.org/en/latest/the-python-yield-keyword-explained.html

原文地址：http://jiangdapeng.github.io/blog/2014/02/16/python-yield/
Written by Asuwill posted at http://jiangdapeng.github.io
版权声明：自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0

基础数据结构与算法——排序

最近几天在重温基础的数据结构和算法，比如基础的排序算法，以及动态规划的应用，也慢慢的在博客上写一个基础的系列吧，作为自己温习的记录。

排序算法

插入排序

虽然插入排序的时间复杂度期望是O（n2)，但是具有实现简单，属于原地排序，并且是稳定排序的特点。之所以将其叫做插入排序，是因为，每一轮操作都是将一个待排序的数插入到一个已经排好序的序列中，过程可以想象将一张扑克牌插入到已经按顺序摆好的扑克牌中，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void insertion_sort(int A[], int low , int high)
{
  for(int i=low+1; i<=high;++i)
  {
      int x = A[i];  // 当前需要排序的数，它之前的数都已经排好序了
      int j = i-1;
      while(j >=low && A[j] > x)
      {
          A[j+1] = A[j];
          j--;
      }
      A[j+1] = x;  // 将 x 放置在正确的位置
  }
}

PAT 1001-1010 题解

前言

PAT 是浙江大学搞出来的一个编程（Programming）能力（Ability）测试（Test），在姥姥的大力推广下，目前也逐渐走上了正道，详细介绍可以直接到官网查看 http://pat.zju.edu.cn/

我断断续续也将上面的题目做得差不多了，想来也应该总结一下，算是给自己一个交代。题解大致的形式将会是每10个（或者少于10个）题目一篇博文，对每个题目而言，会简述题目大意，然后是思路整理，然后是代码链接。我已经完成的题目的代码都在github上，请戳我

1001. A+B Format (20)

题意

按照给定的格式输出两个整数的和：即每三位数一组用逗号分隔，例如 999991 就应该输出为 999,991

思路

简单题，可以将和每次三位取出（即按照1000进制），然后再从高位开始输出即可，注意处理负数，中间合适的位置加上, 主要代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

void format(int  n)
{
  bool neg = false;
  if(n<0)
  {
    neg = true;
    n = -n;
  }
  stack<int> vi;
  do
  {
    vi.push(n%1000);
    n /= 1000;
  }while(n!=0);
  if(neg)
    cout << "-";
  cout << vi.top();
  vi.pop();
  while(!vi.empty())
  {
    int top = vi.top();
    vi.pop();
    printf(",%03d",top);
  }
  cout << endl;
}

完整代码请戳我

Markdown 常用语法

前言

为什么我会出现在标签 pat 下

说起来，是因为，我写第一篇pat题解，用 bundle exec rake generate 的时候，报错了

Liquid Exception: comparison of Array with Array failed in page

Google 了一下，有人说是“每个tag都只使用一次的时候”，这个问题就会出现。我测试了一下，还果真是如此，为了暂时解决这个问题，我只好把pat标签在这篇post里也应用一下了。

标题

这是 H1

1

\# 这是 H1

这是 H2

1

\## 这是 H2

这是 H3

1

\### 这是 H3

这是 H4

1

\#### 这是 H4

区块引用

区块引用1

区块引用2

回到引用1

这是一个标题

  1. 列表1
  2. 列表2

给出一些例子代码：

return shell_exec(“echo $input | $markdown_script”);

列表

无序列表

  • 师叔
  • 师太
  • 春哥
  • 马老师
  • 主席
  • 女王大人
  • 亲王大人

有序列表

  1. 师叔女人1号
  2. 师叔女人2号
  3. 师叔女人3号
  4. 。。。

代码区块

这是普通的段落

这是代码块（行首4个空格或者1个制表符）

区段元素

原文地址：http://jiangdapeng.github.io/blog/2013/10/08/markdown-syntax/
Written by Asuwill posted at http://jiangdapeng.github.io
版权声明：自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0