1580, 1/79 회원가입  로그인  
   Ilios
   [연습용 C자작] 스도쿠 소스

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 : 19312     Date : 2010/05/24 01:02



    
kjwon15 좋은 소스네요..
개인 소장 해도 되죠?
2010/05/26  
rlawldhs6996 와우 수고 하셧어요ㅋ 2010/05/26  
Ilios kjwon15 // 네 물론입니다 ㅎㅎㅎㅎㅎ
rlawldhs6996 // 감사합니다 ^^ ㅋ
2010/05/26  
kji0331 비베에 해두 되나요? 2010/08/10  
Cpgroot 수고 하셧음 ..ㅋ 2010/08/18  
     [공지] 강좌를 올리실 때는 말머리를 달아주세요^ㅡ^ [29] 멍멍 02/27 17656
1579   쉘코드 모음     해킹잘하고싶다
01/15 154
1578   Call by value VS Call by Reference     해킹잘하고싶다
01/15 71
1577   (꼼수) L.O.B 한방에 클리어하기[1]     해킹잘하고싶다
01/14 110
1576   towelroot.c (zip) 코멘팅.[2]     scube
08/18 2759
1575   levitator.c (안드로이드 루팅) 공격 분석 소스 코드 공유.[4]     scube
08/17 2787
1574   무료 정보보안 기술인재 양성 과정 교육생 모집     chanjung111
06/17 3478
1573   K-Shield 주니어 5기 모집     lrtk
06/17 3209
1572   [팁] 파이썬 2소스를 3으로 변경해주는 사이트[3]     한승재
05/13 2998
1571   구글 백링크 작업 질문요     wkatnxka
03/30 2602
1570   [팁] 우분투 미러링서버     한승재
03/09 2985
1569 비밀글입니다  감을못잡겠네요ㅜㅜ     잉잉잉
01/15 2
1568   데비안 계열 리눅스 의존성 깨졌을때 해결법     한승재
11/27 3313
1567   홍보합니다. 신생 보안커뮤니티입니다.     kimwoojin0952
10/26 3472
1566   신기한 프로그래밍 언어[3]     koreal33t
09/06 3797
1565   윈도우,리눅스에서 내 ip를 확인해 보자 [1]     koreal33t
09/06 3066
1564   CTF 사이트[1]     koreal33t
09/06 3556
1563   자격증 (문제)사이트 [2]     koreal33t
09/06 3452
1562   [퍼온글]리눅스 기본 명령어     한승재
06/06 4047
1561   [동강][퍼온글]C언어로 Hellow world를 출력해보자![2]     한승재
05/23 3643
1 [2][3][4][5][6][7][8][9][10]..[79]

Copyright 1999-2023 Zeroboard / skin by Hackerschool.org / Secure Patch by Hackerschool.org & Wowhacker.com