Я пытался использовать возврат для обхода Найта, но это занимает слишком много времени. ⇐ JAVA

[Anonymous]

Вот вся структура программы, она написана на Java
Основной класс - статистика программы по вызову Knight

Код: Выделить всё

   public class Main {
public static void main(String\[\] args) {
Knight knight=new Knight( 33,6);
knight.controller(false);
// knight.possiblemoves();

}

}

Затем класс рыцаря управляет движениями рыцаря и инициирует другие методы и классы

Код: Выделить всё

import java.util.ArrayList;

import java.util.Date;
import java.util.LinkedHashSet;
import java.util.Random;
import java.util.Set;

public class Knight {
Board boarde;
static ArrayList\ possiblity;
static ArrayList\ boarder;
public static int MaxCOl;
public static int MaxRow;
static int position;
int h;
guiframe frame;
backtracklogic logic;
int fposition;

Код: Выделить всё

Knight(int fposition, int size) {
MaxCOl = MaxRow = size;
this.fposition = fposition;
logic = new backtracklogic(fposition);
frame = new guiframe(MaxCOl, fposition);
boarde = new Board(MaxCOl, MaxRow);

boarder = new ArrayList();

for (int i = 0; i < MaxCOl; i++) {
for (int j = 0; j < MaxRow; j++) {
boarder.add(Board.board[i][j]);

}
}

possiblity = new ArrayList();
Knight.position = fposition;
// Board.used.add(fposition);
knightmove(fposition);
}

public void knightmove(int tomove) {
position = tomove;
Board.used.add(tomove);
frame.knightposition(tomove);

}

public void controller(Boolean random) {
boolean n = true;
if (random) {
while (n) {
for (int a = 0; a < MaxCOl * MaxCOl; a++) {
try {
Thread.sleep(100);
} catch (InterruptedException e) {

e.printStackTrace();
}
possiblemoves(position, Board.used);
if (possiblity.size() < 1)
break;
knightmove(randommove());
h = a;
if (h >= MaxCOl * MaxCOl) {
n = false;
}

}

}

} else if (!random)

{
ArrayList used = new ArrayList();
used.add(fposition);

long startTime = new Date().getTime();

logic.move(fposition, new ArrayList(used), new ArrayList(), 1);
knightmover(logic.toplay);
long endTime = new Date().getTime();
long executionTime = endTime - startTime;
System.out.println("Execution time: " + executionTime + " milliseconds");
}
}

public void knightmover(ArrayList list) {
for (int i : list)

{
try {
Thread.sleep(100);
} catch (InterruptedException e) {

e.printStackTrace();
}
knightmove(i);
System.out.println(i + " " + list.indexOf(i));
}
System.out.println(list);
}

public static ArrayList possiblemoves(int pos, ArrayList used) {
possiblity.clear();
int x[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int y[] = { 1, 2, 2, 1, -1, -2, -2, -1 };

for (int j = 0, k = 0; j < x.length || k < y.length; j++, k++) {
int a = x[j];
int d = y[k];
if (check(pos + (a * 10) + d) == 1 && !used.contains(pos + (a * 10) + d))
possiblity.add(pos + (a * 10) + d);
}

// remove duplicate fix it in the future if possible
Set p = new LinkedHashSet(possiblity);

possiblity.addAll(p);

return possiblity;

}

public static int check(int a) {
if (boarder.contains(a)) {
return 1;
} else
return 0;
}

public int randommove() {
Random random = new Random();
int a = random.nextInt(possiblity.size());

return possiblity.get(a);
}

}

затем класс логики возврата

Код: Выделить всё

import java.util.ArrayList;

public class backtracklogic {

ArrayList toplay;

backtracklogic(int fposition) {

toplay = new ArrayList();

}

public void move(int position, ArrayList  used, ArrayList movetoplay, int depth) {
if (depth == Knight.MaxCOl * Knight.MaxCOl) {
toplay = movetoplay;
return;
}
// System.out.println(depth);
int move;

ArrayList possible = new ArrayList(Knight.possiblemoves(position, used));

if (possible.size() 

Подробнее здесь: [url]https://stackoverflow.com/questions/78466878/i-tried-to-use-backtracking-for-knights-tour-but-it-is-taking-too-long[/url]