[python]Sudoku Solver

https://www.codewars.com/kata/5296bc77afba8baa690002d7/train/python

Codewars: Train your coding skills

풀이를 보시려면 더보기를 클릭하시면 됩니다.

 

Sudoku Solver

스도쿠는 숫자 퍼즐로, 가로 9칸, 세로 9칸으로 이루어져 있는 표에 1부터 9까지의 숫자를 채워 넣는 퍼즐입니다.

퍼즐을 푸는 방법은 같은 줄에는 1에서 9까지의 숫자를 한 번만 넣고, 3x3칸의 작은 격자 또한 1에서 9까지의 숫자가 겹치지 않게 들어가야 합니다.

 

입력에서 빈칸은 0으로 표현되어 있습니다. 0인 인덱스만 찾아서 zero_index 리스트에 저장했습니다.

# 0인 인덱스만 찾아서 zero_index에 저장
for i in range(9):
    for j in range(9):
        if puzzle[i][j] == 0:
            zero_index.append([i, j])

 

zero_index에 저장된 인덱스 값들을 검증해야 합니다. a와 b에 인덱스 값을 저장하고 promise라는 변수에 promising이라는 함수의 return 값을 저장합니다.

# 검증을 통해 숫자를 구함
a, b = zero_index[idx]
promise = promising(puzzle, [a, b])

 

여기서 promising는 위에서 언급한 퍼즐을 푸는 방법이 있는 함수입니다. 스도쿠 문제 리스트와 zero_index의 인덱스 값을 받아서 빈칸에 가능한 숫자들을 돌려줍니다.

def promising(puzzle, zero):
    a, b = zero
 
    # 1 ~ 9까지 숫자 리스트 만듬
    nums = list(map(int, range(1, 10)))
 
    # 가로 세로 확인
    for i in range(9):
        # 가로 확인하여 리스트에 숫자가 존재하면 지움
        if puzzle[a][i] in nums:
            nums.remove(puzzle[a][i])
        # 세로 확인하여 리스트에 숫자가 존재하면 지움
        if puzzle[i][b] in nums:
            nums.remove(puzzle[i][b])
 
    # 3x3 확인
    if len(nums) > 0:
        rt = (a // 3) * 3
        ct = (b // 3) * 3
        for i in range(rt, rt + 3):
            for j in range(ct, ct + 3):
                if puzzle[i][j] in nums:
                    nums.remove(puzzle[i][j])
    # 남은 숫자들 리턴
    return nums

 

promise에 promising 함수에서 return한 숫자 리스트들을 하나씩 대입시켜 나가면서 검증을 합니다.

# 숫자 리스트들을 대입시켜 나가면서 검증
for p in promise:
    puzzle[a][b] = p
    idx += 1
    sudoku(puzzle)

 

위의 코드처럼 사용하면 정답이 아닐 경우 수정이 되지 않기 때문에 Boolean 플래그를 생성하여 정답이 아닐 경우 idx 변수는 1 감소하고 puzzle[a][b]에는 0을 넣어 다시 문제를 풀어야 합니다.

# 숫자 리스트들을 대입시켜 나가면서 검증
for p in promise:
    puzzle[a][b] = p
    idx += 1
    sudoku(puzzle)
    # END_FLAG가 True이면 끝
    if END_FLAG:
        return puzzle
# END_FLAG가 False이면 정답이 아니라는 것으로 원상태로 되돌림
if END_FLAG == False:
    idx -= 1
    puzzle[a][b] = 0

 

여기서 아직 언급을 하지 않았던 END_FLAG를 설명하겠습니다. END_FLAG는 스도쿠 문제를 전부 다 풀었는지 확인하는 변수입니다. 초기값을 False로 갖고 만약 idx가 zero_index 길이(len(zero_index)와 같을 경우 True로 변경하여 문제 푸는 것을 종료합니다.

# idx가 zero_index의 길이 만큼 같다면 모두 다 한 것이므로 END_FLAG를 True로 변경
if idx == len(zero_index):
    END_FLAG = True
    # idx와 zero_index를 초기화
    idx = 0
    zero_index = []
    return puzzle

 

sudoku함수 코드

def sudoku(puzzle):
    global zero_index, idx, END_FLAG
 
    # 반복 실행 막음
    if len(zero_index) < 1:
        # 여러가지 케이스 실행 시 END_FLAG가 True로 있으므로 END_FLAG를 False로 변경
        END_FLAG = False
        # 0인 인덱스만 찾아서 zero_index에 저장
        for i in range(9):
            for j in range(9):
                if puzzle[i][j] == 0:
                    zero_index.append([i, j])
 
    # idx가 zero_index의 길이 만큼 같다면 모두 다 한 것이므로 END_FLAG를 True로 변경
    if idx == len(zero_index):
        END_FLAG = True
        # idx와 zero_index를 초기화
        idx = 0
        zero_index = []
        return puzzle
 
    # 검증을 통해 숫자를 구함
    a, b = zero_index[idx]
    promise = promising(puzzle, [a, b])
 
    # 숫자 리스트들을 대입시켜 나가면서 검증
    for p in promise:
        puzzle[a][b] = p
        idx += 1
        sudoku(puzzle)
        # END_FLAG가 True이면 끝
        if END_FLAG:
            return puzzle
    # END_FLAG가 False이면 정답이 아니라는 것으로 원상태로 되돌림
    if END_FLAG == False:
        idx -= 1
        puzzle[a][b] = 0

 

전체 코드

# My Code
zero_index = []
idx = 0
END_FLAG = False
 
def sudoku(puzzle):
    global zero_index, idx, END_FLAG
 
    # 반복 실행 막음
    if len(zero_index) < 1:
        # 여러가지 케이스 실행 시 END_FLAG가 True로 있으므로 END_FLAG를 False로 변경
        END_FLAG = False
        # 0인 인덱스만 찾아서 zero_index에 저장
        for i in range(9):
            for j in range(9):
                if puzzle[i][j] == 0:
                    zero_index.append([i, j])
 
    # idx가 zero_index의 길이 만큼 같다면 모두 다 한 것이므로 END_FLAG를 True로 변경
    if idx == len(zero_index):
        END_FLAG = True
        # idx와 zero_index를 초기화
        idx = 0
        zero_index = []
        return puzzle
 
    # 검증을 통해 숫자를 구함
    a, b = zero_index[idx]
    promise = promising(puzzle, [a, b])
 
    # 숫자 리스트들을 대입시켜 나가면서 검증
    for p in promise:
        puzzle[a][b] = p
        idx += 1
        sudoku(puzzle)
        # END_FLAG가 True이면 끝
        if END_FLAG:
            return puzzle
    # END_FLAG가 False이면 정답이 아니라는 것으로 원상태로 되돌림
    if END_FLAG == False:
        idx -= 1
        puzzle[a][b] = 0
 
def promising(puzzle, zero):
    a, b = zero
 
    # 1 ~ 9까지 숫자 리스트 만듬
    nums = list(map(int, range(1, 10)))
 
    # 가로 세로 확인
    for i in range(9):
        # 가로 확인하여 리스트에 숫자가 존재하면 지움
        if puzzle[a][i] in nums:
            nums.remove(puzzle[a][i])
        # 세로 확인하여 리스트에 숫자가 존재하면 지움
        if puzzle[i][b] in nums:
            nums.remove(puzzle[i][b])
 
    # 3x3 확인
    if len(nums) > 0:
        rt = (a // 3) * 3
        ct = (b // 3) * 3
        for i in range(rt, rt + 3):
            for j in range(ct, ct + 3):
                if puzzle[i][j] in nums:
                    nums.remove(puzzle[i][j])
    # 남은 숫자들 리턴
    return nums
 
if __name__=='__main__':
    answer = sudoku([[5, 3, 0, 0, 7, 0, 0, 0, 0],
                     [6, 0, 0, 1, 9, 5, 0, 0, 0],
                     [0, 9, 8, 0, 0, 0, 0, 6, 0],
                     [8, 0, 0, 0, 6, 0, 0, 0, 3],
                     [4, 0, 0, 8, 0, 3, 0, 0, 1],
                     [7, 0, 0, 0, 2, 0, 0, 0, 6],
                     [0, 6, 0, 0, 0, 0, 2, 8, 0],
                     [0, 0, 0, 4, 1, 9, 0, 0, 5],
                     [0, 0, 0, 0, 8, 0, 0, 7, 9]])
    print(answer)
    puzzle = [[8, 0, 0, 0, 0, 0, 0, 0, 0],
              [0, 0, 3, 6, 0, 0, 0, 0, 0],
              [0, 7, 0, 0, 9, 0, 2, 0, 0],
              [0, 5, 0, 0, 0, 7, 0, 0, 0],
              [0, 0, 0, 0, 4, 5, 7, 0, 0],
              [0, 0, 0, 1, 0, 0, 0, 3, 0],
              [0, 0, 1, 0, 0, 0, 0, 6, 8],
              [0, 0, 8, 5, 0, 0, 0, 1, 0],
              [0, 9, 0, 0, 0, 0, 4, 0, 0]]
    answer = sudoku(puzzle)
    print(answer)

 

백준의 2580번 스도쿠 문제와 비슷합니다.