Python :: 파이썬 스도쿠 풀이프로그램 제작

Python 프로그래밍 기초 수업 때 자율주제로 프로그래밍 프로젝트를 진행했다.

처음에는 turtle을 이용하여 FPS게임을 제작해보려 했으나 타 모듈을 사용하지 않고서 FPS를 만들기란 쉽지가 않았다.

결국 주제를 바꾸어 스도쿠 문제를 풀어주는 프로그램을 만들기로 바꾸었는데 이또한 쉽지 않았다.

스도쿠를 주제로 동시에 두개의 프로그램을 제작하였는데 한가지는 지능형 브루트포스방식으로 한 칸안에 들어갈 가능성을 판단하여 재귀함수를 통한 무차별대입을 가하는 방식이고 다른 한가지는 실제 풀이방법 그대로 풀어가는 프로그램이었다. 머리가 복잡해질 때 마다 프로그램을 바꿔가며 개발을 했는데 방금 브루프포스방법이 성공하였다.

실제 코드는 아래와 같다.

game=[[0,0,3,0,2,0,6,0,0],

      [9,0,0,3,0,5,0,0,1],

      [0,0,1,8,0,6,4,0,0],

      [0,0,8,1,0,2,9,0,0],

      [7,0,0,0,0,0,0,0,8],

      [0,0,6,7,0,8,2,0,0],

      [0,0,2,6,0,9,5,0,0],

      [8,0,0,2,0,3,0,0,9],

      [0,0,5,0,1,0,3,0,0]]

tmp = [[] for i in range(81)]

def startTree(count): #트리구조 대입

    if count%50 ==0:

        print("|",end="")

    if count ==81:

        return 7

    y0=count//9

    x0=count%9

    findPossibility(x0,y0)

    

    tt=1

    while True:

        if tt==7:

            return 7

        elif tt==0:

            if tmp[count-1]!=[0]:

                game[(count-1)//9][(count-1)%9]=0

                return 1

            else:

                return 0

        if tmp[count]==[]:

            tt=0

            continue

        elif tmp[count] !=[0]:

            game[y0][x0]=tmp[count][0]

            del tmp[count][0]

        tt = startTree(count+1)

        if tmp[count] == [0] and tt!=7:

            tt=0

    

def findBase(locate):#기본 사각형 위치 초기화

    if locate<=2:

        return 0

    elif locate>2 and locate<=5:

        return 3

    else:

        return 6

                    

def findPossibility(x1,y1):#해당좌표 가능성 검사

    yTmp=findBase(y1)

    xTmp=findBase(x1)

    tmp[y1*9+x1] = []

    if game[y1][x1] != 0:

        tmp[y1*9+x1] = [0]

        return

    for target in range(1,10):

        for find in range(9):

            if target == game[find][x1]:#세로검사

                find=10

            if find==0 or find==1 or find==2:#네모칸 검사

                if target in game[yTmp+find][xTmp:xTmp+2]:

                    find=10

            if find==10:

                break

        if target in game[y1] or find==10:#가로검사

            continue

        else:

            tmp[y1*9+x1].append(target)

for i in game:

    print(i)

print("")

print("풀이중 ",end=" ")

startTree(0)

print("|")

print("")

for i in game:

    print(i)

시간날 때 나머지 풀이도 완성해보아야겠다.