canyouhack.it Programming Challenge 2 Sudoku!

스도쿠 그림이 나오고, 해당 스도쿠 그림이 있는 부분을 파싱해서 데이터를 잘 가져와서 문제를 푼 다음, A,B,C,D,E,~이런식으로 이어서 3초안에 다 계산해서 보내면 된다. 다른곳에서 알고리즘을 가져왔다.

http://code.activestate.com/recipes/578140-super-simple-sudoku-solver-in-python-source-code/

코드.

# -*- encoding: cp949 -*-
import urllib2
import re
import random
import os
import operator

session = 본인 세션
# GLOBAL VARIABLES
grid_size = 81

def isFull (grid):
    return grid.count('.') == 0
  
# can be used more purposefully
def getTrialCelli(grid):
  for i in range(grid_size):
    if grid[i] == '.':
      #print 'trial cell', i
      return i
      
def isLegal(trialVal, trialCelli, grid):

  cols = 0
  for eachSq in range(9):
    trialSq = [ x+cols for x in range(3) ] + [ x+9+cols for x in range(3) ] + [ x+18+cols for x in range(3) ]
    cols +=3
    if cols in [9, 36]:
      cols +=18
    if trialCelli in trialSq:
      for i in trialSq:
        if grid[i] != '.':
          if trialVal == int(grid[i]):
            #print 'SQU',
            return False
  
  for eachRow in range(9):
    trialRow = [ x+(9*eachRow) for x in range (9) ]
    if trialCelli in trialRow:
      for i in trialRow:
        if grid[i] != '.':
          if trialVal == int(grid[i]):
            #print 'ROW',
            return False
  
  for eachCol in range(9):
    trialCol = [ (9*x)+eachCol for x in range (9) ]
    if trialCelli in trialCol:
      for i in trialCol:
        if grid[i] != '.':
          if trialVal == int(grid[i]):
            #print 'COL',
            return False
  #print 'is legal', 'cell',trialCelli, 'set to ', trialVal
  return True

dic = {}; answer_dic = {}
def setCell(trialVal, trialCelli, grid):
  global dic, answer_dic
  grid[trialCelli] = trialVal
  for key,val in dic.iteritems():
      if val == trialCelli: answer_dic[key]=trialVal
  return grid

def clearCell( trialCelli, grid ):
  grid[trialCelli] = '.'
  #print 'clear cell', trialCelli
  return grid


def hasSolution (grid):
  if isFull(grid):
    #print '\nSOLVED'
    return True
  else:
    trialCelli = getTrialCelli(grid)
    trialVal = 1
    solution_found = False
    while ( solution_found != True) and (trialVal < 10):
      #print 'trial valu',trialVal,
      if isLegal(trialVal, trialCelli, grid):
        grid = setCell(trialVal, trialCelli, grid)
        if hasSolution (grid) == True:
          solution_found = True
          return True
        else:
          clearCell( trialCelli, grid )
      #print '++'
      trialVal += 1
  return solution_found

def main ():
    global dic,answer_dic
    req = urllib2.Request('http://canyouhack.it/Content/Challenges/Programming/Prog2.php')
    req.add_header('cookie',session)
    page = urllib2.urlopen(req).read()
    sampleGrid = re.findall('<center>(.*?)</center>',page)
    printGrid(sampleGrid, 0)
    for i in range(len(sampleGrid)):
        try: int(sampleGrid[i])
        except: dic[sampleGrid[i]]=i; sampleGrid[i]='.'
    if hasSolution (sampleGrid):
        printGrid(sampleGrid, 0)
    else: print 'NO SOLUTION'
    answer_dic = sorted(answer_dic.iteritems(), key=operator.itemgetter(0))
    answer = ','.join(map(lambda x:''.join(str(x[1])),answer_dic))
    print answer
    req = urllib2.Request('http://canyouhack.it/Content/Challenges/Programming/Prog2.php?Answer='+answer)
    req.add_header('cookie',session)
    print urllib2.urlopen(req).read()

def printGrid (grid, add_zeros):
  print
  i = 0
  for val in grid:
    if add_zeros == 1:
      if int(val) < 10: 
        print '0'+str(val),
      else:
        print val,
    else:
        print val,
    i +=1
    if i in [ (x*9)+3 for x in range(81)] +[ (x*9)+6 for x in range(81)] +[ (x*9)+9 for x in range(81)] :
        print '|',
    if add_zeros == 1:
      if i in [ 27, 54, 81]:
        print '\n---------+----------+----------+'
      elif i in [ (x*9) for x in range(81)]:
        print
    else:
      if i in [ 27, 54, 81]:
        print '\n------+-------+-------+'
      elif i in [ (x*9) for x in range(81)]:
        print

if __name__ == "__main__":
    main()