4 Knights

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 {

    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 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();
    }

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