[알고리즘] 스도쿠 알고리즘 [KOI 2006-3]
코덕질/해탈내역들 2009/01/02 08:54
[KOI] 2006_3_고급알고리즘.rar파일 제목의 고급은 신경 안쓰셔도 됩니다.
이 프로그램은 스도쿠 판을 input.txt의 형식[원본 문제 url 참조]으로 입력받아서 output.txt로 출력합니다.
알고리즘의 원리는 다음과 같습니다 :
1. 스도쿠를 풀 x, y위치를 찾는다.
- 스도쿠 판을 쭉 돌면서 값이 0인 곳을 찾음
2. 스도쿠를 풀 x, y위치를 찾으면 그 행/열/구역(3x3)에서 없는 숫자를 찾습니다.
- 여기서는 num_x, num_y, num_area 배열을 이용해서 찾았습니다. 여기 부분은 더 최적화가 가능할듯 싶지만 전 여기에서 관두렵니다 -_-..
3. [2]의 과정에서 없을 경우에는 그냥 그 칸을 0으로 내버려두고, 다시 한번 [1], [2]의 과정을 반복하여 칸을 채웁니다.
- 스도쿠 판을 쭉 돌면서 값이 0인 곳을 찾음
2. 스도쿠를 풀 x, y위치를 찾으면 그 행/열/구역(3x3)에서 없는 숫자를 찾습니다.
- 여기서는 num_x, num_y, num_area 배열을 이용해서 찾았습니다. 여기 부분은 더 최적화가 가능할듯 싶지만 전 여기에서 관두렵니다 -_-..
3. [2]의 과정에서 없을 경우에는 그냥 그 칸을 0으로 내버려두고, 다시 한번 [1], [2]의 과정을 반복하여 칸을 채웁니다.
일단 샘플로 주어진 칸은 채우지만, 칸이 모두 0으로 처리되어 있다든지 하는 것은 채우지 못합니다. 이 경우에는 재귀함수로 처리하거나 저급 알고리즘을 이용하여 처리해야 하는데 이건 그냥 내버려 두도록 하겠.. [퍽퍽]
아, 이 알고리즘이 칸을 채우는 과정을 살펴보기 위해서 중간에 printf로 채우는 칸과 그 값을 확인할 수 있도록 하였는데 sudoku.h의 fillLocation함수 중간중간에 중단점을 걸으시면 확인이 가능할 듯 합니다 :D
댓글을 달아 주세요
여전히 뭔지 이해 불능...
여기는 그냥 내년 정보올림피아드 본선 준비하려고 공부해 본것 짬짬이 올려본 거예요 ^^;
고급이라는 말에 눈길이..;;
ㅋ;
여기도 단지 스도쿠의 문제를 해결하는 알고리즘이네요
스도쿠 생성알고리즘은 못만드신듯...
열공하세요...언젠간 만들어질듯..
흑... 저도 이거 풀고있는데..... 전 어찌 이것에서 이리도 빛이 날까요..? ㅠ
저에게는 너무 어렵....ㅠㅠ
지금 생각해보면 이거 되게 쉬운 문제였는데..라고 생각하고 있습니다 -_-;
그냥 3x3칸 중복처리를 위한 배열 9개, 행/열 중복처리를 위한 배열 9x2개를 준비한다음에 재귀함수 때려주면 연산량이 생각보다 적은지라 시간안에 잘 나오더라고요...