数独(Sudoku) @ 4/13/2009

技术类
周五下午开始,考虑写一个数独玩儿,周末断断续续的测试我的想法,写到现在才算写完了,似乎还有一些小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()
发布于 4/13/2009 10:19:50 | 评论:10
天魔 @ 4/13/2009 16:52:22
很好很强大!
吴雨 @ 4/13/2009 17:47:54
话说,我没有在ff下测试呢。。。
天魔 @ 4/14/2009 0:28:24
我用 FF 试的,没问题~
LH @ 4/17/2009 10:48:01
我最喜欢玩的一个游戏
LH @ 4/17/2009 10:50:06
有点麻烦,不能直接填数吗?只能点一下数点一下空格?
吴雨 @ 4/17/2009 11:13:34
呵呵,其实是因为我想在手机上能玩儿~~特别是iphone~
infmath @ 1/12/2010 6:38:24
请问
你这个新生成的原理是什么?
另外python我会一点点,请问
from google.appengine.ext import webapp
from google.appengine.ext.webapp import template
要装什么,怎么装?
吴雨 @ 1/12/2010 10:05:34
to infmath:
就是找一个已经生成的数独,然后把它横排竖排变着法儿的对调,然后再想办法凑起来一个数独就好了。
google.appengine是google appengine的python开发包。能看懂原理就好啦,不需要一定装gae。
ninthsun @ 3/19/2010 19:56:58
困难有BUG。。。。数字冲突。。。。不过还是顶下。。难度方面还是都差不多啊
吴雨 @ 3/19/2010 20:11:39
数字冲突的问题,其实挺难解决的。
我说的还有小bug就是指这个,因为我在试图解决这个问题的时候,碰到过一个很大的循环,导致全部确定不下来的情况。
我的感觉,如果想避免这个,应该在每去掉一个值的时候都要判断一下这个值是不是不能去掉,判断不能去掉的方法,应该是已经去掉了的值中有多少是跟这个值有关的,但是我对数独研究的不深,所以一时找不到好的办法。
大概去掉一个值的时候,反过来推算一下这个谜能不能解开也可以。

看帖要回帖...

categories
archives
links
statistics
  • 网志数:1168
  • 评论数:2011