I recently pulled a C program (https://repl.it/Klpv) that searches for a knight's tour on an 8 by 8 board. I re-wrote the program in JavaScript (since I understand JS better), then I modified the program so that is can search for a solution on any given board size.
Currently, it uses a recursive algorithm with backtracking to print the first solution it finds. Then it stops. One of the comments from the original C program says that the program will print one of the feasible solutions, but my goal is to print all (or a customizable number of) solutions. I've tried modifying the program's 'return' commands a bit so that I could have it print more than one solution but I can't seem to do that. Can anyone help me out?
// JavaScript Knight's Tour Algorithm
/* A utility function to check if i,j are valid indexes
for width*height chessboard */
var isSafe = function(x, y, sol) {
return (x >= 0 && x < width && y >= 0 && y < height && sol[x][y] == -1);
}
/* A utility function to print solution matrix sol[width][height] */
var printSolution = function(sol) {
var solution = "Knight's Tour for "+width+" by "+height+" board:\n";
for (i = 0; i < width; i++) {
for (j = 0; j < height; j++) {
solution += sol[i][j] + "\t";
}
solution += "\n";
}
console.log(solution)
}
/* This function solves the Knight Tour problem using
Backtracking. This function mainly uses solveKTUtil()
to solve the problem. It returns false if no complete
tour is possible, otherwise return true and prints the
tour.
Please note that there may be more than one solutions,
this function prints one of the feasible solutions. */
var solveKT = function() {
/* Create two-dimentional array */
var sol = new Array(width);
for (i = 0; i < sol.length; i++) {
sol[i] = new Array(height)
}
/* Initialization of solution matrix - set all to -1 */
for (i = 0; i < width; i++) {
for (j = 0; j < height; j++) {
sol[i][j] = -1
}
}
/* xMove[] and yMove[] define next move of Knight.
xMove[] is for next value of x coordinate
yMove[] is for next value of y coordinate */
var xMove = [2, 1, -1, -2, -2, -1, 1, 2];
var yMove = [1, 2, 2, 1, -1, -2, -2, -1];
// Since the Knight is initially at the first block
sol[0][0] = 0;
/* Start from 0,0 and explore all tours using
solveKTUtil() */
if (solveKTUtil(0, 0, 1, sol, xMove, yMove) == 0) {
console.log("Solution does not exist");
return 0;
} else {
printSolution(sol);
}
}
/* A recursive utility function to solve Knight Tour
problem */
var solveKTUtil = function(x, y, movei, sol, xMove, yMove) {
var k, next_x, next_y;
if (movei == width * height) {
return 1;
}
/* Try all next moves from the current coordinate x, y */
for (k = 0; k < 8; k++) {
next_x = x + xMove[k];
next_y = y + yMove[k];
if (isSafe(next_x, next_y, sol)) {
sol[next_x][next_y] = movei;
if (solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove) == 1) {
return 1;
} else {
sol[next_x][next_y] = -1; // backtracking
}
}
}
return 0;
}
var width = 5;
var height = 6;
solveKT();
This will print to the console:
Knight's Tour for 5 by 6 board:
0 27 22 15 6 11
23 16 7 12 21 14
28 1 26 19 10 5
17 24 3 8 13 20
2 29 18 25 4 9
EDIT: I've found a C++ program that does exactly this. https://repl.it/L4Pf No need for help anymore!
There is a lot of solutions to the problem (more than 10^16 according to answer to this question) so you will have to be content with just a few of them.
A trivial way to do this, is to fill an array of of paths until it is large enough for you instead of returning 1.
...
if (solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove) == 1) {
return 1;
}
...
should become something like
...
if (solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove) == 1) {
results.push(deepCopy(sol)) //copy the sol
if(results.length > desired_number_of_paths){
return 1;
}
}
...