모든 솔루션을 인쇄 할 Knight의 여행 알고리즘을 수정하십시오.

Question

저는 최근에 8 x 8 보드에서 나이트 투어를 검색하는 C 프로그램 (https://repl.it/Klpv)을 가져 왔습니다. 필자는 자바 스크립트로 프로그램을 다시 썼는데 (JS가 더 잘 이해할 것이므로), 프로그램을 수정하여 주어진 보드 크기에서 솔루션을 검색 할 수있게했다.

현재 역 추적과 함께 재귀 알고리즘을 사용하여 발견 한 첫 번째 해결책을 인쇄합니다. 그런 다음 중지합니다. 원래 C 프로그램의 주석 중 하나는 프로그램에서 실현 가능한 해결책 중 하나를 인쇄 하겠지만 내 목표는 모든 (또는 사용자 정의 가능한 수의) 솔루션을 인쇄하는 것입니다. 나는 하나 이상의 솔루션을 인쇄 할 수 있도록 프로그램의 'return'명령을 약간 수정하려고 시도했지만 그렇게 할 수는 없습니다. 누구든지 나를 도울 수 있습니까?

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

이 콘솔로 인쇄됩니다

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 

편집 : 나는 정확히이 일을 수행하는 C++ 프로그램을 발견했습니다. https://repl.it/L4Pf 더 이상 도움이 필요하지 않습니다!

Answer 1

this question에 대한 답변에 따르면 10^16 이상의 문제에 대한 해결책이 많으므로 그 중 일부만으로 만족해야합니다.

이 할 수있는 사소한 방법은, 그것은

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

같은이되어야 1.

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

을 반환하는 대신 당신을 위해 충분히 큰 때까지 경로의 배열을 채우는 것입니다 당신

var solveKTUtil = function(x, y, movei, sol, xMove, yMove) { 
    var k, next_x, next_y; 

    if (movei === width * height) { 
     //Solution found, print it 
     printSolution(sol); 
     //Backtrack 
     sol[x][y] = -1; 
    } 
    .... 

해결책 : 해결책을 찾으면 인쇄하고 b를 입력하십시오. 솔루션 검색을 계속하기 위해 돌아 오기 전에 확인하십시오.