스도쿠 sudoku 풀이 알고리즘

http://www.sudoku.name/rules/ko

 

스도쿠 게임 규칙은 이와 같다.

 

9 X 9 셀안에 이미 주어진 숫자가 있다.

 

이때, 각각의 행과 열에는 1 ~ 9 숫자 중 유일하게 한 개의 숫자만 들어갈 수 있다.

 

이를 C로 풀이해내는 방법을 생각해보자.

 

일반적인 스도쿠 사이즈에 따라 9 X 9 사이즈의 배열이 필요할 것이다.

 

이 중, 이미 주어진 숫자들을 제외한 빈칸은 일단 0으로 채워넣어보자.

 

 

빈칸 0에 들어갈 숫자들을 알기 위해서 필요한 정보는 무엇일까?

 

1) 같은 행에 이미 들어간 숫자들 중에서 남은 숫자가 하나 들어간다.

 

2) 같은 열에 이미 들어간 숫자들 중에서 남은 숫자가 하나 들어간다.

 

3) 3 X 3 의 한 묶음 단위의 칸 들 중에서 남은 숫자가 하나 들어간다.

 

위 조건 3가지를 동시에 만족하는 숫자가 들어가게 된다.

 

간단하게, 1) 또는 2), 3) 중에서 8개의 숫자가 주어진 경우부터 생각해서 숫자를 채워가는 방법을 생각해볼 수 있을 것이다.

 

그럼, 일단 배열 값 넣으러 ~