DareYourMind programming 8

http://www.dareyourmind.net/menu.php

들어가보면 스도쿠모양의 틀이 있고, 노란색 점 갯수로 스도쿠를 하면 된다. 매번 이미지는 바뀌며, 제한시간은 5초이다.

저런 이미지에서 뽑아서 하면 된다. 스도쿠 문제는 예전에 풀었던 포스트가 있으므로 거기서 알고리즘을 또 그대로... 가져왔다.

방법론

1. 주변의 회색부분은 흰색으로 만들고 검은색 사각형을 인식한다. 각 81개의 검은 사각형이 인식되는데, 각각의 검은 사각형의 x,y좌표를 처음엔 y좌표로 정렬 그다음엔 x좌표로 정렬해서 따로 저장해둔다.

그러면 현재 위 사진 기준으로 (7,2,5,8,4,' ',' ',3,6,4,1...) 순서로 정렬된다.

2. 노란색 점을 인식해서 각각 노란색점이 위에서 저장해놓은 x,y좌표의 사각형 안에 있는지 확인한다. 사각형 안에 있으면 어떤 변수를 +1시켜줘서 개수를 증가시킨다. 0이면 없는걸로 친다.

3. 스도쿠를 계산해서 알아서 잘 처리해서 보낸다.

코딩.

# -*- encoding: cp949 -*-
import urllib2
import re
import random
import os
import operator
import numpy as np
import Image
import cv2

session = 'PHPSESSID=gscil0mtiv6qpehu275cebp6c6'

# 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
 

def setCell(trialVal, trialCelli, grid):
  grid[trialCelli] = 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 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

def download_photo(filename):
    file_path = "%s%s" % ("C:\\Users\\Ko\\Documents\\Visual Studio 2012\\Projects\\PythonApplication37\\", filename)
    downloaded_image = file(file_path, "wb")
        
    req = urllib2.Request('http://www.dareyourmind.net/Challenge/sudoku2.php')
    req.add_header('Cookie',session)
    image_on_web = urllib2.urlopen(req)
    while True:
        buf = image_on_web.read()
        if len(buf) == 0:
            break
        downloaded_image.write(buf)
    downloaded_image.close()
    image_on_web.close()
    return file_path

def main ():
    download_photo('sudoku.png')
    im = Image.open('sudoku.png').convert('RGB')
    for i in range(im.size[1]):
        for j in range(im.size[0]):
            if im.getpixel((j,i))==(74,74,74):
                im.putpixel((j,i),(255,255,255))
    im.save('sudoku1.png')

    im = cv2.imread('sudoku1.png') 
    imgray = cv2.cvtColor(im,cv2.COLOR_BGR2GRAY) 
    ret,thresh = cv2.threshold(imgray,127,255,0)
    contours, hierarchy = cv2.findContours(thresh,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)
      
    square = []

    for cnt in contours:
        if int(cv2.contourArea(cnt)) == 782: #작은 네모 하나 인식.
            [x,y,w,h] = cv2.boundingRect(cnt)
            square.append([x,y,x+w,y+h,0])
            #rect = cv2.minAreaRect(cnt)
            #box = cv2.cv.BoxPoints(rect)
            #box = np.int0(box)
            #cv2.drawContours(im,[box],0,(0,255,0),2)
            #cv2.imshow('result',im)
            #cv2.waitKey(0)
    square = sorted(square, key = lambda x:(x[1],x[0]))

    for cnt in contours:
        if int(cv2.contourArea(cnt)) < 10: #노란색 점 인식.
            [x,y,w,h] = cv2.boundingRect(cnt)
            for s in square:
                if s[0] < x and s[2] > x and s[1] < y and s[3] > y:
                    s[4] += 1

    sampleGrid = []; answer_index = []
    for s in range(len(square)):
        if square[s][4]==0:
            sampleGrid.append('.')
            answer_index.append(s)
        else:
            sampleGrid.append(square[s][4])


    #sampleGrid = ['2', '1', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '3', '1', '.', '.', '.', '.', '9', '4', '.', '.', '.', '.', '7', '8', '2', '5', '.', '.', '4', '.', '.', '.', '.', '.', '.', '6', '.', '.', '.', '.', '.', '1', '.', '.', '.', '.', '8', '2', '.', '.', '.', '7', '.', '.', '9', '.', '.', '.', '.', '.', '.', '.', '.', '3', '1', '.', '4', '.', '.', '.', '.', '.', '.', '.', '3', '8', '.']
    printGrid(sampleGrid, 0)
    if hasSolution (sampleGrid):
        printGrid(sampleGrid, 0)
    else: print 'NO SOLUTION'

    answer = ''
    for i in range(len(answer_index)):
        answer += str(sampleGrid[answer_index[i]])

    #print answer
    
    req = urllib2.Request('http://www.dareyourmind.net/menu.php?page=programming8&checked='+answer)
    req.add_header('cookie',session)
    print urllib2.urlopen(req).read()
  
if __name__ == "__main__":
    main()