FC2ブログ
--.--
--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

10.13
Sat
ひさしぶりにPython書きました〜

やっぱり書かないと忘れる

数独解くやつ書きましたです

class Sudokuって書いて気づいたんですけど、

これ毎回インスタンス作るはめになるなぁーって

すごく遅そう。はい遅いです。

コードも長くて冗長だしもうあれ

n*nの数独とけるはずです.たぶん

#!/usr/bin/env python
#coding:utf-8

import os
import copy


class Sudoku:

    symbol   = 0

    def __init__(self , filename = "" , ndata = [] , flag = True , blocksize = 3):
        self.blocksize = blocksize
        self.universe = None
        if ndata != []:
            self.board = ndata
            self.universe = set([each+1 for each in range(len(ndata[0]))])
        else:
            if not os.path.exists(os.path.expanduser(filename)):
                raise IOError , "file not found: %s" %(filename)
            else:
                self.board = self.convert(open(os.path.expanduser(filename) , "r").read())
        self.whileinit()
        if flag:
            print "---Problem---------------"
            self.show()

    def convert(self , data):
        eachline = data.split("\n")
        self.blocksize = int(eachline[0])
        self.universe = set([num+1 for num in range(self.blocksize * self.blocksize)])
        del eachline[0:1]
        return [[int(factor) for factor in line.split(",")] for line in eachline if line != ""]

    def factor(self , pos):
        bpos = self.pos2boardpos(pos)
        return self.board[bpos[0]][bpos[1]]

    def pos2boardpos(self , pos):return (pos[1] , pos[0])

    def getblock(self , pos):
        x = pos[0] + 1
        y = pos[1] + 1
        while (x % self.blocksize != 0 or x == 0):x += 1
        while (y % self.blocksize != 0 or x == 0):y += 1
        x = x / self.blocksize - 1
        y = y / self.blocksize - 1
        h = y * self.blocksize
        w = x * self.blocksize
        return [self.board[r_index+h][c_index+w] for c_index in range(self.blocksize) for r_index in range(self.blocksize)]
        
    def findblank(self):
        result = []
        for r_i , line in enumerate(self.board):
            for c_i,factor in enumerate(line):
                if factor == self.symbol:result.append((c_i , r_i))
        return result
        
    def setf(self, place , val):
        pos = self.pos2boardpos(place)
        self.board[pos[0]][pos[1]] = val
        return None
        
    def init(self):
        for eachblank in self.findblank():
            r = self.getpossibility(eachblank)
            if len(r) == 1: self.setf(eachblank , r[0])
        return None

    def show(self):
        for i1,line in enumerate(self.board):
            for i,factor in enumerate(line):
                print factor ,
                print "   " ,
                if (i+1) % self.blocksize == 0: print "  " ,
            print "\n"
            if (i1+1) % self.blocksize == 0 : print "\n"
        
    def whileinit(self):
        cop   = self.board
        result = []
        while (result != cop):
            cop   = copy.deepcopy(self.board)
            self.init()
            result = self.board
        return None
    def getpossibility(self , pos):
        return list(self.universe.difference(set(self.getcolumn(pos[0])).union(set(self.getrow(pos[1]))).union(self.getblock(pos))))
    
    def getrow(self,y):return self.board[y]
   
    def getcolumn(self,x):return [eachrow[x] for eachrow in self.board]
    
    def isin(self, factor , lst):
        if lst == [] : return False
        if type(lst[0]) == list:
           return self.isin(factor , lst[0]) or self.isin(factor , lst[1:])
        else:
            if lst[0] == factor:
                return True
            else:
                return self.isin(factor , lst[1:])
   
    def solve(self):
        if not self.isin(self.symbol , self.board):return self
        blanks = self.findblank()
        numb =   self.getpossibility(blanks[0])
        result = None
        for each in numb:
            self.setf(blanks[0] , each)
            result = Sudoku(ndata = copy.deepcopy(self.board) , blocksize = self.blocksize , flag = False).solve()
            if not result is None:return result
        return result


def main():Sudoku(filename = "~/Desktop/sudoku.txt").solve().show()

"""
以下みたいな感じでファイルを作ります。3ってのはひとつのちっちゃい四角にはいる数字のかずです
"""
"""
3
1,2,3  ,1,2,3  ,1,2,3
1,2,3  ,1,2,3  ,1,2,3
1,2,3  ,1,2,3  ,1,2,3
4,5,6  ,4,5,6  ,4,5,6
4,5,6  ,4,5,6  ,4,5,6
4,5,6  ,4,5,6  ,4,5,6
7,8,9  ,7,8,9  ,7,8,9
7,8,9  ,7,8,9  ,7,8,9
7,8,9  ,7,8,9  ,7,8,9
"""

main()




数独のうまってない部分には0を書いてください
スポンサーサイト

comment 0 trackback 1
トラックバックURL
http://telracsmoratori.blog.fc2.com/tb.php/144-a84ecbf7
トラックバック
ひさしぶりにPython書きました〜 やっぱり書かないと忘れる 数独解くやつ書きましたです class Sudoku
まとめ【ひさびさのPython】 | まっとめBLOG速報 | 2012.11.04 08:55
コメント
管理者にだけ表示を許可する
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。