[Python] 스도쿠

> 과제 요구사항

주어진 스도쿠 문제를 자동으로 해결하는 알고리즘을 만들어야 한다.
+ 추가로, Class를 사용해야 한다.
(숫자 0이 비어있는 공간이라고 생각한다.)

> 출력 예시

보기 편하기 위해 Problem 1~3까지만 출력을 붙여놓았다. 실제로는 1부터 순서대로 출력된다고 생각하면 된다.

> 코드

def get_sudoku_list(document): #only get 10 sudoku_input
    f=open(document,'r',encoding="UTF-8")
    all=[]
    result=[]
    k=0
    while k<10:
        cnt=0
        while True:
            tmp_line=[]
            line=f.readline()
            
            line=line[:9]
            if line!='\n':
                for i in line:
                    tmp_line.append(int(i))
                result.append(tmp_line)
            cnt+=1

            if line=='\n' or (k == 9 and cnt == 9):
                all.append(result)
                result=[]
                break
        k+=1
    return all

def empty(sudoku):
        zero=[(i,j) for i in range(9) for j in range(9) if sudoku[i][j]==0]
        return zero

def possible_num(sudoku,i,j):
    possible=[1,2,3,4,5,6,7,8,9]

    for rc in range(9):
        if sudoku[i][rc] in possible:
            possible.remove(sudoku[i][rc])
        if sudoku[rc][j] in possible:
            possible.remove(sudoku[rc][j])

    i//=3
    j//=3

    for r in range(i*3,(i+1)*3):
        for c in range(j*3,(j+1)*3):
            if sudoku[r][c] in possible:
                possible.remove(sudoku[r][c])

    return possible

class Sudoku:
    def __init__(self,sudoku):
        self.sudoku=sudoku
        self.zero=empty(self.sudoku)
        self.length=len(self.zero)
        self.first=True
        self.flag=False
        self.x=-1

    def __repr__(self):
        i=0
        while i<9:
            j=0
            tmp=[]
            if i%3==0:
                print("-------------")
            while j<9:
                if j%3==0:
                    tmp.append('|')
                tmp.append(str(self.sudoku[i][j]))
                j=j+1
            tmp.append('|')
            tmp=''.join(tmp)
            print(tmp)
            i+=1
        return '-------------'

    def solve(self):
        self.x+=1
        
        if self.flag:
            return

        if self.x ==self.length:
            self.x=-1
            self.flag=True 
            return
        else:
            (i, j)=self.zero[self.x]
            num=possible_num(self.sudoku,i,j)

            for k in num:
                self.sudoku[i][j]=k
                self.solve()
                if self.flag:
                    return
                self.sudoku[i][j]=0
                self.x-=1


sudoku_list=get_sudoku_list("sudoku-input.txt")
cnt=0
while cnt<10:
    my_sudoku=Sudoku(sudoku_list[cnt])
    print(f"Problem {cnt+1}\n",my_sudoku)
    my_sudoku.solve()
    print("Solution")
    print(my_sudoku)
    cnt=cnt+1

> 추가 첨부파일

코드에 쓰인 sudoku-input.txt이다.
https://drive.google.com/file/d/1xvd_SmcCukdher7efYze1ipk9b9iX4Bq/view?usp=share_link
총 10문제로 구성되어 있다. 문서에 적힌 난이도는 지우고 실행시켜보자.
추가로 자신이 만든 문제를 풀게 해보고 싶다면 형식에 맞게 sudoku-input.txt에 추가해보자.