Java :: Aufgabe #180

4 Lösungen Lösungen öffentlich

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.

Lösungen:

vote_ok
von meisen (320 Punkte) - 12.11.2017 um 00:47 Uhr
Quellcode ausblenden Java-Code
import java.util.*;

class FourKnights {
    private final static ChessGame chessGame = new ChessGame();

    public static void main(String args[]) {
        play(0);
    }

    private static void play(int jump) {
        chessGame.setJump(jump);
        chessGame.tryJump();
        if (!chessGame.isValidPosition())
            return;
        chessGame.setPosition();
        if (!chessGame.isNewPosition())
            return;
        chessGame.addPosition();
        System.out.println(chessGame + " - JUMP:  " + jump + "  Best size: "
                + chessGame.bestMoveList.size() + " PosList: " + chessGame.positionList.size());

        for (int i = 0; i < 16; i++) {
            play(i);
            chessGame.moveBack();
        }
        chessGame.removePosition();
    }
}

class ChessGame {
    final List<Integer> bestMoveList = new ArrayList<>();
    final Stack<Integer> moveList = new Stack<>();
    final Stack<String> positionList = new Stack<>();
    private final int[][] moves = {{1, 2}, {2, 1}, {-1, -2}, {-2, -1}, {-1, 2}, {-2, 1}, {1, -2}, {2, -1}};
    private final Player[] player = new Player[2];
    String position;
    private int playerId, knightId;
    // JumpNumber from 0 - 15
    private int jump, jumpNumber;
    private Player waitingPlayer;
    private Knight movingKnight, waitingKnight;

    ChessGame() {
        for (int i = 0; i < 2; i++)
            player[i] = new Player();
        player[0].knight[0] = new Knight(0, 1);
        player[0].knight[1] = new Knight(0, 6);
        player[1].knight[0] = new Knight(7, 1);
        player[1].knight[1] = new Knight(7, 6);
        setPosition();
        positionList.push(position);
        playerId = 0;
    }

    void addPosition() {
        positionList.push(position);
        moveList.push(jump);
        if (bestMoveList.size() <= moveList.size()) {
            bestMoveList.clear();
            bestMoveList.addAll(moveList);
        }
    }

    boolean isNewPosition() {
        return !positionList.contains(position);
    }

    void setJump(int jumpNumber) {
        this.jumpNumber = jumpNumber;
    }

    final void tryJump() {
        Player movingPlayer;
        playerId = moveList.size() % 2 == 0 ? 0 : 1;
        movingPlayer = player[playerId];
        waitingPlayer = player[1 - playerId];
        if (jumpNumber > 7) {
            knightId = 1;
            this.jump = jumpNumber - 8;
        } else {
            knightId = 0;
            this.jump = jumpNumber;
        }
        movingKnight = movingPlayer.knight[knightId];
        waitingKnight = movingPlayer.knight[1 - knightId];
        movingKnight.move(moves[this.jump]);
    }

    void setPosition() {
        position = player[0].getDecimal() + player[1].getDecimal();
    }

    final void moveBack() {
        movingKnight.moveBack(moves[this.jump]);
    }

    final void removePosition() {
        positionList.pop();
        moveList.pop();
    }

    final boolean isValidPosition() {
        if (isOutside()
                || movingKnight.equals(waitingKnight)
                || movingKnight.equals(waitingPlayer.knight[0])
                || movingKnight.equals(waitingPlayer.knight[1]))
            return false;
        return true;
    }

    boolean isOutside() {
        return movingKnight.getX() > 7 || movingKnight.getX() < 0
                || movingKnight.getY() > 7 || movingKnight.getY() < 0;
    }

    @Override
    public String toString() {
        return (playerId == 0 ? "white: " : "black: ")
                + (knightId == 0 ? "left: " : "right: ")
                + movingKnight.toString();
    }
}

/**
 * White or Black
 */
class Player {
    final Knight[] knight = new Knight[2];
    private final Set<Integer> positionPlayer = new TreeSet<>();

    final String getDecimal() {
        StringBuilder playerPositionStr = new StringBuilder();
        for (Knight knight : knight) {
            positionPlayer.add(knight.getDecimal());
        }
        for (int pos : positionPlayer) {
            playerPositionStr.append(String.valueOf(pos));
        }
        positionPlayer.clear();
        return playerPositionStr.toString();
    }

    @Override
    public String toString() {
        return " Right: " + knight[0] + " Left: " + knight[1];
    }
}

class Knight {
    private int x, y;

    Knight(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @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;
    }

    void move(int[] jump) {
        this.x += jump[0];
        this.y += jump[1];
    }

    void moveBack(int[] jump) {
        this.x -= jump[0];
        this.y -= jump[1];
    }

    int getDecimal() {
        return Integer.valueOf("" + x + y);
    }

    int getX() {
        return x;
    }

    void setX(int x) {
        this.x = x;
    }

    int getY() {
        return y;
    }

    void setY(int y) {
        this.y = y;
    }

    @Override
    public String toString() {
        return ((char) (x + 65)) + " - " + (y + 1);
    }
}
vote_ok
von meisen (320 Punkte) - 12.11.2017 um 01:06 Uhr
Quellcode ausblenden Java-Code
import java.util.*;

class FourKnights {
    private final static ChessGame chessGame = new ChessGame();

    public static void main(String args[]) {
        play(0);
    }

    private static void play(int jump) {
        chessGame.setJump(jump);
        chessGame.tryJump();
        if (!chessGame.isValidPosition())
            return;
        chessGame.setPosition();
        if (!chessGame.isNewPosition())
            return;
        chessGame.addPosition();
        System.out.println(chessGame + " - JUMP:  " + jump + "  Best size: "
                + chessGame.bestMoveList.size() + " PosList: " + chessGame.positionList.size());

        for (int i = 0; i < 16; i++) {
            play(i);
            chessGame.moveBack();
        }
        chessGame.removePosition();
    }
}

class ChessGame {
    final List<Integer> bestMoveList = new ArrayList<>();
    final Stack<Integer> moveList = new Stack<>();
    final Stack<String> positionList = new Stack<>();
    private final int[][] moves = {{1, 2}, {2, 1}, {-1, -2}, {-2, -1}, {-1, 2}, {-2, 1}, {1, -2}, {2, -1}};
    private final Player[] player = new Player[2];
    String position;
    private int playerId, knightId;
    // JumpNumber from 0 - 15
    private int jump, jumpNumber;
    private Player waitingPlayer;
    private Knight movingKnight, waitingKnight;

    ChessGame() {
        for (int i = 0; i < 2; i++)
            player[i] = new Player();
        player[0].knight[0] = new Knight(0, 1);
        player[0].knight[1] = new Knight(0, 6);
        player[1].knight[0] = new Knight(7, 1);
        player[1].knight[1] = new Knight(7, 6);
        setPosition();
        positionList.push(position);
        playerId = 0;
    }

    void addPosition() {
        positionList.push(position);
        moveList.push(jump);
        if (bestMoveList.size() <= moveList.size()) {
            bestMoveList.clear();
            bestMoveList.addAll(moveList);
        }
    }

    boolean isNewPosition() {
        return !positionList.contains(position);
    }

    void setJump(int jumpNumber) {
        this.jumpNumber = jumpNumber;
    }

    final void tryJump() {
        Player movingPlayer;
        playerId = moveList.size() % 2 == 0 ? 0 : 1;
        movingPlayer = player[playerId];
        waitingPlayer = player[1 - playerId];
        if (jumpNumber > 7) {
            knightId = 1;
            this.jump = jumpNumber - 8;
        } else {
            knightId = 0;
            this.jump = jumpNumber;
        }
        movingKnight = movingPlayer.knight[knightId];
        waitingKnight = movingPlayer.knight[1 - knightId];
        movingKnight.move(moves[this.jump]);
    }

    void setPosition() {
        position = player[0].getDecimal() + player[1].getDecimal();
    }

    final void moveBack() {
        movingKnight.moveBack(moves[this.jump]);
    }

    final void removePosition() {
        positionList.pop();
        moveList.pop();
    }

    final boolean isValidPosition() {
        if (isOutside()
                || movingKnight.equals(waitingKnight)
                || movingKnight.equals(waitingPlayer.knight[0])
                || movingKnight.equals(waitingPlayer.knight[1]))
            return false;
        return true;
    }

    boolean isOutside() {
        return movingKnight.getX() > 7 || movingKnight.getX() < 0
                || movingKnight.getY() > 7 || movingKnight.getY() < 0;
    }

    @Override
    public String toString() {
        return (playerId == 0 ? "white: " : "black: ")
                + (knightId == 0 ? "left: " : "right: ")
                + movingKnight.toString();
    }
}

/**
 * White or Black
 */
class Player {
    final Knight[] knight = new Knight[2];
    private final Set<Integer> positionPlayer = new TreeSet<>();

    final String getDecimal() {
        StringBuilder playerPositionStr = new StringBuilder();
        for (Knight knight : knight) {
            positionPlayer.add(knight.getDecimal());
        }
        for (int pos : positionPlayer) {
            playerPositionStr.append(String.valueOf(pos));
        }
        positionPlayer.clear();
        return playerPositionStr.toString();
    }

    @Override
    public String toString() {
        return " Right: " + knight[0] + " Left: " + knight[1];
    }
}

class Knight {
    private int x, y;

    Knight(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @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;
    }

    void move(int[] jump) {
        this.x += jump[0];
        this.y += jump[1];
    }

    void moveBack(int[] jump) {
        this.x -= jump[0];
        this.y -= jump[1];
    }

    int getDecimal() {
        return Integer.valueOf("" + x + y);
    }

    int getX() {
        return x;
    }

    void setX(int x) {
        this.x = x;
    }

    int getY() {
        return y;
    }

    void setY(int y) {
        this.y = y;
    }

    @Override
    public String toString() {
        return ((char) (x + 65)) + " - " + (y + 1);
    }
}
1 Kommentar
1x
vote_ok
von meisen (320 Punkte) - 12.11.2017 um 09:58 Uhr
Quellcode ausblenden Java-Code
import java.util.*;
import static java.lang.System.*;

class FourKnights {
    private final static ChessGame chessGame = new ChessGame();

    public static void main(String args[]) {
        chessGame.play(0);
        out.println(chessGame.bestMoveList.size());
    }


}

class ChessGame {
    final List<String> bestMoveList = new ArrayList<>();
    private final Stack<String> positionList = new Stack<>();
    private final int[][] moves = {{1, 2}, {2, 1}, {-1, -2}, {-2, -1}, {-1, 2}, {-2, 1}, {1, -2}, {2, -1}};
    private final Player[] player = new Player[2];
    private String positionId;
    private int playerId, knightId;
    // JumpNumber from 0 - 15
    private int jump, jumpNumber;
    private Player waitingPlayer;
    private Knight movingKnight, waitingKnight;

    ChessGame() {
        for (int i = 0; i < 2; i++)
            player[i] = new Player();
        player[0].knight[0] = new Knight(0, 1);
        player[0].knight[1] = new Knight(0, 6);
        player[1].knight[0] = new Knight(7, 1);
        player[1].knight[1] = new Knight(7, 6);
        setPositionId();
        positionList.push(positionId);
        playerId = 0;
    }

    void play(int jump) {
        setJump(jump);
        tryJump();
        if (!isValidPosition())
            return;
        setPositionId();
        if (!isNewPosition())
            return;
        addPositionId();
        out.println(bestMoveList.size() + ":\t" + this + "\tJumpNumber:\t" + jump + "\tPosList:\t" + positionList.size());
        for (int i = 0; i < 16; i++) {
            play(i);
            jumpBack();
        }
        removePositionId();
    }

    private void addPositionId() {
        positionList.push(positionId);
        if (bestMoveList.size() <= positionList.size()) {
            bestMoveList.clear();
            bestMoveList.addAll(positionList);
        }
    }

    private boolean isNewPosition() {
        return !positionList.contains(positionId);
    }

    private void setJump(int jumpNumber) {
        this.jumpNumber = jumpNumber;
    }

    private void tryJump() {
        Player movingPlayer;
        playerId = positionList.size() % 2 == 0 ? 1 : 0;
        movingPlayer = player[playerId];
        waitingPlayer = player[1 - playerId];
        if (jumpNumber > 7) {
            knightId = 1;
            this.jump = jumpNumber - 8;
        } else {
            knightId = 0;
            this.jump = jumpNumber;
        }
        movingKnight = movingPlayer.knight[knightId];
        waitingKnight = movingPlayer.knight[1 - knightId];
        movingKnight.move(moves[this.jump]);
    }

    private void setPositionId() {
        positionId = player[0].getDecimal() + player[1].getDecimal();
    }

    private void jumpBack() {
        movingKnight.moveBack(moves[this.jump]);
    }

    private void removePositionId() {
        positionList.pop();
    }

    private boolean isValidPosition() {
        return !isOutside()
                && !movingKnight.equals(waitingKnight)
                && !movingKnight.equals(waitingPlayer.knight[0])
                && !movingKnight.equals(waitingPlayer.knight[1]);
    }

    private boolean isOutside() {
        return movingKnight.getX() > 7 || movingKnight.getX() < 0
                || movingKnight.getY() > 7 || movingKnight.getY() < 0;
    }

    @Override
    public String toString() {
        return (playerId == 0 ? "white" : "black") + "-"
                + (knightId == 0 ? "left" : "right") + ":\t"
                + movingKnight.toString();
    }
}

/**
 * White or Black
 */
class Player {
    final Knight[] knight = new Knight[2];
    private final Set<Integer> positionPlayer = new TreeSet<>();

    final String getDecimal() {
        StringBuilder playerPositionStr = new StringBuilder();
        for (Knight knight : knight) {
            positionPlayer.add(knight.getDecimal());
        }
        for (int pos : positionPlayer) {
            playerPositionStr.append(String.valueOf(pos));
        }
        positionPlayer.clear();
        return playerPositionStr.toString();
    }

    @Override
    public String toString() {
        return " Right: " + knight[0] + " Left: " + knight[1];
    }
}

class Knight {
    private int x, y;

    Knight(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @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;
    }

    void move(int[] jump) {
        this.x += jump[0];
        this.y += jump[1];
    }

    void moveBack(int[] jump) {
        this.x -= jump[0];
        this.y -= jump[1];
    }

    final int getDecimal() {
        return Integer.valueOf("" + x + y);
    }

    final int getX() {
        return x;
    }

    final void setX(int x) {
        this.x = x;
    }

    final int getY() {
        return y;
    }

    void setY(int y) {
        this.y = y;
    }

    @Override
    public String toString() {
        return ((char) (x + 65)) + "-" + (y + 1);
    }
}
vote_ok
von meisen (320 Punkte) - 18.11.2017 um 17:33 Uhr
Quellcode ausblenden 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);
    }
}