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