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

앞서 n qeen 문제랑 같은 유형인 back tracking 문제였는데 또 스스로 풀지 못하였다.

꽤나 절망스럽지만 어려운 문제도 하나 두개씩 도전하다보면 스스로도 풀 수 있겠지 하고 심심한 위로를 해본다.

우선 접근방식은 이러하다.

스도쿠 판을 board라는 이차원 배열로 표현했다고 하자.

이차 반복문을 돌면서 board의 요소중에 0인 칸에 직접 숫자를 1 ~ 9 까지 집어 넣어 보는 것이다.

이때 스도쿠의 규칙이 적용되는데

1. 같은 열에 같은 숫자가 있을 수 없다. (같은 열에는 1~9까지의 숫자가 한 번씩 있어야 한다.)
2. 같은 행에 같은 숫자가 있을 수 없다. (같은 행에는 1~9까지의 숫자가 한 번씩 있어야 한다.)
3. 같은 영역(3*3만큼이 하나의 영역이라고 하자, 예를 들어 board[0][0]~board[2][2]까지가 한 영역이다.) 에 같은 숫자가 있을 수 없다. (같은 영역에는 1~9까지의 숫자가 한 번씩 있어야 한다.)

순서도로 표현하면 이런식이다.

이런식이라면 굳이 재귀로 풀 필요도 없을 것 같다. 하지만 문제는 여기서 일어난다.

앞선 절차를 따라 board[4][3] = 3을,

board[4][4] = 1 이 들어갔다. 그리고