[python] 백준 2239 스도쿠

https://www.acmicpc.net/problem/2239

2239번: 스도쿠

 

문제 해결

• 처음에 보면 까마득하다.(스도쿠 옛날에 풀어본 것 같은데 까먹기도 하고 실제로 싫어해서 싫어하는 문제..)
• 하나씩 확인해가며 풀어야겠다는 것은 알겠는데 구현을 잘 못하였다. (시간초과)
• 다른 분의 풀이를 보면서 깔끔하게 푸는 방법을 배울 수 있었다.
• 값이 0인 좌표 (i,j)를 찾아서 1부터 9까지 넣을 수 있는 값을 대입해보고 다음 0값을 가진 좌표 (p,q)를 또 가져와 계속 대입해가며 가능한 해결방법을 찾는 문제.
• 순서를 1부터 9까지 0행부터 8행까지 순서대로 해야지 사전식으로 알맞은 문제 답을 추출할 수 있다.
• 모든 과정을 살펴보는 것을 백트래킹이라 한다고 한다. 더 많이 풀어봐야 할 것 같다.

 

CODE

def find_empty():
    for i in range(9):
        for j in range(9):
            if board[i][j] ==0:
                return i, j
    return None, None

def valid(col, row, val): # (col,row) 위치 값이 val이 가능한지 문제 (행, 열, 박스 안에 val이 없으면 가능)
    for i in range (9):
        if board[col][i] == val: return False
        if board[i][row] == val: return False
    box_col = col//3
    box_row = row//3

    for i in range(3):
        for j in range(3):
            if board[box_col*3 + i][box_row*3 + j] == val:
                return False
    return True

def solution():
    col, row = find_empty() # 비어있는 값의 위치 찾기
    if col is None: # row가 None이여도 상관 없음(동치) 다 대입했다는 뜻
        return True
    else:
        for i in range(1,10):
            if valid(col, row, i):
                board[col][row] = i
                if solution():
                    return True
                board[col][row] = 0
        return False    



if __name__=='__main__':
    board = [list(map(int, input())) for _ in range(9)]
    solution()
    for i in range(9):
        print(*board[i], sep='')

 

같은 유형

https://www.acmicpc.net/problem/2580

2580번: 스도쿠