I created this as part of an interview process of graduate programming job. Submitted the code to them, and I was called for an interview. This is the assignment brief: http://knight-path.sourceforge.net/puzzle.html, however I was told I can accept the input and produce the output in whatever form I think is most effective, and I have to display an OOP understanding as well.I am a beginner in Java and haven't code in it for a while (2 years since my last Java programming subject in uni), thus was curious on areas of improvements. I would like to be evaluated on my OOP, design pattern, and overall code quality.import java.util.Scanner;import java.util.LinkedList;public class Board {    private final int BOARD_WIDTH = 8;    private final int BOARD_HEIGHT = 8;    private LinkedList<Square> squares = new LinkedList();    public Board() {        this.build();    }    private void build() {        this.squares.clear();        for (int y = 1; y <= BOARD_HEIGHT; y++) {            for (int x = 1; x <= BOARD_WIDTH; x++) {                this.squares.add(new Square(x, y, new Blank()));            }        }    }    public void play() {        this.printWelcome();        while (true) {            // build or re-build board from previous play            this.build();            // prompt and validates move input, then creates a move object            Move move = null;            while (move == null) {                try {                    move = new Move(this.readMove(), this);                } catch (IllegalArgumentException e) {                    System.out.println(ERROR:  + e.getMessage() +  Please try again.);                }            }            // set our source square with a knight piece, solve move, and print our boards + solutions            move.getSource().setPiece(new Knight());            LinkedList<LinkedList<Square>> solutions = getKnightTravailsSolutions(move);            this.print(solutions);        }    }    private String readMove() {        Scanner scanner = new Scanner(System.in);        System.out.println();        System.out.println();        System.out.println(=======================================================================================);        System.out.print(MOVES: );        return scanner.nextLine();    }    public Square getSquare(int x, int y) {        for (Square square: squares) {            if (square.matches(x, y)) return square;        }        return null;    }    // ------------------------------------------------------------------------------------------------    // KNIGHT TRAVAILS FUNCTIONS    // ------------------------------------------------------------------------------------------------    public LinkedList<LinkedList<Square>> getKnightTravailsSolutions(Move move) {        // breadth-first search implementation        // return a list of shortest path solution, each solution contains a list of squares it travels        LinkedList<LinkedList<Square>> solutions = new LinkedList();        LinkedList<LinkedList<Square>> queue = new LinkedList();        LinkedList<Square> visited = new LinkedList();        boolean solutionFound = false;        // initialize first path, our very first path is the source square of the move        // this is technically a path, imagine in a case where our source and destination is the same square        LinkedList<Square> firstPath = new LinkedList();        firstPath.add(move.getSource());        queue.add(firstPath);        while (!queue.isEmpty()) {            LinkedList<Square> currentPath = queue.removeFirst();            Square currentSquare = currentPath.getLast();            if (currentSquare == move.getDestination()) {                solutions.add(currentPath);                solutionFound = true;            }            if (!solutionFound) {                for (Square nextLegalSquare: this.getKnightNextLegalMoves(currentSquare)) {                    if (!visited.contains(nextLegalSquare)) {                        LinkedList<Square> nextPath = new LinkedList();                        nextPath.addAll(currentPath);                        nextPath.add(nextLegalSquare);                        queue.addLast(nextPath);                    }                }            }            if (!visited.contains(currentSquare)) visited.add(currentSquare);        }        return solutions;    }    private LinkedList<Square> getKnightNextLegalMoves(Square source) {        // brute force search to find next legal squares to all squares on board        // returns a list of possible next move squares given a source square        LinkedList<Square> nextMoves = new LinkedList();        for (Square destination: squares) {            int xMoveDistance = destination.getX() - source.getX();            int yMoveDistance = destination.getY() - source.getY();            // since a knight hops over other pieces, we just need to ensure no piece  exist within our destination square            // and, whether we moved 2 then 1 space or 1 then 2 spaces            if ((destination.getPiece().isBlank()) && (Math.abs(xMoveDistance * yMoveDistance) == 2)) {                   nextMoves.add(destination);             }        }        return nextMoves;    }    // ------------------------------------------------------------------------------------------------    // PRINTING FUNCTIONS    // ------------------------------------------------------------------------------------------------    private void printWelcome() {        System.out.println();        System.out.println();        System.out.println(=======================================================================================);        System.out.println(The Knight's Travails Challenge);        System.out.println(=======================================================================================);        System.out.println();        System.out.println(Welcome! :) I accept two squares identified by algebraic chess notation.);        System.out.println(The first square is the starting position and the second square is the ending position.);        System.out.println(I will then find the shortest sequence of valid moves to take a Knight piece from the);        System.out.println(starting position to the ending solution.);        System.out.println();        System.out.println(Example input would be: A8 B7);    }    private void print(LinkedList<LinkedList<Square>> solutions) {        if (solutions.isEmpty()) {            System.out.println( SOLUTION #1: No solution exists);        } else {            for (LinkedList<Square> solution: solutions) {                System.out.println(this.getBoardLine(solution));                System.out.println( SOLUTION # + ((int)solutions.indexOf(solution) + 1) + :  + this.getSolutionLine(solution));            }        }    }    public String getSolutionLine(LinkedList<Square> solution) {        String line = ;        if (solution.getFirst() == solution.getLast()) {            line += No travel required;        } else {            for (Square square: solution) {                if (square != solution.getFirst()) line += square.toChessNotation() +  ;            }        }        return line;    }    private String getBoardLine(LinkedList<Square> solution) {        String line = \n;        line += this.getBoardTopLine() + \n;        line += this.getBoardMiddleLine() + \n;        for (int y = 1; y <= this.BOARD_HEIGHT; y++) {            for (int x = 1; x <= this.BOARD_WIDTH; x++) {                Square square = this.getSquare(x, y);                if (!square.getPiece().isBlank()) {                    line +=  |  + square.getPiece().toChessNotation();                } else if (solution.contains(square)) {                    line +=  |  + solution.indexOf(square);                } else {                    line +=  |  + square.getPiece().toChessNotation();                }            }            line +=  |  + y + \n;            line += this.getBoardMiddleLine() + \n;        }        return line;    }    private String getBoardMiddleLine() {        String line =  ;        for (int i = 0; i < this.BOARD_WIDTH; i++) {            line += +---;        }        line += ;        return line;    }    private String getBoardTopLine() {        String line =  ;        char startChar = 'a';        for (int i = 0; i < this.BOARD_WIDTH; i++) {            line +=    + startChar +  ;            startChar++;        }        return line;    }}Other classes:public class Move {    private Square source, destination;    public Move(String moveInput, Board board) {        if (moveInput == null || moveInput.length() != 5 || moveInput.charAt(2) != ' ') {            throw new IllegalArgumentException(Invalid input.);        }        int fromX = (int)moveInput.toUpperCase().charAt(0) - '@';        int fromY = (int)moveInput.toUpperCase().charAt(1) - '0';        int toX = (int)moveInput.toUpperCase().charAt(3) - '@';        int toY = (int)moveInput.toUpperCase().charAt(4) - '0';        // check whether the squares are actually exists        // e.g given input a9 a1, square a9 might not be exist in 8x8 board        if ((board.getSquare(fromX, fromY) == null) || (board.getSquare(toX, toY)) == null) {            throw new IllegalArgumentException(Invalid input.);        }        this.source = board.getSquare(fromX, fromY);        this.destination = board.getSquare(toX, toY);    }    public Square getSource() { return this.source; }    public Square getDestination() { return this.destination; }    public String toChessNotation() {        String line = this.getSource().toString() +               + this.getDestination().toString();        return line;    }}public class Square {    private int x, y;    private Piece piece;    public Square(int x, int y, Piece piece) {        this.x = x;        this.y = y;        this.piece = piece;    }    public int getX() { return this.x; }     public int getY() { return this.y; }    public Piece getPiece() { return this.piece; }    public void setPiece(Piece piece) { this.piece = piece; }    public String toChessNotation() {        return (char)(this.x + 64) +  + (this.y);    }    public boolean matches(int x, int y) {        return (this.x == x && this.y == y);    }}public abstract class Piece {    public Piece() {}    public abstract PieceType getPieceType();    public abstract String toChessNotation();    public boolean isKnight() {         return getPieceType() == PieceType.KNIGHT;     }    public boolean isBlank() {         return getPieceType() == PieceType.BLANK;     }}public enum PieceType {    KNIGHT, BLANK;}public class Blank extends Piece {    public PieceType getPieceType() {         return PieceType.BLANK;     }    public String toChessNotation() {        return  ;    }}public class Knight extends Piece {    public PieceType getPieceType() {         return PieceType.KNIGHT;     }    public String toChessNotation() {        return N;    }}public class Main {    public static void main(String[] args) {        Board board = new Board();        board.play();    }}
Knight's Travails solution
java;design patterns;object oriented
I personally wouldn't do things like this.build(); but just build();... although that's a matter of taste. IMO this doesn't clarify anything but just adds noise to the code.I don't see any reason why your squares is a linked list. A matrix of Piece would suffice and it represents the purpose of squares better in my opinion. It would also simplify it all, since getSquare() would be a matter of querying the matrix indices instead of performing a search. It would also be more robust since you can have several squares with the same x and y. You're forcing it when you build the loop, but still...I would not remove Square completely, but I would keep it as a little bean for getKnightTravailsSolutions, Move, etc. ONLY representing the actual square (not the piece in it.)I would also move the play() (and related methods like printWelcome(), readMove(), etc.) out of Board. It has too many responsibilities: it not only is a board, but it also plays itself and carries the main program logic. Why? It fits better in your class Main (which I would call something like KnightsTravails to fit better its new purpose.It's clear you massed too much functionality because you had to separate it with things like this:// ---...// KNIGHT TRAVAILS FUNCTIONS// ---...Your public enum PieceType belongs to Piece just as Piece.Type.I see no reason why your notations are strings. Characters would be enough and it represents better the notion of one piece = one character in chess notation.I also see no reason to extend concrete pieces such as Blank and Knight since they're not encapsulating very much and just disseminate code all over the place. IMO I would just instance Pieces (that is, making it non-abstract) specifying WHICH piece in the constructor. To implement notation I would do like this:private enum Type {    BLANK (' '),    ...    KNIGHT ('N');    private final char notation;    Type(char notation) { this.notation = notation; }    private char notation() { return notation; }}It would make sense to extend in their own classes if you were actually adding specific logic to each piece (like movement types and so) but you're not doing so. Some would argue your approach offers better extensibility and reusability so your approach might be valid.Not sure if Java lets you do this (I think so, but can't check it) moveInput.charAt(2) could be written more succint as moveInput[2]. The same applies for many of your strings.What's going on in getKnightNextLegalMoves? Why would you bruteforce all over your board?If you have a source, you just have to check in [1,2]; [1,-2]; [-1,2]; [-1,-2]; [2,1]; [2,-1]; [-2,1]; [-2,-1].Regarding getKnightTravailsSolutions:Although you must instance your queue as a LinkedList (or any other class implementing Queue), I would prefer to specify its type as the interface, i.e.: Queue<LinkedList<Square>> queue = new LinkedList<LinkedList<Square>>(); It is more clear that it's a queue and will protect you from doing weird non-queue things. Use the queue interface (i.e. poll() and offer()) instead of removeFirst() and addLast().It might make more sense for visited to be a Set instead (since you're enforcing it anyways when checking in contains(currentSquare).This is not very important, but your visited.add(currentSquare); could be inside the if (!solutionFound) since you don't need to care about visited once you're on your last step.