지환태 :: C언어 스도쿠 자동풀이 프로그램...

'스도쿠'에 해당되는 글 1건

2009/02/09 C언어 스도쿠 자동풀이 프로그램 (6)

C언어 스도쿠 자동풀이 프로그램

from Programming/C/C++ 2009/02/09 18:20

프로그램 다운로드

스도쿠.zip

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

int table[9][9];	//입력한 스도쿠 저장
int completed=0;	//완성된 스도쿠 갯수 저장
FILE *out;

typedef struct This		//빈칸을 가리키는 연결리스트
{
	int y,x;			//y행, x열 좌표
	int cand[10];		//후보숫자 표시배열
	struct This *next;	//다음칸
}blank;

blank *head, *tail;

//끝났는지 확인
int end()
{
	int i,j;

for(i=0; i<9; i++)
		for(j=0; j<9; j++)
			if(table[i][j]==0)	//빈 칸이 있으면
				return 0;		//0리턴
	return 1;
}

//입력
int input()
{
	int i,j;
	FILE *in=fopen("table.txt","r");

if(in==NULL)
		return 0;

for(i=0; i<9; i++)
		for(j=0; j<9; j++)
			fscanf(in," %1d",&table[i][j]);
	fclose(in);
	return 1;
}

//출력
void output()
{
	int i,j;

printf("%d 개 완성 더 만들어?\n입력따윈 ㅇ벗어 싫으면 그냥 꺼\n", ++completed);
	system("PAUSE");

fprintf(out,"%d :\n", completed);		//완성햇던 스도쿠의 갰수 출력
	for(i=0; i<9; i++, fprintf(out,"\n"))
		for(j=0; j<9; j++)
			fprintf(out," %d",table[i][j]);
}

//y열에 쓸 수 있는 후보숫자를 a배열에 표시
void row(int y,int *a)
{
	int i;
	for(i=0; i<9; i++)
		if(table[y][i]!=0)				//0이 아니면(이미 쓴 숫자면)
			a[table[y][i]]=0;			//a[쓰인 숫자]에 0(flase)표시
}

void col(int x,int *a)					//x열에 쓸 수 있는 후보숫자를 a배열에 표시
{
	int i;
	for(i=0; i<9; i++)
		if(table[i][x]!=0)				//0이 아니면(이미 쓴 숫자면)
			a[table[i][x]]=0;			//a[쓰인 숫자]에 0(flase)표시
}

//y행, x열이 포함된 3x3영역 에 쓸 수 있는 후보숫자를 a배열에 표시
void big(int y, int x, int *a)
{
	int i,j;
	for(i=y; i<y+3; i++)
		for(j=x; j<x+3; j++)
			if(table[i][j]!=0)			//0이 아니면(이미 쓴 숫자면)
				a[table[i][j]]=0;		//a[쓰인 숫자]에 0(flase)표시
}

//a, b, c후보숫자 배열의 교집합부분을 구함
void samesame(int *a, int *b, int *c)
{
	int i;
	for(i=1; i<=9;i++)
		a[i]=a[i]&b[i]&c[i];			//셋 다 1이면 1저장, 하나라도 0이면 0저장
}

//y행 x열칸에 쓸 수 있는 후보숫자를 구해 a에 표시
void get_cand(int y, int x, int *a)
{
	int i,j;
	int cand[3][10];
	for(i=0; i<3; i++)					//여기부터
		for(j=0; j<10; j++)				//
			cand[i][j]=1;				//여기까지 1로 초기화
	
	row(y,cand[0]);						//y행에 쓸 수 있는 후보숫자를 cand[0]배열에 저장
	col(x,cand[1]);						//x열에 쓸 수 있는 후보숫자를 cand[1]배열에 저장
	big((y/3)*3,(x/3)*3,cand[2]);		//y행, x열이 포함된 3x3영역 에 쓸 수 있는 후보숫자를 cand[0]배열에 저장
	samesame(cand[0],cand[1],cand[2]);	//위에서 구한 cand[0],cand[1],cand[2]배열의 교집합을 구해 cand[0]에 결과 저장
	memcpy(a,cand[0],sizeof(int)*10);	//a에 cand[0]복사
}

//빈 칸을 가리키는 연결리스트 생성
void set()
{
	int y, x;
	blank *temp;

temp=(blank *)malloc(sizeof(blank));
	head=(blank *)malloc(sizeof(blank));
	tail=(blank *)malloc(sizeof(blank));
	temp=head;

for(y=0; y<9; y++)
	{
		for(x=0; x<9; x++)
		{
			if(table[y][x]==0)		//빈 칸이면
			{
				temp->y=y;			//연결리스트에 저장하고
				temp->x=x;
				temp->next=(blank *)malloc(sizeof(blank));
				temp=temp->next;	//다음 연결리스트를 가리킴
			}
		}
	}
	tail=temp;
}

void solve(blank *node)
{
	int i;

if(node==tail)		//끝까지 왔으면
	{
		if( end() )		//풀렸으면
			output();	//출력
		return;
	}

get_cand(node->y,node->x,node->cand);	//후보숫자구함

for(i=1; i<=9; i++)
	{
		if(node->cand[i])					//쓸 수 있는 숫자면
		{
			table[node->y][node->x]=i;		//쓰고
			solve(node->next);				//다음칸으로 넘어감
			table[node->y][node->x]=0;		//다음 풀이에 영향을 주지 않기 위해 0으로 지움
		}
	}
}

int main()
{
	if( input()== 0)		//입력받고
	{
		printf("파일 입력 오류");
		return 0;
	}

out=fopen("output.txt","w");
	set();				//빈칸 연결리스트생성
	solve(head);		//백트래킹으로 풀이
	fclose(out);

}

프로그램 다운로드

스도쿠.zip

table.txt 파일에 스도쿠랑 똑같이 입력해주시면 됩니다. 빈칸은 0으로

입력확인같은건안해요.

5초이내에 안끝나면 잘못입력했는지 확인해보세요.

이 글이 유익하다면 (굽신굽신) ->

Tag // 스도쿠, 프로그램

Trackback(0) : Comment(6)

Trackback Address >> http://zfanta.com/trackback/439

Mr.번뜩맨 2009/02/17 16:39 address modify / delete reply
윽.. 어지럽다는...-_-;
- address modify / delete 2009/02/21 19:52 　환타
  온라인 대회따 쓰면 유용합니다 ㅎㅎ
파리 2011/10/09 17:16 address modify / delete reply
현기증발생
JulietteOneal26 2011/10/14 18:52 address modify / delete reply
People deserve very good life time and <a href="http://goodfinance-blog.com/topics/credit-loans">credit loans</a> or short term loan will make it better. Just because people's freedom relies on money.
인형 2012/01/11 12:40 address modify / delete reply
과부 사정 홀아비가 안다
이청용 2012/01/13 05:16 address modify / delete reply
빈 수레가 요란하다

지환태

'스도쿠'에 해당되는 글 1건

C언어 스도쿠 자동풀이 프로그램

Trackback Address >> http://zfanta.com/trackback/439

Category

Tags

Recent Post

Recent Comment

Link