BOJ(스도쿠)(2580)

작성일 | In

스도쿠 2580

  • 9x9 크기의 게임 판에 1부터 9까지의 수만 1x1 칸에 넣을 수 있다.
  • 수를 넣는 순서는 행에 1-9 1개씩
  • 열에 1-9 1개씩

  • 3x3 크기에 1-9를 한개씩 넣는 방법이다.

  • 사람이 직접 푸는 방법은 컴퓨터가 푸는 방법과 다르다.
  • 사람은 스도쿠를 풀 때, 각각의 칸에 무엇이 들어가는지 유일하게 결정해서 넣어볼 수 있지만,
  • 컴퓨터의 장점은 무한번 시도를 해볼 수 있다는 것이기에, 일단 시도를 최대한 많이 해보는 방향으로 구현하면 된다.

  • 쭉 스도쿠 판을 살펴보면서 1~9까지를다 넣어보는 것이다.

  • 어떤 칸에 어떤 수를 넣을지, go(z)라는 것으로 결정할 것.
  • (x,y)를 넣는 것은 마지막 칸에서 열이 증가할 때, 다시 행을 증가시키는 코드를 구현해야 해서,

  • 수 하나로 놓은 뒤에 다시 이 값을 계산하는 방식을 이용할 예정.

  • 먼저 행에 1-9 검사
  • 그 다음 열에 1-9 검사
  • 마지막으로 작은 정사각형에 1-9가 하나씩 있는지 없는지를 검사해주면 된다.
  • c[i][j] = i 열에 숫자 j가 있으면 true
  • c2[i][j] = i 행에 숫자 j가 있으면 true
  • c3[i][j] = i번 작은 정사각형에 숫자 j가 있으면 true
  • 9x9 를 3x3으로 나눈 다음에, 각각의 행과 열을 모두 3으로 나누었다. 행과 열을 3으로 나누면
  • 행의 번호000 , 111, 222, 열의 번호도 000,111,222
  • 그 다음 0,1,2,3,4,5를 해주면 되는 것이다.
  • (x,y)는 (x//3)*3+(y//3)번째 칸

구현

  • 이 문제는 항상 n=9다.
  • z가 81이었다 ? 총 81개의 칸이 있고 0부터 채웠으니까. 80번째 칸을 채운 다음 칸은 81번째 칸이다. -> 모든 칸을 다 채웠으므로 출력을 해주고 프로그램을 종료시키면 된다.
def square(x, y):
    return (x//3)*3+(y//3)

def go(z):
    if z == 81: # 종료조건
        for row in a:
            print(' '.join(map(str,row))) # 출력
        return True
    x = z//n # z라는 값을 이용해서 n은 9이므로 r행 c열, x행 y열을 하나의 정수로 나타냈으므로, z를 구하려면 9를 나누고 % 연산을 해줘야 x와 y를 구할수 있다.
    y = z%n
    if a[x][y] != 0: # 0이 아니면 , 이미 채워져 있으므로 그냥 다음 칸을 채우라고 한다.
        return go(z+1)
    else: # 그 외의 경우라면 실제 수를 넣어야 한다.
        for i in range(1, 10): # 0부터 9까지가 아닌 1부터 9까지다. x행 y열에 i를 넣는다.
        # x행에 숫자 i가 없고, y열에도 숫자 i가 없고, 3x3 정사각형에도 y가 없어야 한다.
            if c[x][i] == False and c2[y][i] == False and c3[square(x,y)][i] == False:
                c[x][i] = c2[y][i] = c3[square(x,y)][i] = True
                a[x][y] = i
                if go(z+1):
                    return True
                a[x][y] = 0
                c[x][i] = c2[y][i] = c3[square(x,y)][i] = False
    return False
n = 9
a = [list(map(int,input().split())) for _ in range(n)]
c = [[False]*10 for _ in range(n)]
c2 = [[False]*10 for _ in range(n)]
c3 = [[False]*10 for _ in range(n)]
for i in range(n):
    for j in range(n):
        if a[i][j] != 0:
            c[i][a[i][j]] = True
            c2[j][a[i][j]] = True
            c3[square(i,j)][a[i][j]] = True
go(0)
  • 진짜 일반화된 스도쿠는 백트래킹으로 풀 수 없다.
  • 이 문제는 백트래킹으로 풀 수 있도록 변형되어있다.

참고자료 codeplus

0%