Sudoku를 풀어주는 스크립트

#!/usr/local/bin/python
#-*- coding: cp949 -*-
# date   : 2006.  10.  15
#
# 스도쿠를 풀어주는 스크립트

import random

class Sodoku:
 def __init__(self):
  self.timer = 0
  self.board = []
  self.tmpBoard=[]
  for y in range(0, 82):
   self.board.append(0)
   self.tmpBoard.append(511)

 def display(self):

  for y in range(0, 9):
   for x in range(0, 9):
    idx = y* 9 + x + 1;

    if self.board[idx] != 0:
     print "%d" %(self.board[idx]),
    else:
     print "_",
    print '|',
   print '\n'
 
 def checkSquare(self,  sx,  sy):
  sum = 0;
 
  for y in range(0, 3):
   for x in range(0, 3):
    if ( int(self.board[ (y+sy)*9+(x+sx)+1]) > 0):
     sum |= (1 << (int(self.board[ (y+sy)*9+(x+sx)+1]-1)))
  return sum

 def checkBoard(self):
  ret = 0;
  for y in range(0, 9):
   sum = 0;
   for x in range(0, 9):
    if ( int(self.board[y*9+x+1]) > 0):
     sum |= (1 << (int(self.board[y*9+x+1]-1)))
   if (sum != 511):
    ret = 1
   
  for x in range(0, 9):
   sum = 0;
   for y in range(0, 9):
    if ( int(self.board[y*9+x+1]) > 0):
     sum |= (1 << (int(self.board[y*9+x+1]-1)))
   if (sum != 511):
    ret = 2

  for y in range(0, 3):
   for x in range(0, 3):
    sum = self.checkSquare(x*3, y*3)
   if (sum != 511):
    ret = 3
  return ret

 def readData(self):
  fp = open("sudoku.dat", 'r')
  self.board = map(int, fp.read().split(','))
  fp.close()
 
  for y in range(0, 82):
   self.tmpBoard[y] =511
 
 def guessCount(self, num):
  count = 0
  for i in range(0, 9):
   if ( (1 << i) & num ) != 0:
    count += 1
  return count

 def findStartPos(self):
  sx = 0
  sy = 0
  mvalue = 511
  mcount = 10
  for y in range(0,9):
    for x in range(0,9):
     if (self.board[y * 9 + x + 1] == 0):
      temp = self.guessCount(self.tmpBoard[y*9 + x + 1] )
      if (mcount >  temp):
       mvalue = self.tmpBoard[y*9 + x + 1]
       mcount = temp
       sx = x
       sy = y
  return (sx, sy, mvalue)

 def isFull(self):
  count = 0
  for y in range(0,9):
    for x in range(0,9):
     if (self.board[y * 9 + x + 1] != 0):
      count += 1
  return count == 81

 def solve(self):
  if (self.checkBoard() != 0):
   if (self.isFull()):
    return 0
   #get position
   (x, y, num) = self.findStartPos()
   # set number
   for i in range(0, 9):
    if ( (1 << i) & num ) != 0:
     self.board[y*9 + x + 1] = i+1
     # checkTempBoard
     self.checkWidthTempBoard(x, y)
     self.checkHeightTempBoard(x, y)
     self.checkSquareTempBoard(x/3, y/3, x, y)
     if (self.solve() == 1):
       return 1
     else:
      self.unCheckWidthTempBoard(x, y)
      self.unCheckHeightTempBoard(x, y)
      self.unCheckSquareTempBoard(x/3, y/3, x, y)
      self.board[y*9 + x + 1] = 0
   return 0
  else:
   return 1

       
 def checkTempBoard(self):
  for y in range(0, 9):
   for x in range(0, 9):
    if (self.board[y * 9 + x + 1] != 0):
     self.checkWidthTempBoard(x, y)
     self.checkHeightTempBoard(x, y)
     self.checkSquareTempBoard(x/3, y/3, x, y)
 
 def checkWidthTempBoard(self, sx, sy):
   for x in range(0,9):
    if (self.board[sy * 9 + x + 1] == 0):
     self.tmpBoard[sy * 9 + x + 1] &= ~(1 << (self.board[sy * 9 + sx + 1] - 1))

 def checkHeightTempBoard(self, sx, sy):
   for y in range(0,9):
    if (self.board[y * 9 + sx + 1] == 0):
     self.tmpBoard[y * 9 + sx + 1] &= ~(1 << (self.board[sy * 9 + sx + 1] - 1))

 def checkSquareTempBoard(self, sx, sy, tx, ty):
   for y in range(0,3):
    for x in range(0,3):
     if (self.board[(y + sy) * 9 + sx + x + 1] == 0):
      self.tmpBoard[(y + sy * 3) * 9 + sx * 3 + x + 1] &= ~(1 << (self.board[ty * 9 + tx + 1] - 1))    

 def unCheckWidthTempBoard(self, sx, sy):
   for x in range(0,9):
    if (self.board[sy * 9 + x + 1] == 0):
     self.tmpBoard[sy * 9 + x + 1] |=  (1 << (self.board[sy * 9 + sx + 1] - 1))
     
 def unCheckHeightTempBoard(self, sx, sy):
   for y in range(0,9):
    if (self.board[y * 9 + sx + 1] == 0):
     self.tmpBoard[y * 9 + sx + 1] |= (1 << (self.board[sy * 9 + sx + 1] - 1))
     
 def unCheckSquareTempBoard(self, sx, sy, tx, ty):
   for y in range(0,3):
    for x in range(0,3):
     if (self.board[(y + sy) * 9 + sx + x + 1] == 0):
      self.tmpBoard[(y + sy * 3) * 9 + sx * 3 + x + 1] |= (1 << (self.board[ty * 9 + tx + 1] - 1))

 def generate(self):
  self.readData()
  self.checkTempBoard()

def main():
 sodoku = Sodoku()
 
 sodoku.generate()
 sodoku.display()
 sodoku.solve()
 print "-"*60
 sodoku.display()

#----------------------------------------------------------
# main
if __name__ == "__main__":    
   main()

 

[sudoku.dat]
0, 6, 0, 9, 0, 0, 0, 0, 4, 3, 0, 0, 0, 2, 9, 0, 7, 1, 0, 0, 0, 4, 0, 1, 0, 0, 5, 8, 5, 0, 0, 0, 0, 8, 0, 6, 0, 8, 0, 7, 1, 0, 9, 4, 0, 5, 0, 3, 0, 7, 0, 0, 0, 0, 2, 1, 5, 0, 0, 8, 0, 3, 0, 0, 0, 4, 8, 0, 6, 2, 0, 0, 0, 7, 2, 0, 0, 0, 0, 6, 0, 9

 

[실행결과]

6 | _ | 9 | _ | _ | _ | _ | 4 | 3 |

_ | _ | _ | 2 | 9 | _ | 7 | 1 | _ |

_ | _ | 4 | _ | 1 | _ | _ | 5 | 8 |

5 | _ | _ | _ | _ | 8 | _ | 6 | _ |

8 | _ | 7 | 1 | _ | 9 | 4 | _ | 5 |

_ | 3 | _ | 7 | _ | _ | _ | _ | 2 |

1 | 5 | _ | _ | 8 | _ | 3 | _ | _ |

_ | 4 | 8 | _ | 6 | 2 | _ | _ | _ |

7 | 2 | _ | _ | _ | _ | 6 | _ | 9 |
-----------------------------
6 | 1 | 9 | 8 | 7 | 5 | 2 | 4 | 3 |

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

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

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

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

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

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

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

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