首页 > Mathematica > Crossword Puzzle Maker

Crossword Puzzle Maker

2015年2月16日 发表评论 阅读评论

crossword-mind之前找OS X游戏的时候在一个忘记了什么网站上看到了“Black ink”的Crossword Puzzle游戏，中文就是纵横字谜啦，不过好贵，而且我周围基本没见过有人玩过（感觉上一次见人玩大概就是无数年前Big Bang第一季第一集的时候了。。），自己更加没有刚需，所以就没理了；

然后某天晚上躺在床上脑洞的时候突然想到。。。啊咧，Mathematica的DictionaryLookup函数不是有全部的英语单词么？WordData不是可以获得单词的各种信息，包括Definition么？那我是不是可以利用这个生成单词列表，然后设计一个算法自动构造出一个Crossword Puzzle的谜题来？然后以前玩绘制Pokemon图鉴的时候玩过Grid这个屌炸天的函数，还可以用Dynamic来做一些联动的动态操作，so，本文就是这个脑洞的实现。。

生成单词列表

其实我自己从来没玩过Crossword Puzzle。。(所以我为什么会想到做这种东西)，凭直觉大概觉得单词不会太长，也不会太短。。。。吧。。。。

于是，先找出所有单词里面长度4~7的单词：
1

Mathematica Code

随便看了一下，发现其实有一大部分比例单词第一个字母是大写，而且不是常用词，计划把他们过滤掉，另外，用WordData的时候也发现不是所有词都可以获取到Definition的，这些词也要扔掉！

首先，WordData第一次运行需要从W|A上面下载一些云上的数据，所以可以随便搞个单词来先把数据抓回来：
2

Mathematica Code

上面这个运行一下，等它下载完就可以了。

而且返回来的数据我们要获取其中Definition那部分，所以需要准备一个函数来获取定义：
3

Mathematica Code

然后过滤掉首字母大写和没定义的：
4

Mathematica Code

接下来随机找出我们指定数目的单词即可：
5

Mathematica Code

wordlist即所谓求。

构造谜题

构造谜题这个算法其实不难想，随便脑补一下大概就可以想到了，但是我发现这个算法Mathematica实现起来实在是。。。太尼玛艰难了，当然，我模仿别的语言，用各种For，Table，If函数确实可以翻译出来，但是既然不美，就索性不要去创造！【后来我想了想，可能是我mma在使用模式匹配上面的功力不够】

so，我用python实现了一下，思路很简单，就是随便挑一个单词放棋盘上，然后再不断地找下一个单词，在合适的位置放上去，递归求解就是了；

这个算法用python实现起来很快，我写的第一个可以输出结果的代码，加上空行注释，100行都不到，后面增加了一些结果打印函数，迭代中每次随机找单词和随机找位置，把结果导出到文本以便后期Mathematica调用，代码也是150行都不到。。

但是吐个槽，虽然python实现这种东西代码量远远小于C++，但是再给我一次机会，再也不敢用python了，对于这种需要迭代求解，每次往递归函数里面传进各种标记信息变量的时候，python这种不允许指定是值传递还是引用传递的语法，你就只能用a[:]来值传递一维的list，用copy.deepcopy来值传递二维list，难受死了，不是写得难受，而是感觉代码失去了某种美感。。

代码如下：

import copy,sys,random

# 单词列表
wordstring = "buckles,killed,rubato,collect,......."

WORDPOOL = wordstring.split(',')
random.shuffle(WORDPOOL)
BOARD_SIZE = 33

class CRecord:
    def __init__(self, m_size,m_wordpool):
        self.indexTable = [set() for x in range(26)]
        self.board = [['-' for x in range(m_size)] for x in range(m_size)]
        self.dirFlag = [[0 for x in range(m_size)] for x in range(m_size)]
        self.wordpool = m_wordpool
        self.items = []

# 显示结果
def ShowResult(record):
    output = ""
    for i in record.board:
        for j in i:
            output += j
        output += "\n"
    print output

# 设置单词    
def SetBoard(record, word, i, j, IsRow):
    record_copy = copy.deepcopy(record)
    for (idx,ch) in enumerate(word):
        ci = i + (not IsRow)*idx
        cj = j + IsRow*idx
        record_copy.dirFlag[ci][cj] |= (0x01 if IsRow else 0x02)
        record_copy.board[ci][cj] = ch
        record_copy.indexTable[ord(ch)-ord('a')].add((ci,cj))
    record_copy.items.append([word,i,j,IsRow])
    # 如果结束
    if 0 == len(record_copy.wordpool):
        ShowResult(record)
        sys.exit(0)
    return record_copy

# 检查在指定位置指定方向放单词是否合法
def ValidCheck(record, word, i, j, IsRow):
    L = len(word)
    if i < 0 or j < 0:
        return False
    # 横/纵向溢出检测
    if IsRow and j + L - 1 >= BOARD_SIZE:
        return False
    if not IsRow and i + L - 1 >= BOARD_SIZE:
        return False
    # 单词左边/上边不可以已经有字母
    if IsRow and j-1 >= 0 and record.board[i][j-1] != '-':
        return False
    if not IsRow and i-1 >= 0 and record.board[i-1][j] != '-':
        return False
    # 单词尾部下一位置不可以有单词
    if IsRow and j+L < BOARD_SIZE and record.board[i][j+L] != '-':
        return False
    if not IsRow and i+L < BOARD_SIZE and record.board[i+L][j] != '-':
        return False
    for (idx,ch) in enumerate(word):
        ci = i + (not IsRow)*idx
        cj = j + IsRow*idx
        # 如果和已有单词不匹配
        if record.board[ci][cj] != '-' and record.board[ci][cj] != ch:
            return False
        if record.board[ci][cj] == '-':#如果位置为空
            # 横向单词上下不可以有纵向单词的尾部/头部
            if IsRow and ci-1 >= 0 and record.board[ci-1][cj] != '-' and record.dirFlag[ci-1][cj] & 0x02:
                return False
            if IsRow and ci+1 < BOARD_SIZE and record.board[ci+1][cj] != '-' and record.dirFlag[ci+1][cj] & 0x02:
                return False
            # 纵向单词左右不可以有横向单词的尾部/头部
            if not IsRow and cj-1 >= 0 and record.board[ci][cj-1] != '-' and record.dirFlag[ci][cj-1] & 0x01:
                return False
            if not IsRow and cj+1 < BOARD_SIZE and record.board[ci][cj+1] != '-' and record.dirFlag[ci][cj+1] & 0x01:
                return False
    return True

# 迭代计算
def Calculate(record, curWord, i, j, isrow):
    if ValidCheck(record, curWord, i, j, isrow):
        record_t = SetBoard(record, curWord, i, j, isrow)
        for word in record.wordpool:
            Iter(copy.deepcopy(record_t), word)

# 随机排序yield返回
def RandomSort(l):
    random.shuffle(l)
    for i in l:
        yield i

def Iter(record, curWord):
    global WORDPOOL
    global BOARD_SIZE
    record.wordpool.remove(curWord)
    # 如果是第一个单词，放在棋盘中间
    if len(record.wordpool) == len(WORDPOOL)-1:
        for isrow in RandomSort([True,False]):
            Calculate(record, curWord, (BOARD_SIZE-len(curWord)*(not isrow))//2, (BOARD_SIZE-len(curWord)*isrow)//2, isrow)
    else:# 否则，随机挑个字母，随机挑个位置
        for (idx, ch) in enumerate(curWord):
            for pos in RandomSort(list(record.indexTable[ord(ch)-ord('a')])):
                for isrow in RandomSort([True,False]):
                    Calculate(record, curWord, pos[0]-idx*(not isrow), pos[1]-idx*isrow, isrow)

if __name__ == "__main__":
    record = CRecord(BOARD_SIZE, WORDPOOL)
    for word in record.wordpool:
        Iter(copy.deepcopy(record), word)

本文中代码删减了几个无谓的函数，完整版请看Github

由于不少地方用了random.shuffle函数，所以每次跑出来的结果都是不一样的，结果大概如下（左图是调试的时候一个参考）：
8

然后导出到Mathematica的文本格式大概如下：

finesse 17 14 -
encored 17 20 |
outlay 20 20 -
wisp 16 15 |
cankers 19 20 -
bocks 13 18 |
insofar 16 16 |
gerunds 22 19 -
flower 17 14 |
galling 22 19 |
clear 15 18 -
honchos 14 17 -
decking 22 24 |
.
.
.

标记好单词，起点坐标，横竖信息。

显示谜题

首先，读进来数据，然后计算出有效棋盘大小，再然后初始化一个grid变量，全部为空字符串：
9

Mathematica Code

然后对grid变量，在正确的位置赋值上谜题答案的字母（要分横纵两种情况赋值）：
10

Mathematica Code

在画棋盘之前需要准备两个小函数，一个是设置格子背景颜色的，一个是线框：
11

Mathematica Code

好了，可以试着把棋盘画出来了，一行：
12

Mathematica Code

结果如下：
13

感觉还行。。

但是。。。这个是答案啊！！不是谜题啊摔！！！你搞错了吧。。。

好好好，画谜题就画谜题。。

和画答案的区别在于，不要把字母标上，而是在起始位置标上数字，而联动操作的时候，设置一个按钮面板，点击不同的数，首先会在界面上高亮相应的行或列（or行和列），并且会在面板下面显示行列单词的谜题（就是词典里面这个单词的全部定义啦~）

代码如下：
14

Mathematica Code

录了个gif：
001

这种方法有两个缺陷，第一，要做出自动判断输入结果是对是错这个效果很麻烦(不是不可以)，因为Table内每个元素绑定Dynamic的时候会有点限制。。另外一个问题就是自己输入结果的时候第一个字母处那个数字index要手动删掉。。

所有代码放在Github，有爱自取。

本来想做一个cdf演示直接挂博客的，但是，你看我这文章版面宽度，也懒了。。

总结

总之，食用方法就是先Mathematica生成单词列表，然后把列表拷到python代码中，运行一下，表格将会导出到一个文件中，再用Mathematica读取这个文件，构造界面。。

年前最后一篇博文，赶毕设屁屁踢去了。。民那桑，哈皮牛耶~
885cea9114976961d3c593f9d3c19f52_b

【完】

本文内容遵从CC版权协议，转载请注明出自http://www.kylen314.com

分类: Mathematica 标签: ,
  1. 本文目前尚无任何评论.
验证码：7 + 4 = ?

友情提示：留言可以使用大部分html标签和属性;

添加代码示例:[code lang="cpp"]your code...[/code]

添加公式请用Latex代码，前后分别添加两个$$