Putting as many ships on a square board as possible

Question

Github repository

Origanally I wrote a program that let you play battleship against the computer.

Pretty easy:

1. create a number of ships
2. generate random cells for all the ships
3. let the user try to guess

I implemented a way to place as many ships as possible:

If I have a 3x3 board and I want to place 4 ships that are 2 cells long, there are only few placements that allow the maximum number of ships in the board.

Example correct placement:

|1|1|O|
|2|2|4|
|3|3|4|

Example wrong placement:

|0|1|1|
|2|2|0|
|0|3|3|

Code(full code on github):

public void prepareGame(){

    if (!(field_size*field_size/ship_length >= ship_numbers)){
        System.out.println("Error: Game numbers are invalid");
        System.exit(0);
    }

    
    for (int i = 0; i < ship_numbers; i++) {
        Ships.add(new Ship();
    }

    ArrayList<String> toTest;
    int leftToPlace = ship_numbers;

    for (Ship ship : Ships){
        System.out.println("generating cells for "+ship);

        while(true){

            toTest = generateCells();

            if (!checkShips(toTest)){

                if(backtrackShips(toTest, leftToPlace)){
                    ship.setShip(toTest);
                    System.out.println("success for "+ship+" "+toTest);
                    System.out.println();
                    leftToPlace--;
                    break;
                }
            }
        }
    }
}

---

private boolean backtrackShips(ArrayList<String> toBacktrack, int shipsToPlace){

    boolean backtrack_result = false;
    ArrayList<String> cells;
    ArrayList<ArrayList<String>> givenCells = new ArrayList<>();

    for (int i = 0; i < (ship_numbers - shipsToPlace); i++) {
        givenCells.add(Ships.get(i).getCells());
    }

    //System.out.println("backtracking: "+toBacktrack);
    //System.out.println("given cells before backtrack: "+ givenCells);
    givenCells.add(toBacktrack);
    shipsToPlace--;

    for (int i = 0; i < shipsToPlace; i++) {

        for (int j = 0; j < 1000; j++) {

            cells = generateCells();

            // check if cells lap over already chosen cells
            for (ArrayList<String> list : givenCells) {

                if (Collections.disjoint(list, cells)) {
                    backtrack_result = true;

                } else if (!Collections.disjoint(list, cells)) {
                    backtrack_result = false;
                    break;
                }
            }

            if(backtrack_result) {
                givenCells.add(cells);
                break;
            }
        }
    }

    if (shipsToPlace == 0) { //base-case
        backtrack_result = true;
    }

    //System.out.println("given cells after backtrack: "+ givenCells);
    return backtrack_result;
}

---

public boolean checkShips(ArrayList<String> cells){

    boolean result = false;

    for (Ship ship : Ships){

        if (!Collections.disjoint(cells, ship.getCells())){
            result = true;
        }
    }
    return result;
}

---

If you want to know the Ship Class:

package src;

import java.util.ArrayList;

public class Ship {


ArrayList<String> cells = new ArrayList<>();



public void setShip(ArrayList<String> cells){
    this.cells = cells;
}

public ArrayList<String> getCells(){
    return this.cells;
}

public String checkYourself(String stringTip){

    String result = "Miss";

    if (this.cells.contains(stringTip)){
        result = "Hit";

        this.cells.remove(stringTip);
    }

    if (this.cells.isEmpty()) {
        result = "submerged";
    }
    return result;
}
}

I have basically two questions.

Is this backtracking?

Where can I optimize the code?

Edit: changed naming of ships.

Answer 1

Code style

The formatting and naming is inconsistent and violates common Java conventions, but these things are also very easy to fix. All IDEs and some advanced text editors have features to quickly format the whole code, as well as to easily rename identifiers in all occurrences at once.

Many style guides can be found online for most programming languages and I would recommend choosing one and applying it consistently.

Some examples:

1. if (something) { vs. if(something){ and similar variations. I would expect the first one in all cases as the de-facto standard format, but your chosen style guide should set the rules. Rather than fixing these individually, I would recommend using the IDEs auto-formatting feature to fix the format of the whole file, as well as to be intentional with the correct format already while typing it.

2. ship_numbers should be shipNumbers, etc. Generally Java uses camel case for variable names.

Naming

Clear names are important to ensure that you and others understand the intent of the code and to avoid misunderstandings that can easily lead to bugs or just make it very tedious to maintain the code.

Some examples:

1. checkShips :
   What exactly does this method check? What does if (checkShips(cells)) tell me?

• Looking at the implementation, and knowing the game, it seems like the intent is to check for a collision, so something like isCollision would be much clearer. isOccupied would be another possible option.
• In general, I do not recommend wording boolean methods as commands, because of how if (checkShips()) or even if (checkCollision()) sounds.
• A further improvement, in my opinion, would be to pass the ships as another argument to the method, so that it reads like doesCollide(cells, ships), because it is more explicit and tells the reader the whole context. Otherwise it is implicit regarding what can collide with those cells.

2. setShips (within the Ship class):
   It is already within the context of a ship, so what would ship.setShip(cells) mean? Since the method actually sets the cells of the ship, setCells would make more sense. (The fact that having a setter at all might be problematic is a separate, more high-level point which I will not cover in this review, but potentially in a separate one with updated code.)
3. shipNumbers :
   Even after reading the code I am still not completely sure what this means. The names should make it easier to understand the context of the code, rather than requiring context to decipher their meaning.
   maxNumberOfShips might be clearer, assuming that my interpretation is correct.
4. toTest :
   To test what?
   Some suggestions:

• In the context of checkShips(), toCheck might be a slight improvement.
• cellsToCheck would be clearer.
• candidateCells makes sense in this case, since they are randomly generated and then checked against some rules (in this case having no collisions with existing ships).
• randomCells is less explicit about the intended use, but more explicit about its own meaning/origin.

Simplicity/readability

checkShips()

• Current version:

public boolean checkShips(ArrayList<String> cells){

    boolean result = false;

    for (Ship ship : Ships){

        if (!Collections.disjoint(cells, ship.getCells())){
            result = true;
        }
    }
    return result;
}

• Suggestion 1:

There is no need to iterate over all ships if the result is never reset to false again. Instead we can simply return true after the first match, and return false by default. Thus it already becomes much easier to reason about what can be returned in what case, since you can be sure that the return value is not being altered again afterwards.

public boolean checkShips(ArrayList<String> cells) {
    for (Ship ship : Ships) {
        if (!Collections.disjoint(cells, ship.getCells())){
            return true;
        }
    }
    return false;
}

• Suggestion 2:

The functional approach using Java streams is even less error prone, shorter and easier to understand.

public boolean checkShips(ArrayList<String> cells) {
    return ships.stream()
        .anyMatch(ship -> {
            !Collections.disjoint(cells, ship.getCells())
        });
}

• Suggestion 3:

Assuming we renamed the method to isCollision and passed the ships as argument, as suggested earlier, we can extract a second method with the same name but for a single ship, thus reducing the number of things done by each method per abstraction level.

public boolean isCollision(List<String> cells, List<Ship> ships) {
    return ships.stream()
        .anyMatch(ship -> isCollision(cells, ship));
}

private boolean isCollision(List<String> cells, Ship ship) {
    return !Collections.disjoint(cells, ship.getCells());
}

Debugging and commented-out code

//System.out.println("backtracking: "+toBacktrack);

These statements seem to have been used for debugging, but they clutter the code and make it harder to read. I recommend removing them and using an actual debugger instead. Of course there is nothing wrong with quickly adding a print statement temporarily to quickly check something, but it should be removed again before regarding the code as finished. This applies to commented-out code in general: If it is not needed anymore, it should be deleted. If it is simply commented out, how will you know later on whether it can be deleted or should be uncommented? Like most people, you would probably not be sure and ignore it, and thus it resides in the code base forever as a piece of commented-out code that does not add any value.

Next steps

There are (as is often the case) many more things that can be improved, but I would keep it at that for a first code review iteration focusing on lower level problems that are rather easy to fix and also easy to prevent in future code. Feel free to post a follow-up with an updated version of the code. Further iterations could cover more high-level concepts like design, OOP, layering etc.