Java :: Aufgabe #180 :: Lösung #4
4 Lösungen
#180
Maximale Zügezahl beim Springerschachspiel
Fortgeschrittener - Java
von hollst
- 02.09.2017 um 16:50 Uhr
Wir betrachten ein vom Schachspiel abgeleitetes Spiel, bei dem
lediglich die vier Springer mitwirken (Abb. 1). Das Spiel hat
weder Gewinner noch Verlierer (wird manchmal als Lernübung für das
Schachspiel verwendet, insbesondere, um die eigenartige Gangart
des Springers zu verinnerlichen). Die vier Springer stehen in ihrer
normalen Ausgangsstellung und können in der beim Schach üblichen
Art ziehen und schlagen. Weitere Figuren sind auf dem Schachbrett
nicht vorhanden. Weiß und Schwarz ziehen abwechselnd, Weiß beginnt.
Eine Partie ist beended, wenn eine der zwei folgenden Bedingungen
erfüllt ist:
1. Einer der zwei Spieler hat lediglich nur noch einen Springer
- in diesem Fall könnte man auch vereinbaren, dass der Spieler
mit den zwei Springern als Sieger gewertet wird.
2. Es ist mit dem letzten Zug eine Stellug entstanden, die im
Verlaufe des Spieles breits einmal zuvor auf dem Brett war.
Die Programmieraufgabe besteht darin, die hinsichtlich der
Zügezahl längst mögliche Zugfolge(n) zu ermitteln.
lediglich die vier Springer mitwirken (Abb. 1). Das Spiel hat
weder Gewinner noch Verlierer (wird manchmal als Lernübung für das
Schachspiel verwendet, insbesondere, um die eigenartige Gangart
des Springers zu verinnerlichen). Die vier Springer stehen in ihrer
normalen Ausgangsstellung und können in der beim Schach üblichen
Art ziehen und schlagen. Weitere Figuren sind auf dem Schachbrett
nicht vorhanden. Weiß und Schwarz ziehen abwechselnd, Weiß beginnt.
Eine Partie ist beended, wenn eine der zwei folgenden Bedingungen
erfüllt ist:
1. Einer der zwei Spieler hat lediglich nur noch einen Springer
- in diesem Fall könnte man auch vereinbaren, dass der Spieler
mit den zwei Springern als Sieger gewertet wird.
2. Es ist mit dem letzten Zug eine Stellug entstanden, die im
Verlaufe des Spieles breits einmal zuvor auf dem Brett war.
Die Programmieraufgabe besteht darin, die hinsichtlich der
Zügezahl längst mögliche Zugfolge(n) zu ermitteln.
#4
von meisen (330 Punkte)
- 18.11.2017 um 17:33 Uhr
Java-Code
import java.text.NumberFormat; import java.util.*; import static java.lang.System.out; /** Let each chess-player two knights jump along, without beating each other, and without ever repeating any position, until one player stucks. The task is to evaluate the longest move period possible. positionList grows, as long each position have up to 16 jumps left. It shrinks, as soon the positions expire their possible jumps and stuck. */ public class Jumping { private static final Stack<Position> positionList = new Stack<>(); private static Position position; private static long counter = 0; private static final int BOARD = 7; public static void main(String args[]) { final Player p1 = new Player(new Knight[]{new Knight(0, 1), new Knight(0, 6)}); final Player p2 = new Player(new Knight[]{new Knight(BOARD, 1), new Knight(BOARD, 6)}); position = new Position(new Player[]{p1, p2}, false); position.generatePositionId(); out.println(run()); } private static List<Position> run() { final List<Position> bestMoveList = new ArrayList<>(); boolean white, hasNext = true, firstLoop = true; int min = 0; while (positionList.size() > 2 || firstLoop) { while (hasNext) { counter++; positionList.push(position); white = positionList.size() % 2 != 0; position = new Position(position.getPlayers(), white); hasNext = nextJump(); } if (positionList.size() > bestMoveList.size()) { bestMoveList.clear(); bestMoveList.addAll(positionList); min = positionList.size(); out.print("\t **** total valid jumps: " + NumberFormat.getInstance().format(counter) + "\n Max ... Min: " + NumberFormat.getInstance().format(min)); } while (!hasNext) { position = positionList.pop(); hasNext = nextJump(); } if (min > positionList.size()) { min = positionList.size(); out.print("\t" + NumberFormat.getInstance().format(min)); } firstLoop = false; } return bestMoveList; } private static boolean nextJump() { while (position.nextJump()) { position.generatePositionId(); if (!positionList.contains(position)) return true; jumpBack(); } return false; } private static void jumpBack() { position.jumpBack(); } } class Position { @Override public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof Position)) return false; Position position = (Position) o; return getPositionId() == position.getPositionId(); } @Override public int hashCode() { return getPositionId(); } private Player[] players = new Player[2]; private Player waitingPlayer, movingPlayer; private boolean white; private int positionId; Position(Player[] players, boolean white) { for (int i = 0; i < 2; i++) this.players[i] = new Player(players[i].knights); movingPlayer = this.players[white ? 0 : 1]; waitingPlayer = this.players[white ? 1 : 0]; this.white = white; } Player[] getPlayers() { return players; } private int getPositionId() { return positionId; } boolean nextJump() { while (movingPlayer.nextJump()) { if (isValidPosition()) return true; jumpBack(); } return false; } void jumpBack() { movingPlayer.jumpBack(); } void generatePositionId() { positionId = Integer.valueOf((players[0].generatePositionId() + players[1].generatePositionId()).replaceAll("(\\W|\\s)", "")); } private boolean isValidPosition() { for (Knight knight : waitingPlayer.knights) if (movingPlayer.getMovingKnight().equals(knight)) return false; return true; } @Override public String toString() { return (white ? "white" : "black") + movingPlayer.toString(); } } /** * White or Black */ class Player { final Knight[] knights = new Knight[2]; private Knight movingKnight; Player(Knight[] knights) { for (int i = 0; i < 2; i++) this.knights[i] = new Knight(knights[i].getX(), knights[i].getY()); } Knight getMovingKnight() { return movingKnight; } final String generatePositionId() { final Set<String> positionPlayer = new TreeSet<>(); for (Knight knight : knights) positionPlayer.add(knight.toString()); return positionPlayer.toString(); } boolean nextJump() { for (int i = 0; i < 2; i++) { movingKnight = knights[i]; while (knights[i].nextJump()) { if (!movingKnight.equals(knights[1 - i])) return true; jumpBack(); } } return false; } void jumpBack() { movingKnight.jumpBack(); } @Override public String toString() { return " Right: " + knights[0] + " Left: " + knights[1]; } } class Knight { private int x, y; private int nextJump = -1; private final int[][] moves = {{1, 2}, {2, 1}, {-1, -2}, {-2, -1}, {-1, 2}, {-2, 1}, {1, -2}, {2, -1}}; Knight(int x, int y) { this.x = x; this.y = y; } final int getX() { return x; } final int getY() { return y; } private void jump() { this.x += moves[nextJump][0]; this.y += moves[nextJump][1]; } void jumpBack() { this.x -= moves[nextJump][0]; this.y -= moves[nextJump][1]; } boolean nextJump() { if (nextJump > 6) return false; nextJump++; jump(); if (isOutside()) { jumpBack(); return nextJump(); } return true; } private boolean isOutside() { return x > 7 || x < 0 || y > 7 || y < 0; } @Override public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof Knight)) return false; Knight knight = (Knight) o; return getX() == knight.getX() && getY() == knight.getY(); } @Override public int hashCode() { int result = getX(); result = 31 * result + getY(); return result; } @Override public String toString() { return "" + (x+1) + (y+1); //return ((char) (y + (int) 'A')) + "-" + (x + 1); } }
Kommentare:
Für diese Lösung gibt es noch keinen Kommentar
Seite 1 von 0
1