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