1580, 3/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 : 19240     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  
1540   [자작] ssh / sftp 사용법 정리 (포트설정시)[1]     soohosin
02/15 20366
1539   D.H 의 HTML 강의 (1) 해킹의 기초[13]     DH_ 99
10/12 20133
1538   [자작]해킹하는데 C언어는 필요한가     dontknow
07/23 20071
1537   어셈블리어 강좌 5편     asdzxc301
12/13 19801
1536   cmos비밀번호 푸는 방법[25]     idl0521
12/29 19396
  [연습용 C자작] 스도쿠 소스[5]     Ilios
05/24 19239
1534   해킹당한 서버에서 확인해야할일[9]     소유
09/21 19169
1533   패스워드 알아내기 1[15]     geniusevil
12/15 19045
1532   [C기초] 12 - 삼항연산자(3항연산자)     sihun1113
05/01 18924
1531   네트워크 개념 휘어잡기 1[24]     소유
09/10 18628
1530   어셈블리어 총정리 강좌     asdzxc301
12/13 18609
1529   좋은 비밀번호란???[24]     소유
09/04 18397
1528   [펌] 리눅스 job, bg, fg에 관한 고찰[1]     qpt0707
04/06 18214
1527   [c언어] 문자열을 입력받아 거꾸로 출력하기[8]     H.R.T
12/15 17933
1526   sql 인젝션 공격기법[4]     subroutine
01/11 17865
1525   C언어로 만든 그래픽 프로그램[11]     승리의박성환
04/22 17858
1524   유치원 만화 크게보기[11]     소유
09/03 17710
1523   [자작] 한번 분석해본 보이스채팅 프로그램.[7]     푸른하늘
08/23 17698
     [공지] 강좌를 올리실 때는 말머리를 달아주세요^ㅡ^ [29] 멍멍 02/27 17578
1521   해커스랩 레벨 0 깨는 방법 - 시작하기[22]     불사
05/21 17368
[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