Hi Leute,
ich bin neu hier im Forum und hoffe mal, dass ihr mir vielleicht weiterhelfen könnt!
Ich möchte alle Lösungen des Springerproblems mit einem Algorithmus finden.
Orientiert habe ich mich am Backtracking, hier ist erstmal mein Code:
[CODE lang="java" title="Springer"]import java.util.ArrayList;
import java.util.List;
public class Knight {
private Square pos;
public Knight(Square pos) {
this.pos = pos;
}
public List<Square> getPossibleMoves(Chessboard chessboard) {
List<Square> reachableSquares = new ArrayList<Square>();
//Nach oben
int row = pos.getRow();
int column = pos.getColumn();
Square[][] matrix = chessboard.getBoardmatrix();
int size = chessboard.getSize();
//Nach oben
if (row - 2 >= 0) {
//oben links
if (column - 1 > 0) {
reachableSquares.add(matrix[row - 2][column - 1]);
}
//oben rechts
if (column + 1 < size) {
reachableSquares.add(matrix[row - 2][column + 1]);
}
}
//Nach links
if (column - 2 >= 0) {
//links oben
if (row - 1 >= 0) {
reachableSquares.add(matrix[row - 1][column - 2]);
}
//links unten
if (row + 1 < size) {
reachableSquares.add(matrix[row + 1][column - 2]);
}
}
//Nach unten
if (row + 2 < size) {
//unten links
if (column - 1 >= 0) {
reachableSquares.add(matrix[row + 2][column - 1]);
}
//unten rechts
if (column + 1 < size) {
reachableSquares.add(matrix[row + 2][column + 1]);
}
}
//Nach rechts
if (column + 2 < size) {
//rechts oben
if (row - 1 >= 0) {
reachableSquares.add(matrix[row - 1][column + 2]);
}
//rechts unten
if (row + 1 < size) {
reachableSquares.add(matrix[row + 1][column + 2]);
}
}
return reachableSquares;
}
public void move(Square square) {
this.pos = square;
}
public Square getPos() {
return pos;
}
}[/CODE]
[CODE lang="java" title="Schachbrett"]public class Chessboard {
private Square[][] boardmatrix;
private final int size;
public Chessboard(int size) {
this.size = size;
createBoardmatrix();
}
public void createBoardmatrix() {
boardmatrix = new Square[size][size];
for (int row = 0; row < size; row++) {
for (int column = 0; column < size; column++) {
boardmatrix[row][column] = new Square(row, column, size);
}
}
}
public void printMatrix(){
for (int row = 0; row < size; row++) {
System.out.println("\n");
for (int column = 0; column < size; column++) {
System.out.print(boardmatrix[row][column] + "\t");
}
}
}
public Square[][] getBoardmatrix() {
return boardmatrix;
}
public int getSize() {
return size;
}
}
[/CODE]
[CODE lang="java" title="Schachfeld"]public class Square {
private final int row;
private final int outputrow;
private final int column;
public Square(int row, int column, int size) {
this.row = row;
this.column = column;
this.outputrow=size-row;
}
public int getColumn() {
return column;
}
public int getRow() {
return row;
}
@Override
public String toString(){
String alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
StringBuilder output=new StringBuilder();
output.append(alphabet.charAt(column))
.append(outputrow);
return output.toString();
}
}[/CODE]
[CODE lang="java" title="Die (leider nicht funktionierende) Simulator-Klasse"]import java.util.ArrayList;
import java.util.List;
public class Simulator {
Chessboard chessboard;
Knight knight;
ArrayList<Square> solution;
public Simulator(int size, Square pos) {
this.chessboard = new Chessboard(size);
this.knight = new Knight(chessboard, pos);
solution = new ArrayList<>();
for (int i = 0; i < chessboard.getSize() * chessboard.getSize(); i++) {
solution.add(null);
}
System.out.println(solution.size());
int ebene = 0;
simulate(ebene);
}
public void simulate(int depth) {
//Fuer die erste Iteration
if(depth==0){
solution.set(depth,knight.getPos());
}
//falls alle Felder besucht sind
if (depth == chessboard.getSize() * chessboard.getSize() - 1) {
for (Square square : solution) {
System.out.print(square + " ");
}
System.out.println("\n");
} else {
List<Square> moves = knight.getPossibleMoves(chessboard);
//mache jeden moeglichen Zug
for (Square move : moves) {
//wenn Feld noch nicht besucht wurde
if (!solution.contains(move)) {
//naechste Stufe mit den erreichbaren Feldern
solution.set(depth + 1, move);
knight.move(move);
simulate(depth + 1);
//rueckgaengig machen, um alle Lsg. zu finden
for(int i=0;i<solution.size();i++){
if(i>=depth+1){
solution.set(i,null);
}
}
}
}
//falls keine Zuege mgl. sind Feld entfernen
solution.set(depth, null);
//wieder zurueck gehen
knight.move(solution.get(depth-1));
}
}
}
[/CODE]
In der Main-Methode habe ich
Aufgerufen.
Es gibt eine Ausgabe, aber das Programm beendet sich nicht und ruft die Lösungen mehrmals auf, bevor sich etwas verändert.
Vielen Dank schonmal, ich freue mich über jede Idee!
LG ^^
ich bin neu hier im Forum und hoffe mal, dass ihr mir vielleicht weiterhelfen könnt!
Ich möchte alle Lösungen des Springerproblems mit einem Algorithmus finden.
Orientiert habe ich mich am Backtracking, hier ist erstmal mein Code:
[CODE lang="java" title="Springer"]import java.util.ArrayList;
import java.util.List;
public class Knight {
private Square pos;
public Knight(Square pos) {
this.pos = pos;
}
public List<Square> getPossibleMoves(Chessboard chessboard) {
List<Square> reachableSquares = new ArrayList<Square>();
//Nach oben
int row = pos.getRow();
int column = pos.getColumn();
Square[][] matrix = chessboard.getBoardmatrix();
int size = chessboard.getSize();
//Nach oben
if (row - 2 >= 0) {
//oben links
if (column - 1 > 0) {
reachableSquares.add(matrix[row - 2][column - 1]);
}
//oben rechts
if (column + 1 < size) {
reachableSquares.add(matrix[row - 2][column + 1]);
}
}
//Nach links
if (column - 2 >= 0) {
//links oben
if (row - 1 >= 0) {
reachableSquares.add(matrix[row - 1][column - 2]);
}
//links unten
if (row + 1 < size) {
reachableSquares.add(matrix[row + 1][column - 2]);
}
}
//Nach unten
if (row + 2 < size) {
//unten links
if (column - 1 >= 0) {
reachableSquares.add(matrix[row + 2][column - 1]);
}
//unten rechts
if (column + 1 < size) {
reachableSquares.add(matrix[row + 2][column + 1]);
}
}
//Nach rechts
if (column + 2 < size) {
//rechts oben
if (row - 1 >= 0) {
reachableSquares.add(matrix[row - 1][column + 2]);
}
//rechts unten
if (row + 1 < size) {
reachableSquares.add(matrix[row + 1][column + 2]);
}
}
return reachableSquares;
}
public void move(Square square) {
this.pos = square;
}
public Square getPos() {
return pos;
}
}[/CODE]
[CODE lang="java" title="Schachbrett"]public class Chessboard {
private Square[][] boardmatrix;
private final int size;
public Chessboard(int size) {
this.size = size;
createBoardmatrix();
}
public void createBoardmatrix() {
boardmatrix = new Square[size][size];
for (int row = 0; row < size; row++) {
for (int column = 0; column < size; column++) {
boardmatrix[row][column] = new Square(row, column, size);
}
}
}
public void printMatrix(){
for (int row = 0; row < size; row++) {
System.out.println("\n");
for (int column = 0; column < size; column++) {
System.out.print(boardmatrix[row][column] + "\t");
}
}
}
public Square[][] getBoardmatrix() {
return boardmatrix;
}
public int getSize() {
return size;
}
}
[/CODE]
[CODE lang="java" title="Schachfeld"]public class Square {
private final int row;
private final int outputrow;
private final int column;
public Square(int row, int column, int size) {
this.row = row;
this.column = column;
this.outputrow=size-row;
}
public int getColumn() {
return column;
}
public int getRow() {
return row;
}
@Override
public String toString(){
String alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
StringBuilder output=new StringBuilder();
output.append(alphabet.charAt(column))
.append(outputrow);
return output.toString();
}
}[/CODE]
[CODE lang="java" title="Die (leider nicht funktionierende) Simulator-Klasse"]import java.util.ArrayList;
import java.util.List;
public class Simulator {
Chessboard chessboard;
Knight knight;
ArrayList<Square> solution;
public Simulator(int size, Square pos) {
this.chessboard = new Chessboard(size);
this.knight = new Knight(chessboard, pos);
solution = new ArrayList<>();
for (int i = 0; i < chessboard.getSize() * chessboard.getSize(); i++) {
solution.add(null);
}
System.out.println(solution.size());
int ebene = 0;
simulate(ebene);
}
public void simulate(int depth) {
//Fuer die erste Iteration
if(depth==0){
solution.set(depth,knight.getPos());
}
//falls alle Felder besucht sind
if (depth == chessboard.getSize() * chessboard.getSize() - 1) {
for (Square square : solution) {
System.out.print(square + " ");
}
System.out.println("\n");
} else {
List<Square> moves = knight.getPossibleMoves(chessboard);
//mache jeden moeglichen Zug
for (Square move : moves) {
//wenn Feld noch nicht besucht wurde
if (!solution.contains(move)) {
//naechste Stufe mit den erreichbaren Feldern
solution.set(depth + 1, move);
knight.move(move);
simulate(depth + 1);
//rueckgaengig machen, um alle Lsg. zu finden
for(int i=0;i<solution.size();i++){
if(i>=depth+1){
solution.set(i,null);
}
}
}
}
//falls keine Zuege mgl. sind Feld entfernen
solution.set(depth, null);
//wieder zurueck gehen
knight.move(solution.get(depth-1));
}
}
}
[/CODE]
In der Main-Methode habe ich
Java:
Simulator simulator=new Simulator(6,square1);
Es gibt eine Ausgabe, aber das Programm beendet sich nicht und ruft die Lösungen mehrmals auf, bevor sich etwas verändert.
Vielen Dank schonmal, ich freue mich über jede Idee!
LG ^^