Hey, guys,
to begin with, I'm a complete newbie to C and I'm writing a Knight Tour program. The idea of my program is to check every possible way (it is necessary for the assignment), so I start with x + 1 & y + 2 and so on. If it reaches a square where no more options are available and the chessboard is not full yet, it goes back by one move and tries another possible way skipping the last one which failed. It works with most starting coordinates. With 5x5 board it solves every possibility in a matter of seconds. But I ran into difficulties with larger boards. For instance, 6x6 board - starting from (1, 1) square it solves this puzzle instantly. But from another square (1, 2) it keeps calculating forever. I know it's because of the order of checking available moves but why would it take so long? From another side of the board again - it solves it instantly. So the question would be, why does it take so much time calculating and never finding a solution?
Here are the main parts then:
struct figure {
int x, y, mov, movAvail[8];
struct figure *prev;
};
typedef struct figure list;
int main() {
<...>
setupKnight (&knight, x, y, board, n);
while (knight && !boardIsFull (board, n)) {
nextMove (&knight, board, n);
}
if (boardIsFull (board, n)) {
printBoard (board, n);
} else printf("No solution found.");
// Let's remove the knight
for (i = 0; i < n*n; i++) {
if (knight) {
temp = knight;
knight = temp->prev;
free(temp);
}
}
}setupKnight :
void setupKnight (list **knight, int x, int y, int **board, int n) {
int i;
(*knight) = malloc (sizeof(list));
(*knight)->x = x;
(*knight)->y = y;
(*knight)->mov = 1;
(*knight)->prev = NULL;
board[x][y] = 1;
for (i = 0; i < 8; i++)
(*knight)->movAvail[i] = 1;
}Now the main function, next possible move and also a function to check whether the possition is available:
int moveIsValid (int **board, int n, int x, int y, int mov) {
if ((x < 0) || (x >= n) || (y < 0) || (y >= n)) {
return FALSE;
}
if ((board[x][y] != 0) && (board[x][y] < mov)) {
return FALSE;
}
return TRUE;
}
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
int nextMove (list **knight, int **board, int n) {
if ((*knight)->mov == n*n)
return FINISHED;
int x = (*knight)->x;
int y = (*knight)->y;
int mov = (*knight)->mov;
list *temp = NULL;
mov++;
if (moveIsValid(board, n, (x+1), (y+2), mov) && ((*knight)->movAvail[0] != 0)) {
(*knight)->movAvail[0] = 0;
x+=1;
y+=2;
} else
if (moveIsValid(board, n, (x+2), (y+1), mov) && ((*knight)->movAvail[1] != 0)) {
(*knight)->movAvail[1] = 0;
x+=2;
y+=1;
} else
if (moveIsValid(board, n, (x+2), (y-1), mov) && ((*knight)->movAvail[2] != 0)) {
(*knight)->movAvail[2] = 0;
x+=2;
y-=1;
} else
if (moveIsValid(board, n, (x+1), (y-2), mov) && ((*knight)->movAvail[3] != 0)) {
(*knight)->movAvail[3] = 0;
x+=1;
y-=2;
} else
if (moveIsValid(board, n, (x-1), (y-2), mov) && ((*knight)->movAvail[4] != 0)) {
(*knight)->movAvail[4] = 0;
x-=1;
y-=2;
} else
if (moveIsValid(board, n, (x-2), (y-1), mov) && ((*knight)->movAvail[5] != 0)) {
(*knight)->movAvail[5] = 0;
x-=2;
y-=1;
} else
if (moveIsValid(board, n, (x-2), (y+1), mov) && ((*knight)->movAvail[6] != 0)) {
(*knight)->movAvail[6] = 0;
x-=2;
y+=1;
} else
if (moveIsValid(board, n, (x-1), (y+2), mov) && ((*knight)->movAvail[7] != 0)) {
(*knight)->movAvail[7] = 0;
x-=1;
y+=2;
} else {
board[x][y] = 0;
if ((*knight)->prev) {
temp = (*knight);
(*knight) = (*knight)->prev;
free(temp);
mov--;
return FALSE;
}
free((*knight));
(*knight) = NULL;
return FALSE;
}
int i;
temp = malloc(sizeof(list));
board[x][y] = mov;
for (i = 0; i < 8; i++)
temp->movAvail[i] = 1;
temp->x = x;
temp->y = y;
temp->mov = mov;
temp->prev = *knight;
(*knight) = temp;
return TRUE;
}