스도쿠 소스 코드 Sudoku Sourcecode

 

sudoku.zip

 

작년에 만든 스도쿠 풀이 알고리즘

 

데이터 구조론 수업 마지막 레포트로 만든 것.

 

9 x 9 배열에 스도쿠 문제를 입력하면 자동으로 값을 내줍니다.

 

 

2012/11/02 - [노트정리/알고리즘 놀이] - 스도쿠 sudoku 풀이 알고리즘

 

2012/11/11 - [공돌이공부거리/데이터 구조론 Data Structure] - 말로 풀어보는 스도쿠 알고리즘

 

2012/11/15 - [공돌이공부거리/데이터 구조론 Data Structure] - 말로 풀어보는 스도쿠 알고리즘 - 자료 구조 선택

 

2012/11/22 - [공돌이공부거리/데이터 구조론 Data Structure] - 스도쿠 sudoku 히든 싱글 개념 hidden single

 

 

#include
#include
#include
#include
#include
using namespace std;

//////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////이번 스도쿠 프로그램에서 사용될 자료 구조들/////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
class cell{
public:
	int n; //스도쿠에 들어갈 값이다.
	bool filled; //스도쿠가 차있냐 아니냐? 모두 차 있다면 스도쿠 출력하고 프로그램 종료, 차 있다면 1, 아니면0
	list candid; //행, 열, 박스내에 있는 값들을 제외한 숫자.
	int number_of_box; //현재 셀의 박스 번호
};

//배열을 순회하면서 0이 아닌 값을 찾아서 스택에 넣어둔다.
class stack_data{
public:
	stack row; //0이 아닌 값의 row
	stack col; //0이 아닌 값의 col
	stack hint; //0이 아닌 값의 hint
};

class near_boxes{
public:
	int number_of_box;
	list candid;
};
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////이번 스도쿠 프로그램에서 사용될 함수들의 PROTOTYPE//////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
void print_elements(const vector>& v);
void input_value(vector>& v);
void find_box(const vector>& sudoku,near_boxes near_box[],int i,int boxis,int boxie,int s,int boxje, cell temp_cell[][9]);
void call_find_box(vector>& sudoku, near_boxes near_box[], cell temp_cell[][9]);
void find_filled(const vector>& sudoku, cell temp_cell[][9]);
void stack_to_hint(const vector>& sudoku, stack_data& stack_hint);
void ini_cell_candid(cell temp_cell[][9]);
void cross_out(stack_data& stack_hint, cell temp_cell[][9]);
void box_out(near_boxes near_box[], cell temp_cell[][9]);
void find_naked_single(cell temp_cell[][9]);
void find_naked_single(cell temp_cell[][9], vector>& sudoku);
void print_candid(cell temp_cell[][9]);
int count_filled(cell temp_cell[][9]);
void hidden_vertical(cell temp_hidden_single_cell[][9], cell temp_cell[][9], vector>& sudoku, stack_data stack_hint, near_boxes near_box[], int& count);
void copy_to_cell(cell temp_cell[][9], cell temp_hidden_single_cell[][9]);
void hidden_horizon(cell temp_hidden_single_cell[][9], cell temp_cell[][9], vector>& sudoku, stack_data stack_hint, near_boxes near_box[], int& count);
void hidden_box(cell temp_hidden_single_cell[][9], cell temp_cell[][9], vector>& sudoku, stack_data stack_hint, near_boxes near_box[], int& count);
void call_naked_single(vector>& sudoku, cell temp_cell[][9], cell temp_hidden_single_cell[][9], stack_data stack_hint, near_boxes near_box[], int& count);
void call_hidden_single(vector>& sudoku, cell temp_cell[][9], cell temp_hidden_single_cell[][9], stack_data stack_hint, near_boxes near_box[], int& count);
void initialize(vector>& sudoku, cell temp_cell[][9]);
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////이번 스도쿠 프로그램의 main 함수///////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main(){
	//스도쿠 메인에서 필요한 변수들
	stack_data stack_hint; //스도쿠에 있는 숫자들의 위치와 숫자의 값
	cell temp_cell[9][9]; //스도쿠에 대한 정보를 넣어둘 임시 cell
	cell temp_hidden_single_cell[9][9];
	near_boxes near_box[9]; //박스는 총 9개 이므로 박스 번호는 0~8
	vector> sudoku(9, vector(9)); //9 X 9 벡터

	initialize(sudoku, temp_cell);

	int count=0, post_count=count;

	while(count!=81){

		call_naked_single(sudoku, temp_cell, temp_hidden_single_cell, stack_hint, near_box, count);

		if(post_count==count){
			call_hidden_single(sudoku, temp_cell, temp_hidden_single_cell, stack_hint, near_box, count);
		} else {
			post_count=count;
		}
	}

	print_elements(sudoku);

	return 0;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////이번 스도쿠 프로그램에서 사용될 함수들/////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
//vector로 된 sudoku를 화면에 출력하는 함수
void print_elements(const vector>& v){
	int i,j;
	cout<<"현재 9 X 9의 모습은 아래와 같습니다."<>& v){
	int a[9][9]={{7,0,0,0,0,0,0,0,9},
				{5,2,0,0,1,0,0,3,4},
				{0,6,0,7,0,9,0,5,0},
				{0,0,0,6,0,4,0,0,0},
				{4,0,0,0,0,0,0,0,7},
				{0,0,0,2,0,1,0,0,0},
				{0,5,0,4,0,8,0,1,0},
				{1,9,0,0,6,0,0,4,8},
				{8,0,0,0,0,0,0,0,2}}; //벡터에 입력을 편하게 하기 위한 꼼수.

	for(int i=0 ; i<9 ; i++){
		for(int j=0 ; j<9 ; j++){
			v[i][j]=a[i][j];
		}
	}
}


//박스를 순회하며 박스 내 값들을 near_box 에 넣어둔다.
//다시 박스를 순회하며 해당 박스의 스도쿠 값 중 0인 곳의 temp_cell.assigned 에 near_box의 값들을 넣어둔다.
//near_boxes를 함수에 넘겨줄 때, 1차원 배열의 경우 배열만 넘겨주면 알아서 주소값이 넘어가지만, 클래스는 아래와 같이 넘겨야함
void find_box(const vector>& sudoku,near_boxes near_box[],int i,int boxis,int boxie,int s,int boxje, cell temp_cell[][9]){
	for(;boxis>& sudoku, near_boxes near_box[], cell temp_cell[][9]){
	for(int z=0 ; z<9 ; ++z){
		near_box[z].candid.clear();
	}

	for(int i=0,boxis=0,boxie=3 ; boxis<=6,boxie<=9 ; boxis+=3,boxie+=3){
		for(int boxjs=0,boxje=3 ; boxjs<=6,boxje<=9 ; boxjs+=3,boxje+=3){
			find_box(sudoku,near_box,i,boxis,boxie,boxjs,boxje,temp_cell);
			//cout은 검사용
			//cout<<" i= "<>& sudoku, stack_data stack_hint, near_boxes near_box[], int& count){			
	for(int i=0 ; i<9 ; ++i){
		for(int j=0 ; j<9 ; ++j){
					
			copy_to_cell(temp_cell, temp_hidden_single_cell);

			for(int k=0 ; k<9 ; ++k){
				if(temp_hidden_single_cell[i][j].filled==0 && temp_cell[k][j].filled==0 && i!=k){
					for(list::iterator l=temp_cell[k][j].candid.begin() ; l!=temp_cell[k][j].candid.end() ; ++l){
						temp_hidden_single_cell[i][j].candid.remove(*l);
					}
				}
			}

			if(temp_hidden_single_cell[i][j].candid.size()==1 && temp_hidden_single_cell[i][j].filled==0){
				sudoku[i][j]=temp_hidden_single_cell[i][j].candid.front();
				temp_cell[i][j].filled=1;
				temp_hidden_single_cell[i][j].filled=1;

				find_filled(sudoku, temp_cell); //스도쿠에 값이 차 있는지 검사
				stack_to_hint(sudoku, stack_hint); //스도쿠를 돌며 0이 아닌 값이 있다면, 스택에 넣어둔다.
				cross_out(stack_hint, temp_cell);
				call_find_box(sudoku, near_box, temp_cell);
				box_out(near_box, temp_cell);
				find_naked_single(temp_cell, sudoku);
				count=count_filled(temp_cell);
			}
		}
	}
}

void copy_to_cell(cell temp_cell[][9], cell temp_hidden_single_cell[][9]){
	for(int i=0 ; i<9 ; ++i){
		for(int j=0 ; j<9 ; ++j){
			temp_hidden_single_cell[i][j].filled=temp_cell[i][j].filled;
			temp_hidden_single_cell[i][j].candid.clear();
			for(list::iterator k=temp_cell[i][j].candid.begin() ; k!=temp_cell[i][j].candid.end() ; ++k){
				temp_hidden_single_cell[i][j].candid.push_back(*k);
			}
			temp_hidden_single_cell[i][j].number_of_box=temp_cell[i][j].number_of_box;
		}
	}
}
void hidden_horizon(cell temp_hidden_single_cell[][9], cell temp_cell[][9], vector>& sudoku, stack_data stack_hint, near_boxes near_box[], int& count){			
	for(int i=0 ; i<9 ; ++i){
		for(int j=0 ; j<9 ; ++j){

			copy_to_cell(temp_cell, temp_hidden_single_cell);

			for(int k=0 ; k<9 ; ++k){
				if(temp_hidden_single_cell[i][j].filled==0 && temp_cell[i][k].filled==0 && j!=k){
					for(list::iterator l=temp_cell[i][k].candid.begin() ; l!=temp_cell[i][k].candid.end() ; ++l){
						temp_hidden_single_cell[i][j].candid.remove(*l);
					}
				}
			}

			if(temp_hidden_single_cell[i][j].candid.size()==1 && temp_hidden_single_cell[i][j].filled==0){
				sudoku[i][j]=temp_hidden_single_cell[i][j].candid.front();
				temp_cell[i][j].filled=1;
				temp_hidden_single_cell[i][j].filled=1;

				find_filled(sudoku, temp_cell); //스도쿠에 값이 차 있는지 검사
				stack_to_hint(sudoku, stack_hint); //스도쿠를 돌며 0이 아닌 값이 있다면, 스택에 넣어둔다.
				cross_out(stack_hint, temp_cell);
				call_find_box(sudoku, near_box, temp_cell);
				box_out(near_box, temp_cell);
				find_naked_single(temp_cell, sudoku);
				count=count_filled(temp_cell);
			}
		}
	}
}

void hidden_box(cell temp_hidden_single_cell[][9], cell temp_cell[][9], vector>& sudoku, stack_data stack_hint, near_boxes near_box[], int& count){			
	for(int i=0 ; i<9 ; ++i){
		for(int j=0 ; j<9 ; ++j){

			copy_to_cell(temp_cell, temp_hidden_single_cell);

			for(int k=0 ; k<9 ; ++k){
				for(int l=0 ; l<9 ; ++l){
					if(temp_hidden_single_cell[i][j].number_of_box==temp_cell[k][l].number_of_box
						&& temp_hidden_single_cell[i][j].filled==0 && temp_cell[k][l].filled==0 && !(i==k && j==l)){
						for(list::iterator m=temp_cell[k][l].candid.begin() ; m!=temp_cell[k][l].candid.end() ; ++m){
							temp_hidden_single_cell[i][j].candid.remove(*m);
						}
					}
				}
			}

			if(temp_hidden_single_cell[i][j].candid.size()==1 && temp_hidden_single_cell[i][j].filled==0){
				sudoku[i][j]=temp_hidden_single_cell[i][j].candid.front();
				temp_cell[i][j].filled=1;
				temp_hidden_single_cell[i][j].filled=1;

				find_filled(sudoku, temp_cell); //스도쿠에 값이 차 있는지 검사
				stack_to_hint(sudoku, stack_hint); //스도쿠를 돌며 0이 아닌 값이 있다면, 스택에 넣어둔다.
				cross_out(stack_hint, temp_cell);
				call_find_box(sudoku, near_box, temp_cell);
				box_out(near_box, temp_cell);
				find_naked_single(temp_cell, sudoku);
				count=count_filled(temp_cell);
			}
		}
	}
}

void call_naked_single(vector>& sudoku, cell temp_cell[][9], cell temp_hidden_single_cell[][9], stack_data stack_hint, near_boxes near_box[], int& count){
	find_filled(sudoku, temp_cell); //스도쿠에 값이 차 있는지 검사
	stack_to_hint(sudoku, stack_hint); //스도쿠를 돌며 0이 아닌 값이 있다면, 스택에 넣어둔다.
	cross_out(stack_hint, temp_cell);
	call_find_box(sudoku, near_box, temp_cell);
	box_out(near_box, temp_cell);
	find_naked_single(temp_cell, sudoku);
	count=count_filled(temp_cell);
}

void call_hidden_single(vector>& sudoku, cell temp_cell[][9], cell temp_hidden_single_cell[][9], stack_data stack_hint, near_boxes near_box[], int& count){
	hidden_vertical(temp_hidden_single_cell, temp_cell, sudoku, stack_hint, near_box, count);
	hidden_vertical(temp_hidden_single_cell, temp_cell, sudoku, stack_hint, near_box, count);
	hidden_horizon(temp_hidden_single_cell, temp_cell, sudoku, stack_hint, near_box, count);			
}
void initialize(vector>& sudoku, cell temp_cell[][9]){
	ini_cell_candid(temp_cell); //임시 셀의 candid에 일단 1 ~ 9 까지 숫자를 전부 넣어둔다.
	input_value(sudoku); //배열의 값을 스도쿠 벡터에 넣어준다.
}