首页 > 代码库 > 八皇后问题
八皇后问题
#pragma once #include <stdio.h> #include <malloc.h> #include <memory.h> #define N 10 typedef enum BOOL { TRUE=1, FALSE=0 }BOOL; typedef struct queen_node { int level; int position; }queen_node; typedef struct queen_stack { int pointer; int size; int volume; queen_node** container; }queen_stack; /*create a queen node.*/ void queen_node_create(queen_node** const the_node); /*initialize the queen node value.*/ void queen_node_init(queen_node* const the_node,const int level,const int position); /*free the queen node.*/ void queen_node_free(queen_node* const the_node); /*copy a queen node to another.*/ void queen_node_copy(queen_node* const the_destination,const queen_node* const the_source); /*get next queen node*/ void queen_node_next(queen_node* const the_node,const int level,const int position); /*create queen stack.*/ void queen_stack_create(queen_stack** const the_stack,const int stack_volume); /*free queen stack.*/ void queen_stack_free(queen_stack* const the_stack); /*push queen node to queen stack.*/ BOOL queen_stack_push(queen_stack* const the_stack,const queen_node* const the_node); /*pop queen node from queen stack.*/ BOOL queen_stack_pop(queen_stack* const the_stack,queen_node* const the_node); /*return the queen stack whether overflow.*/ BOOL queen_stack_overflow(const queen_stack* const the_stack); /*return the queen stack whether empty.*/ BOOL queen_stack_empty(const queen_stack* const the_stack); /*fill the number array with the stack data*/ void number_array_fill(int** const the_array,const queen_stack* const the_stack,const int array_dimension); /*create number array.*/ void number_arrary_create(int*** const the_arrary,const int array_dimension); /*assign number array.*/ void number_array_assign(int** const the_array,const int row,const int column,const int array_dimension); /*print number array data to screen.*/ void number_array_print(const int** const the_array,const int array_dimension); /*free number arrary data.*/ void number_array_free(int** const the_array,const int array_dimension); /*clear the number array data*/ void number_array_clear(int** const the_array,const int array_dimension); int main() { /*declare values.*/ int** the_array=NULL; queen_node* current_node=NULL; queen_stack* current_stack=NULL; int next_position=-1; int next_level=-1; int position_index=0; BOOL found=FALSE; /*create values.*/ number_arrary_create(&the_array,N); queen_node_create(¤t_node); queen_stack_create(¤t_stack,N+1); /*push root to stack*/ queen_stack_push(current_stack,current_node); while(queen_stack_empty(current_stack) == FALSE) { number_array_clear(the_array,N); number_array_fill(the_array,current_stack,N); found=FALSE; for(position_index=current_node->position+1;position_index<N;position_index++) { if(the_array[current_stack->pointer][position_index] == 0) { next_position=position_index; found=TRUE; break; } } if(found==FALSE) { queen_stack_pop(current_stack,current_node); } else { next_level=current_stack->pointer; queen_node_init(current_node,next_level,next_position); queen_stack_push(current_stack,current_node); queen_node_init(current_node,-1,-1); if(queen_stack_overflow(current_stack)==TRUE) { number_array_clear(the_array,N); number_array_fill(the_array,current_stack,N); number_array_print(the_array,N); queen_stack_pop(current_stack,current_node); } } } /*free number arrary.*/ number_array_free(the_array,N); the_array=NULL; /*free current node.*/ queen_node_free(current_node); current_node=NULL; /*free current stack.*/ queen_stack_free(current_stack); current_stack=NULL; return 0; } void queen_node_create(queen_node** const the_node) { (*the_node)=(queen_node*)malloc(sizeof(queen_node)); memset((*the_node),0,sizeof(queen_node)); (*the_node)->level=-1; (*the_node)->position=-1; } void queen_node_init(queen_node* const the_node,const int level,const int position) { the_node->level=level; the_node->position=position; } void queen_node_free(queen_node* const the_node) { free(the_node); } void queen_node_copy(queen_node* const the_destination,const queen_node* const the_source) { the_destination->level=the_source->level; the_destination->position=the_source->position; } void queen_node_next(queen_node* const the_node,const int level,const int position) { the_node->level=level; the_node->position=position; } void queen_stack_create(queen_stack** const the_stack,const int stack_volume) { (*the_stack)=(queen_stack*)malloc(sizeof(queen_stack)); memset((*the_stack),0,sizeof(queen_stack)); (*the_stack)->volume=stack_volume; (*the_stack)->pointer=-1; (*the_stack)->size=0; (*the_stack)->container=(queen_node**)malloc(sizeof(queen_node*)*(*the_stack)->volume); memset((*the_stack)->container,0,sizeof(queen_node*)*(*the_stack)->volume); } void queen_stack_free(queen_stack* const the_stack) { int volume_index=0; for(volume_index=0;volume_index<=the_stack->pointer;volume_index++) { queen_node_free(the_stack->container[volume_index]); the_stack->container[volume_index]=NULL; } free(the_stack->container); the_stack->container=NULL; free(the_stack); } BOOL queen_stack_push(queen_stack* const the_stack,const queen_node* const the_node) { if(the_stack->size < the_stack->volume) { the_stack->pointer++; queen_node_create(&(the_stack->container[the_stack->pointer])); queen_node_copy(the_stack->container[the_stack->pointer],the_node); the_stack->size++; return TRUE; } else { return FALSE; } } BOOL queen_stack_pop(queen_stack* const the_stack,queen_node* const the_node) { if(the_stack->size>0) { queen_node_copy(the_node,the_stack->container[the_stack->pointer]); the_stack->container[the_stack->pointer]=NULL; the_stack->pointer--; the_stack->size--; return TRUE; } else { return FALSE; } } BOOL queen_stack_overflow(const queen_stack* const the_stack) { return the_stack->size == the_stack->volume ? TRUE : FALSE; } BOOL queen_stack_empty(const queen_stack* const the_stack) { return the_stack->size == 0 ? TRUE : FALSE; } void number_arrary_create(int*** const the_arrary,const int array_dimension) { int arrary_index=0; (*the_arrary)=(int**)malloc(sizeof(int*)*array_dimension); memset((*the_arrary),0,sizeof(int*)*array_dimension); for(arrary_index=0;arrary_index<array_dimension;arrary_index++) { (*the_arrary)[arrary_index]=(int*)malloc(sizeof(int)*array_dimension); memset((*the_arrary)[arrary_index],0,sizeof(int)*array_dimension); } } void number_array_assign(int** const the_array,const int row,const int column,const int array_dimension) { int row_index=0; int column_index=0; the_array[row][column]=1; for(column_index=0;column_index<column;column_index++) { if(the_array[row][column_index] == 0) { the_array[row][column_index]=2; } } for(column_index=column+1;column_index<array_dimension;column_index++) { if(the_array[row][column_index] == 0) { the_array[row][column_index]=2; } } for(row_index=0;row_index<row;row_index++) { if(the_array[row_index][column] == 0) { the_array[row_index][column]=2; } } for(row_index=row+1;row_index<array_dimension;row_index++) { if(the_array[row_index][column] == 0) { the_array[row_index][column]=2; } } for(row_index=row-1,column_index=column-1;row_index>=0 && column_index>=0 ;row_index--,column_index--) { if(the_array[row_index][column_index] == 0) { the_array[row_index][column_index]=2; } } for(row_index=row+1,column_index=column+1;row_index<array_dimension && column_index<array_dimension;row_index++,column_index++) { if(the_array[row_index][column_index] == 0) { the_array[row_index][column_index]=2; } } for(row_index=row-1,column_index=column+1;row_index>=0 && column_index<array_dimension;row_index--,column_index++) { if(the_array[row_index][column_index] == 0) { the_array[row_index][column_index]=2; } } for(row_index=row+1,column_index=column-1;row_index<array_dimension && column_index>=0;row_index++,column_index--) { if(the_array[row_index][column_index] == 0) { the_array[row_index][column_index]=2; } } } void number_array_print(const int** const the_array,const int array_dimension) { int row_index=0; int column_index=0; static int number=1; printf("--------------- the %d queen data---------------\n\n",number++); for(row_index=0;row_index<array_dimension;row_index++) { for(column_index=0;column_index<array_dimension;column_index++) { if(the_array[row_index][column_index]==2) { printf("%d ",0); } else { printf("%d ",the_array[row_index][column_index]); } } printf("\n"); } printf("\n"); } void number_array_free(int** const the_array,const int array_dimension) { int row_index=0; for(row_index=0;row_index<array_dimension;row_index++) { free(the_array[row_index]); the_array[row_index]=NULL; } free(the_array); } void number_array_fill(int** const the_array,const queen_stack* const the_stack,const int array_dimension) { int stack_index=0; for(stack_index=the_stack->pointer;stack_index>0;stack_index--) { number_array_assign(the_array,the_stack->container[stack_index]->level,the_stack->container[stack_index]->position,array_dimension); } } void number_array_clear(int** const the_array,const int array_dimension) { int row_index=0; int column_index=0; for(row_index=0;row_index<array_dimension;row_index++) { for(column_index=0;column_index<array_dimension;column_index++) { the_array[row_index][column_index]=0; } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。