말로 풀어보는 스도쿠 알고리즘

교수님께서 naked single이라는 키워드로 힌트를 주셨으나,

 

스도쿠가 워낙 유명한 문제라 인터넷에 검색하면 답이 바로 나올게 분명하므로 안찾아보고...

 

 

 

큰 그림으로 그려보면

 

1. 스도쿠에 빈칸이 있다. ex) 스도쿠 매트릭스를 루프를 돌면서 원소가 0인 경우가 있다. -> 아래를 실행

 

2. 가로 행을 조사해서 cell 구조체의 head부터 linked list 자료 구조에 원소를 넣는다.

역시, 세로 행을 조사해서 같은 일을 한다.

동일한 box 내 원소를 조사해서 같은 일을 한다.

insert는 같은 원소는 제외하고, 1~9까지 오름차순으로

 

3. 다시 처음부터 스도쿠 매트릭스의 루프를 돌면서 각 셀의 구조체를 조사하며 linked list에서 그 원소 갯수가 8개인 경우를 찾는다.

1 ~ 9 까지 숫자 중 원소에 있는 숫자를 제외하고, final확정한다.

 

4. 1로 돌아가서 다시 2, 3을 순차적으로 루프. 1이 0이면 프로그램 종료하고, 스도쿠 출력