java - Knights Tour won't move past 4th move -
i programming solution knights tour problem using heuristic evaluate potential moves, , choose "most difficult" one. run problem makes fourth move , not move forward or backward diffent move. farthest gets is:
1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 3 -1 -1 i working on 5 x 5 board now, before ramping 8 x 8 ultimately. wanted see work on small scale first. know there valid moves, unsure if heuristic comparison going wrong, or if else entirely not seeing.
package csne2; import java.util.scanner; public class knightstour { private final static int board_length = 5; //the length of board private final static int max_moves = board_length * board_length; private static int board[][]; //the simulated board private static int[][] hueristic = new int[][] { {2, 3, 4, 3, 2}, {3, 4, 6, 4, 3}, {4, 6, 8, 6, 4}, {3, 4, 6, 4, 3}, {2, 3, 4, 3, 2} }; //list of possible moves knight private final static int xmove[] = { 2, 1, -1, -2, -2, -1, 1, 2 }; private final static int ymove[] = { 1, 2, 2, 1, -1, -2, -2, -1 }; public static void main(string[] args) { scanner in = new scanner(system.in); system.out.printf("enter starting row (0-7): "); int row = in.nextint(); system.out.printf("enter starting column (0-7): "); int col = in.nextint(); solvetour(row, col); in.close(); } /** * helper method determine if square safe knight * * @param row row knight on * @param col column knight on * @return true if square safe knight */ private static boolean issafe(int row, int col) { return ((row >= 0 && row < board_length) && (col >= 0 && col < board_length) && (board[row][col] == -1)); } /** * helper method print tour solution console */ private static void printtour() { (int r = 0; r < board_length; r++) { (int c = 0; c < board_length; c++) { system.out.print(board[r][c] + " "); } system.out.printf("\n"); } } /** * solves knight's tour using backtracking * * @param srow starting row * @param scol starting column */ public static void solvetour(int srow, int scol) { initializeboard(); board[srow][scol] = 1; if (solvetour(srow, scol, 2)) { printtour(); } else { system.out.printf("no solution!%n"); printtour(); } } private static void initializeboard() { board = new int[board_length][board_length]; //make of board -1 because have not visited square (int r = 0; r < board_length; r++) { (int c = 0; c < board_length; c++) { board[r][c] = -1; } } } /** * helper method solve tour * * @param row current row * @param col current column * @param kthmove current move * @return true if there solution knight's tour */ private static boolean solvetour(int row, int col, int kthmove) { //base case int nextrow = row; int nextcol = col; if(kthmove > max_moves) { return true; } int[] possxmoves = new int[5]; int[] possymoves = new int[5]; int nextmove = 7; for(int = 0; < max_moves; i++) { (int j = 0; j < xmove.length; j++) { if(issafe(row + xmove[j], col + ymove[j])) { possxmoves[j] = row + xmove[j]; possymoves[j] = col + ymove[j]; } else { possxmoves[j] = row; possymoves[j] = col; } } for(int k = 0; k < 8; k++) { if(nextmove > hueristic[possxmoves[j]][possymoves[j]]) { if(issafe(possxmoves[j], possymoves[j])) { nextmove = hueristic[possxmoves[j]][possymoves[j]]; nextrow = possxmoves[j]; nextcol = possymoves[j]; } } } hueristic[nextrow][nextcol] = 7; if(issafe(nextrow, nextcol)) { board[nextrow][nextcol] = kthmove; if (solvetour(nextrow, nextcol, kthmove + 1 )) { return true; } else { board[nextrow][nextcol] = -1; heuristic[nextrow][nextcol] = nextmove; } } } return false; } } edit : final working code
package csne2; import java.util.scanner; public class knightstour { private final static int board_length = 5; //the length of board private final static int max_moves = board_length * board_length; private static int board[][]; //the simulated board private static int[][] hueristic = new int[][] { {2, 3, 4, 3, 2}, {3, 4, 6, 4, 3}, {4, 6, 8, 6, 4}, {3, 4, 6, 4, 3}, {2, 3, 4, 3, 2} }; private static int highestheuristicnumplusone = 9; //list of possible moves knight private final static int xmove[] = { 2, 1, -1, -2, -2, -1, 1, 2 }; private final static int ymove[] = { 1, 2, 2, 1, -1, -2, -2, -1 }; public static void main(string[] args) { scanner in = new scanner(system.in); system.out.printf("enter starting row (0-7): "); int row = in.nextint(); system.out.printf("enter starting column (0-7): "); int col = in.nextint(); solvetour(row, col); in.close(); } /** * helper method determine if square safe knight * * @param row row knight on * @param col column knight on * @return true if square safe knight */ private static boolean issafe(int row, int col) { return ((row >= 0 && row < board_length) && (col >= 0 && col < board_length) && (board[row][col] == -1)); } /** * helper method print tour solution console */ private static void printtour() { (int r = 0; r < board_length; r++) { (int c = 0; c < board_length; c++) { system.out.print(board[r][c] + " "); } system.out.printf("\n"); } } /** * solves knight's tour using backtracking * * @param srow starting row * @param scol starting column */ public static void solvetour(int srow, int scol) { initializeboard(); board[srow][scol] = 1; if (solvetour(srow, scol, 2)) { printtour(); } else { system.out.printf("no solution!%n"); printtour(); } } private static void initializeboard() { board = new int[board_length][board_length]; //make of board -1 because have not visited square (int r = 0; r < board_length; r++) { (int c = 0; c < board_length; c++) { board[r][c] = -1; } } } /** * helper method solve tour * * @param row current row * @param col current column * @param kthmove current move * @return true if there solution knight's tour */ private static boolean solvetour(int row, int col, int kthmove) { //base case int nextrow = row; int nextcol = col; if(kthmove > max_moves) { return true; } int[] possxmoves = new int[xmove.length]; int[] possymoves = new int[ymove.length]; int nextmove = highestheuristicnumplusone; for(int = 0; < max_moves; i++) { (int j = 0; j < xmove.length; j++) { if(issafe(row + xmove[j], col + ymove[j])) { possxmoves[j] = row + xmove[j]; possymoves[j] = col + ymove[j]; } else { possxmoves[j] = row; possymoves[j] = col; } if(nextmove > hueristic[possxmoves[j]][possymoves[j]]) { if(issafe(possxmoves[j], possymoves[j])) { nextmove = hueristic[possxmoves[j]][possymoves[j]]; nextrow = possxmoves[j]; nextcol = possymoves[j]; } } } if(issafe(nextrow, nextcol)) { board[nextrow][nextcol] = kthmove; if (solvetour(nextrow, nextcol, kthmove + 1 )) { return true; } else { board[nextrow][nextcol] = -1; } } } return false; } } all appreciated, try clarify asked of me.
there many problems in solvetour method
- magic numbers. 5? 7? give constants meaningful names. (hint: numbers both wrong)
- why modify heuristic table while doing search?
- give loop variables better names j , k , rethink do. 1 of loops shouldn't there @ all.
Comments
Post a Comment