السلام عليكم ورحمة الله وبركاته
احاول عمل برنامج لحل مشكلة knights tour problem
قمت بحل هذه المشكله على لوحه 3*3 كالاتي:
/* Program NKnightsLIST.c */
#include <stdio.h>
#include <stdlib.h>
#define SIZE 3
struct Point{
int x, y;
};
struct node {
int depth;
Point position;
// char move;
struct node * parent;
int liveChildCount;
struct node * next;
struct node * prev;
};
struct Queue{
struct node * head;
struct node * tail;
struct node * current;
};
//---------------------------------------------------
int checkValidMove(struct Point A,struct Point B)
{
int ok = 1;
if(A.x<1||A.x>SIZE||B.x<1||B.x>SIZE||A.y<1||A.y>SIZE||B.y<1||B.y>SIZE)
return !ok;
if(abs((A.x-B.x)*(A.y-B.y))==2)return ok;
else return !ok;
}
void printBoard(struct node * n)
{
int i, j;
node * ptr;
static int count = 0;
ptr=n;
for (i = 1; i <=SIZE; i++)
{
for (j = 1; j<=SIZE; j++)
{
while(ptr!=NULL)
{ if(ptr->position.x==i&&ptr->position.y==j){ printf(" %2d ",ptr->depth);break;}
ptr=ptr->parent;
}
if(ptr==NULL) printf(" ");
ptr=n;
}
printf("\n");
}
count ++;
}
void printSolution(struct Queue * q){
printBoard(q->tail);
}
int checkAll(struct node * n){
static int longestSize = 0;
int ok = 1;
if(n->depth> longestSize)
{
longestSize = n->depth;
printf("Size:%d\n",longestSize);
printBoard(n);
printf("\n");
}
if(n->depth!=SIZE*SIZE) return !ok;
else return ok;
}
int checkSolution(struct node * L){
return (checkAll(L));
}
int repeat(struct node * l, struct node * c){
node * ptr=c;
while(ptr!=NULL)
{
if((l->position.x == ptr->position.x) && (l->position.y == ptr->position.y)) return 1;
ptr=ptr->parent;
}
return 0;
}
void findChildren(struct node * c, struct node * L[8]){
int count = 0;
int i, j, k;
Point moves[8]={{1,2},{2,1},{-1,2},{2,-1},{1,-2},{-2,1},{-1,-2},{-2,-1}};
for( i = 0; i<8;i++)
{ L=NULL;
L[count]=(struct node *)malloc(sizeof(struct node));
if(L[count]==NULL){printf("ERROR:no memory\n");exit(1);}
L[count]->liveChildCount=0;
L[count]->depth = c->depth +1;
L[count]->position.x=c->position.x+moves.x;
L[count]->position.y=c->position.y+moves.y;
if(!checkValidMove(L[count]->position,c->position)||(repeat(L[count],c)))
{ free(L[count]);L[count]=NULL;}
else
{
count++;
}
}
}
//---------------------------------------------
struct node * removeHead(struct Queue * q){
struct node * head;
if(q->head!=NULL){
head = q->head;
q->head=q->head->next;
head->prev=NULL;
head->next=NULL;
}
if(q->head==NULL){
q->tail=NULL;
}
return head;
}
void add(struct node * c, struct Queue * q){
if(q->head==NULL)
{
q->head=c;
q->tail=c;
q->head->prev=NULL;
} else
{
q->tail->next = c;
c->prev=q->tail;
q->tail=c;
}
}
void addChild(struct node * parent,struct node * child, struct Queue * q){
add(child, q);
q->tail->parent = parent;
parent->liveChildCount ++;
}
void expand(struct node * c, struct Queue * q){
int i;
static long int expanded=0;
struct node * list[8];//maximum of 8 successors
findChildren(c,list);
for(i=0;i<8;i++){
if(list!=NULL){
addChild(c, list,q);
// printBoard(q->tail);
// getchar();
expanded++;
// if(expanded%100==0)printf(".");
if(checkSolution(list)) {
printf("found solution\n");
printSolution(q); exit(1);}
}
}
}
void initialise(struct Queue * queue)
{
int k;
queue->head->liveChildCount=0;
queue->head->depth=1;
queue->head->position.x=1;
queue->head->position.y=1;
queue->head->liveChildCount=0;
}
int main(int argc, char * argv){
int input=0;
printf("%d\n",SIZE);
scanf("%d", &input);
if(input==1) exit(1);
if(input>SIZE){ printf("Too big !\n"); exit(0); }
struct Queue queue, expanded;
struct node *current;
expanded.head=NULL;
expanded.tail=NULL;
expanded.current=NULL;
queue.head=(struct node *) malloc(sizeof(struct node));
initialise (&queue);
queue.head->parent=NULL;
queue.head->next=NULL;
queue.head->prev=NULL;
expanded.tail=NULL;
expanded.current=NULL;
while(queue.head!=NULL)
{
current=removeHead(&queue);
expand(current, &queue);
add(current, &expanded);
}
printf("No Solution\n");
return 0;
}
لقد ارفقت ال كود بشكل افضل حيث يمكن استعماله
برنامجي ياحذ وقت خيالي لحل 8*8 .... هل يمكن مساعدتي لحل هذه المشكله
شكرا