Knight Tour Algorithm ändern, um alle Lösungen zu drucken

Question

Kürzlich habe ich ein C-Programm (https://repl.it/Klpv) gezogen, das auf einer 8 x 8-Karte nach einer Springer-Tour sucht. Ich habe das Programm in JavaScript neu geschrieben (da ich JS besser verstehe), dann habe ich das Programm so modifiziert, dass es nach einer Lösung für jede gegebene Boardgröße suchen kann.

Derzeit verwendet es einen rekursiven Algorithmus mit Backtracking, um die erste gefundene Lösung zu drucken. Dann hört es auf. Einer der Kommentare aus dem ursprünglichen C-Programm sagt, dass das Programm eine der möglichen Lösungen drucken wird, aber mein Ziel ist es, alle (oder eine anpassbare Anzahl von) Lösungen zu drucken. Ich habe versucht, die Return-Befehle des Programms etwas zu ändern, so dass ich mehr als eine Lösung drucken konnte, aber das scheint mir nicht möglich zu sein. Kann mir jemand helfen?

// 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(); 

Dies wird auf die Konsole drucken:

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: Ich habe ein C++ Programm gefunden, das dies tut genau. https://repl.it/L4Pf Keine Hilfe mehr nötig!

Answer 1

Es gibt viele Lösungen für das Problem (mehr als 10^16 nach Antwort auf this question), so dass Sie mit nur ein paar von ihnen zufrieden sein müssen.

Eine triviale Weise, dies zu tun, ist eine Reihe von Pfaden zu füllen, bis es für Sie statt der Rückkehr 1.

... 
if (solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove) == 1) { 
    return 1; 
    } 
... 

groß genug ist, sollten Sie so etwas wie

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

Answer 2

werden könnte auch Ihre Lösung zu ändern:

Dies ist: Wenn eine Lösung gefunden wird, drucken Sie es, und b acktrack vor der Rückkehr, um weiterhin nach Lösungen suchen zu können.