Ну, я начал думать о алгоритме грубой силы, и я ушел, что ниже, но оказывается, что это на самом деле проще для поиска всех ответов, а не генерации всех конфигураций и проверки правильных ответов. Вот код поиска, который в итоге выглядел так же, как @Brent Washburne's. Он работает через 53 миллисекунды на моем ноутбуке.
import java.util.Arrays;
class Puzzle {
final int path[][];
final int grid[] = new int[25];
Puzzle(int[][] path) {
// Make the path endpoints 0-based for Java arrays.
this.path = Arrays.asList(path).stream().map(pair -> {
return new int[] { pair[0] - 1, pair[1] - 1 };
}).toArray(int[][]::new);
}
void print() {
System.out.println();
for (int i = 0; i < grid.length; i += 5)
System.out.println(
Arrays.toString(Arrays.copyOfRange(grid, i, i + 5)));
}
void findPaths(int ip, int i) {
if (grid[i] != -1) return; // backtrack
grid[i] = ip; // mark visited
if(i == path[ip][1]) // path complete
if (ip < path.length - 1) findPaths(ip + 1, path[ip + 1][0]); // find next path
else print(); // solution complete
else { // continue with current path
if (i < 20) findPaths(ip, i + 5);
if (i > 4) findPaths(ip, i - 5);
if (i % 5 < 4) findPaths(ip, i + 1);
if (i % 5 > 0) findPaths(ip, i - 1);
}
grid[i] = -1; // unmark
}
void solve() {
Arrays.fill(grid, -1);
findPaths(0, path[0][0]);
}
public static void main(String[] args) {
new Puzzle(new int[][]{{1, 22}, {4, 17}, {5, 18}, {9, 13}, {20, 23}}).solve();
}
}
Старый, плохой ответ
Эта проблема является выполнимым с помощью грубой силы, если вы думаете о том, что «назад:» назначить все сетки квадратов к дорожкам и тест, чтобы увидеть, если присвоение является действительным. Есть 25 квадратов сетки, и вам нужно построить 5 путей, каждая с двумя конечными точками. Значит, вы знаете пути, на которые эти 10 пунктов лежат. Все, что осталось, - обозначить оставшиеся 15 квадратов путями, на которых они лежат. Для каждого из них есть 5 возможностей, поэтому всего 5^15. Это около 30 миллиардов. Осталось только создать эффективную проверку, которая говорит, является ли заданное задание 5 действительными путями. Это легко сделать с помощью линейного поиска по времени. Приведенный ниже код находит свое решение в течение примерно 2 минут и занимает немного до 11 минут, чтобы проверить исчерпывающе на моем MacBook:
import java.util.Arrays;
public class Hacking {
static class Puzzle {
final int path[][];
final int grid[] = new int[25];
Puzzle(int[][] path) { this.path = path; }
void print() {
System.out.println();
for (int i = 0; i < grid.length; i += 5)
System.out.println(
Arrays.toString(Arrays.copyOfRange(grid, i, i + 5)));
}
boolean trace(int p, int i, int goal) {
if (grid[i] != p) return false;
grid[i] = -1; // mark visited
boolean rtn =
i == goal ? !Arrays.asList(grid).contains(p) : nsew(p, i, goal);
grid[i] = p; // unmark
return rtn;
}
boolean nsew(int p, int i, int goal) {
if (i < 20 && trace(p, i + 5, goal)) return true;
if (i > 4 && trace(p, i - 5, goal)) return true;
if (i % 5 < 4 && trace(p, i + 1, goal)) return true;
if (i % 5 > 0 && trace(p, i - 1, goal)) return true;
return false;
}
void test() {
for (int ip = 0; ip < path.length; ip++)
if (!trace(ip, path[ip][0] - 1, path[ip][1] - 1)) return;
print();
}
void enumerate(int i) {
if (i == grid.length) test();
else if (grid[i] != -1) enumerate(i + 1); // already known
else {
for (int ip = 0; ip < 5; ip++) {
grid[i] = ip;
enumerate(i + 1);
}
grid[i] = -1;
}
}
void solve() {
Arrays.fill(grid, -1);
for (int ip = 0; ip < path.length; ip++)
grid[path[ip][0] - 1] = grid[path[ip][1] - 1] = ip;
enumerate(0);
}
}
public static void main(String[] args) {
new Puzzle(new int[][]{{1, 22}, {4, 17}, {5, 18}, {9, 13}, {20, 23}}).solve();
}
}
начиная массива:
[ 0, -1, -1, 1, 2]
[-1, -1, -1, 3, -1]
[-1, -1, 3, -1, -1]
[-1, 1, 2, -1, 4]
[-1, 0, 4, -1, -1]
Результат:
[ 0, 1, 1, 1, 2]
[ 0, 1, 3, 3, 2]
[ 0, 1, 3, 2, 2]
[ 0, 1, 2, 2, 4]
[ 0, 0, 4, 4, 4]
Посмотрите на алгоритмы шахматных движений для перемещения короля – SteveFerg
Да, я слышал об этом, но это только для того, чтобы держать Короля в безопасности. Это, однако, другое ИМО. – user3907480