알라딘MGG와이드바


스도쿠 알고리즘(sudoku algorithm) by python 개발 이야기

블로그 보다가 likejazz 님 글인지 누구님 블로그에서 스도쿠 짜는 알고리즘에 대한 기사를 읽고 필 받아서 만들어 봤습니다.
python 를 잘 할 줄 몰라서 시간을 많이 잡아 먹었네요.
게다가 빈 칸이 많아서 대안이 둘 이상 되는 경우는 아직 만들지 않아서 미완성이라 할 수 있다는 흐흐...

뭐 허접하지만 여기에서 확인 가능합니다.
http://www.parkpd.x-y.net/moniwiki/wiki.php/Sudoku

이렇게 입력값을 주면

240060970
060004530
000091006
790400000
005908400
000005093
500840000
079300020
036020085

이런 식으로 출력합니다.

2 4 8 5 6 3 9 7 1
9 6 1 7 8 4 5 3 2
3 5 7 2 9 1 8 4 6
7 9 3 4 1 2 6 5 8
6 2 5 9 3 8 4 1 7
1 8 4 6 7 5 2 9 3
5 1 2 8 4 7 3 6 9
8 7 9 3 5 6 1 2 4
4 3 6 1 2 9 7 8 5

코드는 대강 이런 식입니다.


   1: from __future__ import with_statement
   2:  
   3: class Tile:
   4:     def __init__(self, row, col, rect, n):
   5:         self.row = row
   6:         self.col = col
   7:         self.rect = rect
   8:         self.n = n
   9:         self.possible = set([])
  10:     def ShowMe(self):
  11:         print self.row, self.col, self.rect, self.n, " Possible : ", self.possible
  12:     def ShowNum(self):
  13:         print self.n,
  14:     def SetPossible(self, possible):
  15:         self.possible = self.possible | possible
  16:         
  17: class Tiles:
  18:     def __init__(self, name):
  19:         self.name = name
  20:         self.found = set([])                #
  21:         self.notFound = set(range(1,10))    # TODO : merge it with found
  22:         self.notFoundTiles = []
  23:     
  24:     def Append(self, value):
  25:         if value.n != 0:
  26:             self.found.add(value.n)
  27:         else:
  28:             self.notFoundTiles.append(value)
  29:             
  30:     def Ready(self):
  31:         self.found = set(self.found)
  32:         self.notFound = self.notFound - self.found
  33:         
  34:     def RemovePossible(self, v):
  35:         self.notFoundTiles.remove(v)
  36:         for x in self.notFoundTiles:
  37:             if v.n in x.possible:
  38:                 #print "before = ", x.possible
  39:                 x.possible.discard(v.n)
  40:                 #print "after = ", x.possible
  41:  
  42: class TileMgr:
  43:     def __init__(self, name):
  44:         self.tiles = []
  45:         for i in range(0, 9):
  46:             newName = name + str(i)
  47:             self.tiles.append(Tiles(newName))
  48:  
  49:     def Append(self, index, value):
  50:         assert(index < 9)
  51:         self.tiles[index].Append(value)
  52:             
  53:     def Ready(self):
  54:         for i in range(0, 9):
  55:             self.tiles[i].Ready()
  56:     
  57:     def __getitem__(self, key):
  58:         return self.tiles[key]
  59:  
  60: # init global variable
  61: tiles = []
  62: notFoundTiles = []
  63: row = TileMgr("row")
  64: col = TileMgr("col")
  65: rect = TileMgr("rect")
  66:  
  67: # read file and make data structure
  68: r = 0
  69: with open("sudoku.txt") as f:
  70:     for line in f:
  71:         for c in range (0, 9):
  72:             index = (r/3)*3 + (c/3)
  73:             t = Tile(r, c, index, int(line[c]))
  74:             tiles.append(t)
  75:             row.Append(r, t)
  76:             col.Append(c, t)            
  77:             rect.Append(index, t)
  78:         r = r + 1
  79:  
  80: row.Ready()
  81: col.Ready()
  82: rect.Ready()
  83:  
  84: # with notFound in row, col, rect
  85: # Tile found his possibleNumber
  86: for r in range(0, 9):
  87:     for c in range(0, 9):
  88:         i = r * 9 + c
  89:         if tiles[i].n == 0:
  90:             index = (r/3)*3 + (c/3)
  91:             tiles[i].SetPossible(row[r].notFound & col[c].notFound & rect[index].notFound)
  92:             notFoundTiles.append(tiles[i])
  93:  
  94: # use sort(lambda x, y: len(x.possible) < len(y.possible))
  95: notFoundTiles.sort(lambda x,y: cmp(len(x.possible), len(y.possible)))
  96:  
  97: #for x in notFoundTiles:
  98: #    x.ShowMe()
  99:  
 100: while 0 < len(notFoundTiles):
 101:     # get tiles which has only one possible
 102:     t = notFoundTiles[0]
 103:     
 104:     if len(t.possible) == 1:
 105:         # confirm this tile's value
 106:         t.n = t.possible.pop()
 107:  
 108:         # remove t.n from reletive possible
 109:         row[t.row].RemovePossible(t)
 110:         col[t.col].RemovePossible(t)
 111:         rect[t.rect].RemovePossible(t)
 112:         
 113:         # remove head item
 114:         notFoundTiles.pop(0)
 115:         
 116:         # todo : we can soft after comsuming all one possible tiles
 117:         # when we incount at len(t.possible) > 2, then sort again
 118:         notFoundTiles.sort(lambda x,y: cmp(len(x.possible), len(y.possible)))
 119:     else:
 120:         # TODO : using path finding like A*
 121:         # we can route more than 2 alternatives.
 122:         # use stack to remember alternatives
 123:         print "len(t.possible) = ", len(t.possible)
 124:         for x in notFoundTiles:
 125:             x.ShowMe()
 126:         break
 127:  
 128: for r in range(0, 9):
 129:     for c in range(0, 9):
 130:         i = r * 9 + c
 131:         print tiles[i].n,
 132:     print " "

덧글

댓글 입력 영역


Yes24위대한게임의탄생3

위대한 게임의 탄생 3
예스24 | 애드온2