Member Avatar for Vytautas

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;
}

+1 point for using code tags. :-)

-1 point for not searching this website for one of many examples of the Knights Tour :-(


net score: neutral :-|

.

Member Avatar for Vytautas

I actually did search for those and studied all of them. I didn't find anything related to my current problem. And I don't want to borrow codes as I want to learn and currently I've ran out of ideas what could be wrong. It seems like it won't find a solution with certain coordinates but it should as it finds them with smaller one's. Maybe the linked list gets messed up somehow?

Anyway, thank you for your fast reply :)

commented: cool +7

I'll tell ya now, backtracking is the wrong way to go about it. you'll get to a 5x5 board and then the time will just grow ridiculously long.

if you searched around a bit, you would see that the Warnsdorff's Algorithm is the easiest method to calculate a solution. It's also very quick. other solutions will solve larger and larger boards, but this one will totally suffice for a normal sized board.

A couple years ago, I posted a non-recursive Warnsdorff implementation in this forum that will solve any position on an 8x8 board less than a second. you just need to think about how this algorithm. you will need to rewrite a lot of code that you have. just get used to it, i have to rewrite stuff all the time.

Member Avatar for Vytautas

if you searched, you would see that the Warnsdorff's Algorithm is the easiest method to calculate a solution and will complete all 64 moves in less than a second.

Yes, I forgot to mention that I have already written Warnsdorff's algorithm but I need both to work. After all, Warnsdorff's doesn't always find a solution when it is possible. And I'm writting this one so I'm able to compare them. I've already noticed that backtracking is a poor choice for such programs, it could take forever to find a good solution for 6x6, 7x7 and so on. *Don't do this, kids* :)

yeah, i don't know how else i would do it. backtracking is an untenable method. theres just no point even trying, IMO

some folks talk about Schenk's Theorem and Hamiltonian Paths, but I'm afraid I'm not clever enough to understand it much less apply it. And I don't have a need or care to solve a 20x20 board, so Warnsdorff is good for me.

otherwise, i've got nothing. sorry. i'll leave you with one interesting thing i just found, a very old article about the Knights Tour from Creative Computing. good luck.


.

Member Avatar for Vytautas

Well, thank you for your time, mate. I guess it can't be optimized further so I'll just have to leave it as it is or maybe someone will have something to add. Thanks for the link by the way.

But still it looks strange when 5x5 is solved in less than a second while 6x6 can't be solved in an hour? Geesh... :)

well, it can be optimized further using advanced numerical methods, but the optimization is geared for larger boards (or neural networks.) Any speed difference wont be noticable for what you're doing on an 8x8 board.

your assignment was probably to discover this fact that the old warnsdorff algorithm blows bruteforce/backtracking out of the water. if so, then it was a success. :)

Are you trying to make ONE knights tour from every square on the board, or are you trying to find EVERY knight's tour that is possible, from every square on the board?

Are you trying to make ONE knights tour from every square on the board, or are you trying to find EVERY knight's tour that is possible, from every square on the board?

that's impossible. impossible for anyone here, at least.

there are over 13,000,000,000,000 undirected closed solutions to the Knights tour on a normal board. And an even ridiculously greater number of open solutions, the number of which is still unsolved and might as well be infinite for our purposes.

he's just trying to solve one solution at a time. bruteforce or backtracking method cant even be counted on to do a single solution on a 6x6 board in a reasonable time.

.

Member Avatar for Vytautas

Yes, one solution from each square is enough. I finally decided to wait for all the solutions for 6x6 board, I guess it took more than 40 minutes and I accidentally closed the console... Doh! :) But I was fast enough to notice that from the square that was bugging me from the beginning it took 35 minutes to find a solution. Others were normal. Anyhow, I think Warnsdorff's algorithm failed with some of those. So this is apparently functionality vs speed duel. Thought I'd update this thread in case anyone finds it useful.

Cheers for the help again.

you're comparing apples and oranges. You're seeing 35 - 60+(?) minutes using the brute force on a 6x6 board, and comparing it against the algorithm on an 8x8 board. your bruteforce likely won't ever complete an 8x8 board for days or weeks.

Whereas, Warnsdorff will, on an 8x8 board, quickly find a solution from any square if you allow it to start over from the occasions when it hits a dead end. Usually Warnsdorff finds it on the first attempt, although it might take 2 or 3, maybe 4, attempts in some cases.

the failures you see with Warnsdorff occurs when it has ties in the algorithm on seemingly-equal paths to choose from. if you have it pick them at random, sometimes you wind up on invalid path that cant be predicted by the algorithm. But all you have to do is re-run the algorithm from the starting square, and the random choice picks different paths at the tie points, most likely leading to a solution on the 2nd attempt. Even if it winds up taking 3 or possibly 4 attempts, Warnsdorff still will always find a solution for each square in less than a second on a typical desktop's CPU.

the real problem with Warnsdorff is that you have no control over whether it's going to find an open solution or a closed solution, and that there's no intelligence behind differentiating between paths of equal value.


.

There is an easy solution to this. Use Ira Pohl's theorem, on top of Warnsdorff's algorithm.

iirc, it means if you find two squares that evaluate as equal in connectivity, then you extend the search depth another ply until the subsequent moves do not evaluate to even anymore.

If you go to Wikipedia, on Warnsdorff's algorithm, it has a link to a free version of Pohl's paper on it.

I haven't played with it in a program, but it lead me to believe that you could solve the problem much faster, because it stops "blind alleys".

Didn't see any figures for using it on different size boards, etc., however.

interesting. i'll have to look for that.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.