Knight tour in C and with dynamic memorry allocation
Knight tour is an interesting problem. To summarize it:
Given an a x b sized board find the way that chess knight can visit all the squares landing in each square only once. There might be a situation without a valid way.
What makes this problem interesting in computer science is multiple ways it can be solved. Brute-forcing, heuristics, neuron networks to name a few. Also testing is made more difficult, because unless you know a priori that a way exists, there is no way to test the "There is no knight tour!" answer from your program.
To write a knight tour solving program first thing one should know is how knight can move. To illustrate available moves I took a picture from wikipedia.
legal knight moves
As you can see knight can move by 2 squares in one direction plus additional one square perpendicular to its 2 squares movement. Since it always can move to only 8 positions, calculating legal moves is not very difficult (compared let's say to queen).
Then the other thing is to choose method for finding knight tour. I went for straight forward wall head-banging (brute force). Also this way I had a chance to remember recursive programming. Algorithm is a really simple one - given starting position calculate all possible moves. Then narrow down the list by removing places you have already visited. From remaining list try first available. If after trying you did not finish knight tour, try other available. If you want to reuse my legal moves calculating function - heres the sequence I use for trying out moves.
knight moves numbered
Some things to remember:
- There might be a board without a knight tour.
- If there is a knight tour, there always will always be one in counter direction.
- Starting position does not have any difference. You are visiting all places anyway.
Next step - rewrite of this code using POSIX threads and adding some heuristics. Also - I promise to add results of benchmarks in the nearest future.
IMPORTANT: Add some sanity checking to user input!
Click "Continue reading" to get source code: Continue to knight tour source code
Source of main program:
#include <stdio.h> #include <stdlib.h> int move_knight(int **board, int *width, int *height, int movex, int movey, int numvisited); int *get_possible_moves(int **board, int *w, int *h, int *x, int *y); int main() { int w,h, startx, starty, i, k, numvisited, ret; printf("Starting knight tour!\n"); printf("Please enter board widht: "); scanf("%d",&w); printf("\nPlease enter board height: "); scanf("%d",&h); printf("\nAllocating memory for %d size board\n", w*h); int **board; board=malloc(h*sizeof(int)); if(board == NULL) { printf("Memory allocation failed! Exiting!"); return 1; } for(i = 0; i < h; i++) { board[i] = malloc(w * sizeof(int)); if(board[i] == NULL) { printf("Memory allocation failed! Exiting!"); return 1; } } printf("Please enter starting widht coordinate: "); scanf("%d",&startx); printf("\nPlease enter starting height coordinate: "); scanf("%d",&starty); if (startx > w || starty > h) { printf("\nStarting coordinates are off the board! Exiting!"); free(board); return 0; } printf("\nStarting coordinates are w: %d, h: %d\n", startx, starty); //Clear the memory region. We havent visited anything yet for(i=0;i<h;i++) { for(k=0;k<w;k++) { board[i][k] = 0; } } numvisited=0; ret = move_knight(board, &w, &h, startx, starty, numvisited); if(ret) { printf("There are no possible moves!\n"); } else { printf("Knight tour found!\n"); } for(i=0;i<h;i++) { free(board[i]); } free(board); return 0; }
Source of helper functions:
int *get_possible_moves(int **board, int *w, int *h, int *x, int *y) { // board - our current board state // w and h is size of board // x and y is our possition // return pointer to array with posibles moves // 1st char = number of possible moves // nth char = available x coord, n%2=0 // n+1 char = available y coord, (n+1)%2=0 int *posibilities=NULL; int movespossible=0; int moveslist[8][2]; //1 if(*x + 1 <= *w - 1 && *y - 2 >= 0) { if(board[*(int *)y - 2][*(int *)x + 1] == 0) { moveslist[movespossible][0] = *(int *)x + 1; moveslist[movespossible][1] = *(int *)y - 2; movespossible++; } } //2 if(*x + 2 <= *w - 1 && *y - 1 >= 0) { if(board[*(int *)y - 1][*(int *)x + 2] == 0) { moveslist[movespossible][0] = *(int *)x + 2; moveslist[movespossible][1] = *(int *)y - 1; movespossible++; } } //3 if(*x + 2 <= *w - 1 && *y + 1 <= *h - 1) { if(board[*(int *)y + 1][*(int *)x + 2] == 0) { moveslist[movespossible][0] = *(int *)x + 2; moveslist[movespossible][1] = *(int *)y + 1; movespossible++; } } //4 if(*x + 1 <= *w-1 && *y + 2 <= *h - 1) { if(board[*(int *)y + 2][*(int *)x + 1] == 0) { moveslist[movespossible][0] = *(int *)x + 1; moveslist[movespossible][1] = *(int *)y + 2; movespossible++; } } //5 if(*x - 1 >= 0 && *y + 2 <= *h - 1) { if(board[*(int *)y + 2][*(int *)x - 1] == 0) { moveslist[movespossible][0] = *(int *)x - 1; moveslist[movespossible][1] = *(int *)y + 2; movespossible++; } } //6 if(*x - 2 >= 0 && *y + 1 <= *h - 1) { if(board[*(int *)y + 1][*(int *)x - 2] == 0) { moveslist[movespossible][0] = *(int *)x - 2; moveslist[movespossible][1] = *(int *)y + 1; movespossible++; } } //7 if(*x - 2 >= 0 && *y - 1 >= 0) { if(board[*(int *)y - 1][*(int *)x - 2] == 0) { moveslist[movespossible][0] = *(int *)x - 2; moveslist[movespossible][1] = *(int *)y - 1; movespossible++; } } //8 if(*x - 1 >= 0 && *y - 2 >= 0) { if(board[*(int *)y - 2][*(int *)x - 1] == 0) { moveslist[movespossible][0] = *(int *)x - 1; moveslist[movespossible][1] = *(int *)y - 2; movespossible++; } } if(movespossible == 0) { posibilities = malloc(sizeof(int)); posibilities[0]=0; } else { posibilities = malloc(((movespossible*2)+1) * sizeof (int)); if (posibilities == NULL) { printf("Error No: 123 ;) \n"); } posibilities[0]=movespossible; int i=1; int k=0; for(i=1, k=0;k<movespossible;i+=2, k++) { posibilities[i]=moveslist[k][0]; posibilities[i+1]=moveslist[k][1]; } } return posibilities; } //return 1; //move failed //return 0; //move made to finish int move_knight(int **board, int *width, int *height, int movex, int movey, int numvisited) { //Need to check if we are in last sq //We are occupying one right now: numvisited++; int i = *(int *)width; int k = *(int *)height; //Total num of sqs int ik=i*k; //If we are in the last one - get back with success return value if(numvisited == ik) { return 0; } int ret, nn; // indicate in board matrix that we have visited our current place board[movey][movex]=1; // get legal moves from our possition int *movesavail = get_possible_moves(board, width, height, &movex, &movey); // if we have no available moves - step back if (movesavail[0]==0) { free(movesavail); movesavail=NULL; // unvisit our place board[movey][movex]=0; return 1; } //Try each available move for(i=1, k=0;k<movesavail[0];i+=2, k++) { //printf("Trying avail move: %d\n", k); nn=numvisited; ret = move_knight(board, width, height, movesavail[i], movesavail[i+1], nn); //In case we have filled full board! if(ret == 0) { printf("Succesfull move: x=%d y=%d\n", movesavail[i], movesavail[i+1]); free(movesavail); movesavail=NULL; return 0; } } // If we failed to reach end of board, unvisit our place board[movey][movex]=0; free(movesavail); movesavail=NULL; // Get back one step return 1; }