Can someone modify this code to work to complete a drunk knight tour.. The tour
ID: 3773226 • Letter: C
Question
Can someone modify this code to work to complete a drunk knight tour.. The tour shouldn't always go to every tile, and should print out the best tour thus far. If theres a way to make it work without the possibles class that would be great!! Below is a photo of the assignment. I think the problem is with line 80ish or so, using the possibles class might be the problem
Here is the code thus far, it fails every time and only goes to one space:
import java.util.*;
class possibles
{
public possibles()
{
}
int[][] board;
int a;
int b;
private final static int[][] moves = {{1,-2},{2,-1},{2,1},{1,2},{-1,2},
{-2,1},{-2,-1},{-1,-2}};
public possibles(int[][] board, int x, int y)
{
a = x;
b = y;
board = board;
}
public ArrayList checkPossibles()
{
ArrayList nbrs = new ArrayList();
for (int[] m : moves)
{
int x = m[0];
int y = m[1];
if (board[a + y][b + x] == 0)
{
int num = countNeighbors(a + y, b + x);
nbrs.add(new int[]{a + y, b + x, num});
}
}
return nbrs;
}
private int countNeighbors(int r, int c)
{
int num = 0;
for (int[] m : moves)
if (board[r + m[1]][c + m[0]] == 0)
num++;
return num;
}
}
public class DrunkKnightTour
{
public static Random r1 = new Random();
static ArrayList AList = new ArrayList();
public static int[][] ktour = new int[8][8];
public static int count = 0;
public static int klongest = 0;
public static int counter = 0;
public static void main(String[] args)
{
int[][] kboard = new int[8][8];
for(int a = 0; a<8; a++)
{
for(int b = 0; b<8; b++)
{
kboard[a][b] = 1;
ktour[a][b] = 0;
}
}
while(!kcomplete(ktour))
{
counter++;
for(int a = 0; a<8; a++)
{
for(int b = 0; b<8; b++)
{
kboard[a][b] = 1;
ktour[a][b] = 0;
}
}
count = 0;
kTest(kboard,r1.nextInt(8),r1.nextInt(8));
if(counter <= 5 || kcomplete(ktour) || (count > klongest && counter >5) || counter%1000 == 0)
{
System.out.println(counter+" tour, tour legnth: " + count);
System.out.println("");
display(ktour);
if(count > klongest)
{
klongest = count;
}
}
if(counter == 1000000)
{
System.out.println("After 1000000 tours, longest tour" + klongest + "moves long & we've yet to have a complete-tour");
break;
}
}
}
public static boolean kcomplete(int[][] kboard)
{
for(int a = 0; a<8; a++)
{
for(int b = 0; b<8; b++)
{
if(kboard[a][b] == 0)
return false;
}
}
return true;
}
public static void display(int[][] kboard)
{
for(int a = 0; a<8; a++)
{
for(int b = 0; b<8; b++)
{
System.out.print(" " + kboard[a][b] + " ");
}
System.out.println(" ");
}
}
public static void kTest(int[][] kboard,int a, int b)
{
int krandom = 0;
int size = 0;
kboard[a][b] = 0;
ktour[a][b] = ++count;
possibles p = new possibles(kboard, a, b);
//AList = p.checkPossibles();
size = AList.size();
if(!AList.isEmpty())
{
if(size == 1)
{
krandom = 0;
}
else
{
krandom = r1.nextInt(size);
}
if(AList.get(krandom) == 1)
{
kTest(kboard,a-2,b+1);
}
if(AList.get(krandom) == 2)
{
kTest(kboard,a-1,b+2);
}
if(AList.get(krandom) == 3)
{
kTest(kboard,a+1,b+2);
}
if(AList.get(krandom) == 4)
{
kTest(kboard,a+2,b+1);
}
if(AList.get(krandom) == 5)
{
kTest(kboard,a+2,b-1);
}
if(AList.get(krandom) == 6)
{
kTest(kboard,a+1,b-2);
}
if(AList.get(krandom) == 7)
{
kTest(kboard,a-1,b-2);
}
if(AList.get(krandom) == 8)
{
kTest(kboard,a-2,b-1);
}
}
}
}
Explanation / Answer
import java.util.*;
public class KnightsTour
{
private final static int base = 12;
private final static int[][] moves = {{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2}};
private static int[][] grid;
private static int total;
public static void main(String[] args)
{
grid = new int[base][base];
total = (base - 4) * (base - 4);
for (int r = 0; r < base; r++)
for (int c = 0; c < base; c++)
if (r < 2 || r > base - 3 || c < 2 || c > base - 3)
grid[r][c] = -1;
int row = 2 + (int) (Math.random() * (base - 4));
int col = 2 + (int) (Math.random() * (base - 4));
grid[row][col] = 1;
if (solve(row, col, 2))
printResult();
else
System.out.println("no result");
}
private static boolean solve(int r, int c, int count)
{
if (count > total)
return true;
List<int[]> nbrs = neighbors(r, c);
if (nbrs.isEmpty() && count != total)
return false;
Collections.sort(nbrs, new Comparator<int[]>()
{ public int compare(int[] a, int[] b)
{ return a[2] - b[2];}
});
for (int[] nb : nbrs)
{
r = nb[0];
c = nb[1];
grid[r][c] = count;
if (!orphanDetected(count, r, c) && solve(r, c, count + 1))
return true;
grid[r][c] = 0;
}
return false;
}
private static List<int[]> neighbors(int r, int c)
{
List<int[]> nbrs = new ArrayList<>();
for (int[] m : moves)
{
int x = m[0];
int y = m[1];
if (grid[r + y][c + x] == 0)
{
int num = countNeighbors(r + y, c + x);
nbrs.add(new int[]{r + y, c + x, num});
}
}
return nbrs;
}
private static int countNeighbors(int r, int c)
{
int num = 0;
for (int[] m : moves)
if (grid[r + m[1]][c + m[0]] == 0)
num++;
return num;
}
private static boolean orphanDetected(int cnt, int r, int c)
{
if (cnt < total - 1)
{
List<int[]> nbrs = neighbors(r, c);
for (int[] nb : nbrs)
if (countNeighbors(nb[0], nb[1]) == 0)
return true;
}
return false;
}
private static void printResult()
{
for (int[] row : grid)
{
for (int i : row)
{
if (i == -1) continue;
System.out.printf("%2d ", i);
}
System.out.println();
}
}
}