Knight's Travails solution

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 squares = new LinkedList();

public Board() {
this.build();
}

private void build() {
this.squares.clear();
for (int y = 1; y > 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> getKnightTravailsSolutions(Move move) {

// breadth-first search implementation
// return a list of shortest path solution, each solution

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> queue = new LinkedList>(); 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.

StackExchange Code Review Q#11496, answer score: 3