java – Putting as many ships on a square board as possible


Github repository

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

  1. create a number of ships (dotcoms in my example)
  2. generate random cells for all the ships (in my case dotcoms)
  3. let the user try to guess

I implemented a way to place as many “dotcoms” as possible:

If I have a 3×3 board and I want to place 4 “dotcoms” 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(){

    for (int i = 0; i < dotcom_numbers; i++) {
        Dotcoms.add(new DotCom());
    }

    ArrayList<String> toTest;
    int leftToPlace = dotcom_numbers;

    for (DotCom dotcom : Dotcoms){
        System.out.println("generating cells for "+dotcom);

        while(true){

            toTest = generateCells();

            if (!checkDotcoms(toTest)){ //this checks if cells are in any other dotcom

                if(backtrackDotcoms(toTest, leftToPlace)){ //this checks if its possible to place the rest of dotcoms if we chose this cells
                    dotcom.setDotCom(toTest);
                    System.out.println("success for "+dotcom+" "+toTest);
                    System.out.println();
                    leftToPlace--;
                    break;
                }
            }
        }
    }
}

private boolean backtrackDotcoms(ArrayList<String> toBacktrack, int dotcomsToPlace){
    boolean backtrack_result = false;
    ArrayList<String> cells;
    ArrayList<ArrayList<String>> givenCells = new ArrayList<>();

    for (int i = 0; i < (dotcom_numbers - dotcomsToPlace); i++) {
        givenCells.add(Dotcoms.get(i).getCells());
    }

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

    if (!givenCells.isEmpty()) {

        givenCells.add(toBacktrack);
        dotcomsToPlace--;

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

            for (int j = 0; j < 100; 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;
                }
            }
        }
    } else{
        backtrack_result = true;
    }

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

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

I have basically two questions.

Is this backtracking?

Where can I optimize the code?