|
http://www.hackerschool.org/HS_Boards/zboard.php?id=Free_Lectures&no=1460 [복사]
#include<fstream>
using namespace std;
file *fin=fopen("input.txt", "r");
file *fout=fopen("output.txt", "w");
void back(int point);
int data[10][10];
int row_chk[10][10], col_chk[10][10];
int square_num[10][10], square_chk[10][10], square_cnt;
int zero_point[110][3], zero_cnt;
int main(){
int i, j, k, l;
for(i=1; i<=9; i+=3){
for(j=1; j<=9; j+=3){
square_cnt++;
for(k=i; k<i+3; k++){
for(l=j; l<j+3; l++){
square_num[k][l] = square_cnt; // 3*3 배열 크기로 각 사각형에 번호를 부여
}
}
}
}
for(i=1; i<=9; i++){
for(j=1; j<=9; j++){
fscanf(fin, "%d", &data[i][j]); // data[i][j] 를 입력받는다.
if(data[i][j]){
row_chk[i][data[i][j]]=1; // 가로줄 체크 배열에 data[i][j] 가 쓰였다는 것을 체크
col_chk[j][data[i][j]]=1; // 세로줄 체크 배열에 data[i][j] 가 쓰였다는 것을 체크
square_chk[square_num[i][j]][data[i][j]]=1; // 사각형 체크 배열에 data[i][j] 가 쓰였다는 것을 체크
}
else{
zero_point[++zero_cnt][1] = i; // 0의 개수를 세주면서 0의 좌표를 저장해놓는다
zero_point[zero_cnt][2] = j;
}
}
}
back(0); // 백트레킹 시작
fclose(fin);
fclose(fout);
return 0;
}
void back(int point){
int i, j;
int x, y;
if(point == zero_cnt){ // 0을 모두 채웠다면
for(i=1; i<=9; i++){
for(j=1; j<=9; j++){
fprintf(fout, "%d ", data[i][j]); // 출력
}
fprintf(fout, "\n");
}
exit(0); // 더 돌면 안 되니까 종료
}
x = zero_point[point+1][1]; // point+1 번째의 0의 좌표를 얻어옴
y = zero_point[point+1][2];
for(i=1; i<=9; i++){
if(!row_chk[x][i] && !col_chk[y][i] && !square_chk[square_num[x][y]][i]){ // data[x][y] 에 넣을 i값이 이미 쓰였던 값인지 확인
row_chk[x][i] = col_chk[y][i] = square_chk[square_num[x][y]][i] = 1; // 쓰였다고 체크
data[x][y] = i; // data[x][y] 에 값을 채워넣는다.
back(point + 1); // 다음 0을 향해 전진ㅋ
data[x][y] = row_chk[x][i] = col_chk[y][i] = square_chk[square_num[x][y]][i] = 0; // 돌아오면서 초기화(다음 작업을 위해)
}
}
}
사용법
: exe 파일이 있는 폴더 안에 input.txt 와 output.txt 를 생성해 놓은 후
input 파일 안에 스도쿠 형식으로 값을 입력해 놓은 후 실행한다.
(입력 형식은 빈 칸을 0으로 채워넣고, 띄어쓰기를 하면 됩니다.)
알고리즘(?)
: 백트레킹 알고리즘을 이용했습니다.
가로줄 체크 배열과 세로줄 체크 배열, 1번 부터 9번 까지의 체크 배열을 이용해서,
0으로 체크된 비어있는 칸에 값을 집어넣고 다음 빈칸으로 진행하다가, 더 이상 진행할 수 없다고 판단되는 곳(넣을 값이 한정되어 있지만, 그 값들이 모두 체크 배열에 이미 체크가 되어 있는 상태일 때)에서 return 해 돌아와서 다시 다른 값을 집어넣는 식으로 하였습니다.
- 예전에 정올준비할대 했었던 건데, 다시 보니 새롭네요; 참고로 이건 윈도우의 Visual Studio C++ 환경에서 제작한겁니다.
예시)
input)
4 0 5 0 0 0 8 0 0
3 9 0 0 0 0 5 0 0
1 0 0 0 0 0 0 0 2
0 0 0 0 0 4 0 0 0
6 8 0 0 0 0 0 0 1
2 0 0 0 9 1 0 0 0
0 0 0 4 5 0 0 9 0
0 0 2 0 0 0 3 0 0
9 1 0 0 8 0 0 0 4
output)
4 2 5 9 1 7 8 6 3
3 9 8 2 4 6 5 1 7
1 6 7 5 3 8 9 4 2
7 5 1 8 2 4 6 3 9
6 8 9 3 7 5 4 2 1
2 3 4 6 9 1 7 8 5
8 7 3 4 5 2 1 9 6
5 4 2 1 6 9 3 7 8
9 1 6 7 8 3 2 5 4
|
Hit : 20087 Date : 2010/05/24 01:02
|
176, 
3/9 
kjwon15
