Warum hält der folgende Code, der das Springerproblem für 8x8 lösen soll, nicht an?
package org.example;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
public class Springer {
public static class Punkt {
private final int invertable_16_hash;
public Punkt(int x, int y) {
invertable_16_hash = (x << 16) | ((y << 16) >>> 16);
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Punkt punkt = (Punkt) o;
return invertable_16_hash == punkt.invertable_16_hash;
}
@Override
public int hashCode() {
return invertable_16_hash;
}
@Override
public String toString() {
int a = get_x();
int b = get_y();
return "(" + a + "," + b + ")";
}
public int get_x() {
return invertable_16_hash >>> 16;
}
public int get_y() {
return (invertable_16_hash << 16) >>> 16;
}
}
private final int dim;
private final HashMap<Punkt, HashSet<Punkt>> moves_cache = new HashMap<>();
public Springer(final int dim) {
this.dim = dim;
for (int k = 0; k < dim * dim; k++) {
Punkt last = new Punkt(k % dim, k / dim);
HashSet<Punkt> visited = new HashSet<>();
LinkedList<Punkt> path = new LinkedList<>();
visited.add(last);
path.add(last);
boolean r = backtracking_calculate_path(last, visited, path);
System.out.println("visited = " + visited);
System.out.println("path = " + path);
for (Punkt p : path) {
int a = p.get_x();
int b = p.get_y();
for (int i = 0; i < dim; i++) {
for (int j = 0; j < dim; j++) {
if (i == b && j == a) {
System.out.print("_s_ ");
} else {
System.out.print("___ ");
}
}
System.out.println();
}
System.out.println();
}
if (r) {
break;
}
}
}
private boolean backtracking_calculate_path(Punkt last, HashSet<Punkt> visited, LinkedList<Punkt> path) {
// Kreis:
//if (path.size() == dim * dim) {
// return get_moves(last).contains(path.getFirst());
//}
// Kein Kreis:
if (path.size() == dim * dim) {
return true;
}
HashSet<Punkt> moves = get_moves(last);
for (Punkt p : moves) {
if (!visited.contains(p)) {
visited.add(p);
path.add(p);
if (backtracking_calculate_path(p, visited, path)) {
return true;
}
visited.remove(p);
path.removeLast();
}
}
return false;
}
private HashSet<Punkt> get_moves(Punkt p) {
if (!moves_cache.containsKey(p)) {
moves_cache.put(p, calculate_moves(p));
}
return moves_cache.get(p);
}
private HashSet<Punkt> calculate_moves(Punkt p) {
int a = p.get_x();
int b = p.get_y();
HashSet<Punkt> moves = new HashSet<>();
int dx, dy;
dx = a + 2;
dy = b + 1;
if (dx >= 0 && dx < dim && dy >= 0 && dy < dim) {
moves.add(new Punkt(dx, dy));
}
dx = a + 2;
dy = b - 1;
if (dx >= 0 && dx < dim && dy >= 0 && dy < dim) {
moves.add(new Punkt(dx, dy));
}
dx = a - 2;
dy = b + 1;
if (dx >= 0 && dx < dim && dy >= 0 && dy < dim) {
moves.add(new Punkt(dx, dy));
}
dx = a - 2;
dy = b - 1;
if (dx >= 0 && dx < dim && dy >= 0 && dy < dim) {
moves.add(new Punkt(dx, dy));
}
dx = a + 1;
dy = b + 2;
if (dx >= 0 && dx < dim && dy >= 0 && dy < dim) {
moves.add(new Punkt(dx, dy));
}
dx = a + 1;
dy = b - 2;
if (dx >= 0 && dx < dim && dy >= 0 && dy < dim) {
moves.add(new Punkt(dx, dy));
}
dx = a - 1;
dy = b + 2;
if (dx >= 0 && dx < dim && dy >= 0 && dy < dim) {
moves.add(new Punkt(dx, dy));
}
dx = a - 1;
dy = b - 2;
if (dx >= 0 && dx < dim && dy >= 0 && dy < dim) {
moves.add(new Punkt(dx, dy));
}
return moves;
}
public static void main(String[] args) {
new Springer(1); // hält an, keine Lösung
new Springer(2); // hält an, keine Lösung
new Springer(3); // hält an, keine Lösung
new Springer(4); // hält an, keine Lösung
new Springer(5); // hält an
new Springer(6); // hält an
new Springer(7); // hält an
new Springer(8); // <- hält nicht an :(
}
}
Kann obige dim nicht mit backtracking berechnet werden, oder anders, ist das für Computer zu schwierig? Oder habe ich einen ineffizienten Fehltritt gemacht? Oder gibt es einen anderen semantischen Fehler?