秋梦无痕

周五下午开始，考虑写一个数独玩儿，周末断断续续的测试我的想法，写到现在才算写完了，似乎还有一些小bug，不管了，咔咔，放到GAE上去，链接地址是http://ifyr.appspot.com/sudoku.py，都来玩玩吧，找找错哈。
数独的原理很简单，在9×9的大九宫格中有9个3×3的小九宫格，并提供一定数量的数字。根据这些数字，利用逻辑和推理，在其他的空格上填入1到9的数字。每个数字在每个小九宫格内不能出现一样的数字，每个数字在每行、每列也不能出现一样的数字。
数独生成算法通常都用回溯法，就是先把数都摆上，然后挨个试着换位置，直到成为一个数独局为止，可以参考数独游戏局的建立算法 (Sudoku Generating Algorithm Using Backtracking) 和Sudoku Generator。窃以为这种算法很消耗cpu的说，我是个懒人，就会想些懒法子。
于是从最规则的数独开始，纵横变幻，然后发现。。。这样得出的数独也是很规则的。后来就找了一个不规则的数独，纵横变换，哇咔咔，可以用了。。。但是这样似乎生成不了很规则的数独，不过这样没有关系，玩的时候就应该玩没有规则的，对吧。
然后，怎么样定难度呢？说实话，我还真不知道。。。瞎定了一下，如果有人玩儿，麻烦告诉我，目前这个难度的设定是不是可以接受？
嗯，至于为什么弄得这么窄，是因为我希望能在手机上玩儿~~

以下是源代码：

#! /usr/bin/env python
# coding=utf-8
# filename: sudoku.py
import wsgiref.handlers
import time
import random
import copy

from google.appengine.ext import webapp
from google.appengine.ext.webapp import template

class Sudoku(webapp.RequestHandler):
root = [
['9','8','1','2','4','7','5','3','6'],
['7','5','4','3','6','8','9','1','2'],
['3','2','6','9','5','1','7','8','4'],
['1','4','9','5','3','2','6','7','8'],
['5','6','3','7','8','4','1','2','9'],
['2','7','8','6','1','9','3','4','5'],
['6','1','2','8','9','3','4','5','7'],
['4','9','7','1','2','5','8','6','3'],
['8','3','5','4','7','6','2','9','1']
]
def get(self, *arg):
if self.request.query_string == '':
self.response.out.write(template.render('sudoku.htm'), {})
else:
level = self.request.GET['level']
if level == '':
level = 0
else:
level = int(level)
if level not in range(0,3):
level = 0
self.newgame(level)

def newgame(self, level):
seek = int(time.time())
board = self.generate(seek)
puzzle = self.puzzle(board, level)
self.write(board,puzzle)

def write(self, board, puzzle):
boardstr = ''
for i in range(0, 9):
boardstr += ''.join(board[i])
puzzlestr = ''
for i in range(0, 9):
puzzlestr += ''.join(puzzle[i])
self.response.headers['Expires'] = "Fri, 01 Jan 1990 00:00:00 GMT"
self.response.headers['content-type'] = 'text/javascript'
self.response.headers['cache-control'] = 'no-cache, no-store, max-age=0, must-revalidate'
self.response.out.write('{answer:"'+boardstr+'",puzzle:"'+puzzlestr+'"}')

def generate(self, seek):
board = copy.deepcopy(self.root)
n = 0
while True:
item = seek % 9
action = seek % 6
m = item / 3 * 3 + action % 3
n = item / 3 * 3 + (m + 1) % 3
if action / 3 == 0:
for i in range(0, 9):
temp = board[i][m]
board[i][m] = board[i][n]
board[i][n] = temp
else:
temp = board[m]
board[m] = board[n]
board[n] = temp
m = item
n = (item + action) % 9
if m != n:
x = board[0][m]
y = board[0][n]
for i in range(0,9):
j = board[i].index(x)
k = board[i].index(y)
board[i][j] = y
board[i][k] = x
if seek < 9:
break
n = (n + 1) % 9
seek = seek / 9
return board

def puzzle(self, board, level):
puzzle = copy.deepcopy(board)
c = [44,48,50][level] # easy 44, medium 48, hard 50
while c > 0:
i = random.randint(0, 8)
j = random.randint(0, 8)
if puzzle[i][j] != '0':
puzzle[i][j] = '0'
c -= 1
return puzzle

def main():
application = webapp.WSGIApplication([("/sudoku.py", Sudoku)], debug=True)
wsgiref.handlers.CGIHandler().run(application)

if __name__ == "__main__":
main()