Validating a Battleship board, 2d array, how to check possibilities for boards validity?

The board is valid if the position of all of the ships are valid.

This means you need a data structure for the ship. To start, a simple data structure might be [ ship_type, [ position_1 , position_2, position_3 ] ]

Once you have data structures for the ship, it is trivial to check that all of the ships are on the board, no two ships share a single position, and the correct number of ships of each type are on the board. Correct number of ships of each type can go into a Fleet data structure.

With a ship, you will quickly realize that the board for the side with awareness of its fleet can be rendered with letters for their ships. But the other board is "special" because there is no ship visibility. This means that (as in the real game) Battleship consists of two kinds of board, a hit-detection board and a ship positioning board. That they look similar is only a side-effect of manufacturing.

Now for the HitBoard how would and AI attempt to hunt down a ship? Well, they would start off with random placements, or a pattern. There are advantages to both approaches. Once a hit is detected, then it will consult the number of remaining ships on the field, and start probing along the horizontal and vertical axis to find the ship's full position. Once it is told "You sunk my " It will know that the sunk ship must be removed from play.

 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,1,1,1,1,0,0},
 {0,0,0,0,1,1,1,1,0,0},
 {0,0,0,0,1,1,1,1,0,0},
 {0,0,0,0,1,1,1,1,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},

Consisting of two battleships, a destroyer, a submarine, and a cruiser. Without additional information, it will be impossible to know of the majority of the ships are oriented left-to-right or top-to-bottom.

Occasionally, it is even impossible to know the ship positioning while play is occurring. Interestingly enough, that might not always be enough information to know the position of the ship. This sometimes occurs when the ships are in a tightly packed formation, and you sink a ship by placing an attack within a row or column (or both) of squares that already have registered hits. In this case, your hit might not define the end of the sunk item.

If the goal is to validate the board without any extra information beyond position, then you need to take a different approach.

1. Order the ships by size.
2. Within the current board position, repeat until there are no ships available.
3. Select the largest ship.
4. Search for all possible positionings of the largest ship, generating new boards without the markings for the ship's position.
5. If the ship could not be placed, the board was not a valid board configuration.
6. If the ship list is empty and the board has markings, the board was not a valid board configuration.
7. If the ship list is empty and the board is empty, the markings were in a valid board configuration.
8. Repeat, treating all boards independently for the generated boards from step 2.

This is a brute-force approach; but, within the brute-force approach are a number of optimizations that are possible.

Since we can't tell the ships apart with certainty we will need to try different possibilities. Try placing a ship in a possible position (reserving that position) and then try for the next ship recursively. (This is probably what others have suggested too). For a 10x10 board with this few ships the computation is pretty quick.

Here is my attempt to implement it.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import java.util.concurrent.atomic.AtomicInteger;

public class Main {
    private static final int SIZE = 10;
    private static final int HORIZONTAL = 0;
    private static final int VERTICAL = 1;

    private static final int[] shipSizes = {4, 3, 3, 2, 2, 2};
    private static final int NR_OF_ONES = 4;

    private static final int[][] board1 = {
            {1, 0, 0, 0, 0, 1, 1, 0, 0, 0},
            {1, 1, 0, 0, 0, 0, 0, 0, 1, 0},
            {1, 1, 0, 0, 1, 1, 1, 0, 1, 0},
            {1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
            {0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
            {0, 0, 0, 1, 0, 0, 0, 0, 1, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

    private static AtomicInteger counter = new AtomicInteger();

    public static void main(String[] args) {
        int[][] board = board1;

        validateBoard(board);
        long start = System.nanoTime();
        boolean valid = checkBoard(board, 0);
        long time = System.nanoTime() - start;
        System.out.println("Board is " + (valid ? "" : "NOT ") + "valid");
        System.out.println("Checked board in " + time + " ns");
    }

    private static boolean checkBoard(int[][] currentBoard, int shipSizePos) {
        if (shipSizePos >= shipSizes.length) {
            return true;
//            return countOnes(currentBoard) == NR_OF_ONES;
        }
        List<Ship> currentSizeShips = findPossibleShips(currentBoard, shipSizes[shipSizePos]);
        boolean valid = false;
        for (Ship ship : currentSizeShips) {
            if(checkBoard(removeShipFromBoard(currentBoard, ship), shipSizePos + 1)) {
                return true;
            }
        }
        return valid;
    }

    private static int[][] removeShipFromBoard(int[][] board, Ship ship) {
        int[][] newBoard = new int[SIZE][SIZE];
        for (int r = 0; r < SIZE; ++r) {
            for (int c = 0; c < SIZE; ++c) {
                if ((ship.orientation == HORIZONTAL && r == ship.row && (c >= ship.col && c < ship.col + ship.size))
                        || (ship.orientation == VERTICAL && c == ship.col && (r >= ship.row && r < ship.row + ship.size))) {
                    newBoard[r][c] = 0;
                } else {
                    newBoard[r][c] = board[r][c];
                }
            }
        }
        return newBoard;
    }

    private static List<Ship> findPossibleShips(int[][] board, int size) {
        List<Ship> ships = new ArrayList<>();
        for (int r = 0; r < SIZE; ++r) {
            for (int c = 0; c < SIZE; ++c) {
                if (board[r][c] == 1) {
                    if (isPossibleHorizontalShip(board, size, r, c)) {
                        ships.add(new Ship(r, c, size, HORIZONTAL));
                    }
                    if (isPossibleVerticalShip(board, size, r, c)) {
                        ships.add(new Ship(r, c, size, VERTICAL));
                    }
                }
            }
        }
        return ships;
    }

    private static boolean isPossibleHorizontalShip(int[][] board, int size, int row, int col) {
        if (SIZE - col < size) {
            return false;
        }
        int c;
        for (c = col; c < SIZE && board[row][c] == 1; ++c) ;
        return c - col >= size;
    }

    private static boolean isPossibleVerticalShip(int[][] board, int size, int row, int col) {
        if (SIZE - row < size) {
            return false;
        }
        int r;
        for (r = row; r < SIZE && board[r][col] == 1; ++r) ;
        return r - row >= size;
    }

    private static int countOnes(int[][] board) {
        int ones = 0;
        for (int r = 0; r < SIZE; ++r) {
            for (int c = 0; c < SIZE; ++c) {
                ones += board[r][c];
            }
        }
        return ones;
    }

    private static void validateBoard(int[][] board) {
        for (int r = 0; r < SIZE; ++r) {
            for (int c = 0; c < SIZE; ++c) {
                if (!(board[r][c] == 0 || board[r][c] == 1)) {
                    throw new IllegalArgumentException("Illegal character at " + r + ", " + c);
                }
            }
        }
        if (countOnes(board) != Arrays.stream(shipSizes).sum() + NR_OF_ONES) {
            throw new IllegalArgumentException("Wrong number of ship pieces");
        }
    }

    private static class Ship {
        private final int row;
        private final int col;
        private final int size;
        private final int orientation;

        public Ship(int row, int col, int size, int orientation) {
            this.row = row;
            this.col = col;
            this.size = size;
            this.orientation = orientation;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Ship ship = (Ship) o;
            return row == ship.row && col == ship.col && size == ship.size && orientation == ship.orientation;
        }

        @Override
        public int hashCode() {
            return Objects.hash(row, col, size, orientation);
        }

        @Override
        public String toString() {
            return "Ship{" +
                    "row=" + row +
                    ", col=" + col +
                    ", size=" + size +
                    ", orientation=" + orientation +
                    '}';
        }
    }
}

• First validates board to make sure it contains only 0s and 1s and the correct number of 1s
• Goes through the list of non size 1 ships from largest to smallest.
• Searches for possible placements for the current size, removes one and checks that branch for the next size
• When only 1s remain, the board is OK (we rely on the count from the validation to be correct)

I think the best way to approach this is to iteratively place ships, starting with the biggest. A rough outline of an algorithim is this:

• Select the largest ship not placed
• Consider a list of all possible placements
• For every possible placement, remove those 1s from the array, and repeat the process, without the ship you just placed

Since you aren't encoding the type of ship certain points are, you can remove points from placed ships, and continue trying to place ships. This will explode as the number of ships increase, but I think its fast enough for this small solution.

An attempt at a solution that does not allow contact:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

public class BattleFieldValidator {
  private static final int SIZE = 10;

  private static class Ship {
    public int     col;
    public int     row;
    public boolean horizontal;
    public int     size;

    @Override
    public String toString() {
      return "size " + size + " at (" + (row + 1) + "," + (col + 1) + ") " + (horizontal ? "horizontal" : "vertical");
    }
  }

  public static void validateField(int[][] field) {
    // 10x10 field
    if(field.length != SIZE || field[0].length != SIZE) {
      throw new RuntimeException("invalid field dimensions");
    }

    // each cell 0 or 1
    for(int row = 0; row < SIZE; row++) {
      for(int col = 0; col < SIZE; col++) {
        int cellValue = field[row][col];
        if(cellValue != 0 && cellValue != 1) {
          throw new RuntimeException("invalid cell value at (" + (row + 1) + "," + (col + 1) + ")");
        }
      }
    }

    print(field);

    boolean[][] discoveredShipCells = new boolean[SIZE][SIZE];
    List<Ship> ships = new ArrayList<>();

    for(int row = 0; row < SIZE; row++) {
      for(int col = 0; col < SIZE; col++) {
        if(discoveredShipCells[row][col]) {
          continue;
        }

        if(field[row][col] == 1) {
          Ship ship = discoverShip(field, discoveredShipCells, row, col);
          ships.add(ship);
        }
      }
    }

    Collections.sort(ships, (a, b) -> b.size - a.size);
    System.out.println("discovered ships:");
    ships.forEach(s -> System.out.println(s));

    if(ships.stream().filter(s -> s.size == 4).count() != 1) {
      throw new RuntimeException("battleship(size 4) count != 1");
    }

    if(ships.stream().filter(s -> s.size == 3).count() != 2) {
      throw new RuntimeException("cruiser(size 3) count != 2");
    }

    if(ships.stream().filter(s -> s.size == 2).count() != 3) {
      throw new RuntimeException("destroyer(size 2) count != 3");
    }

    if(ships.stream().filter(s -> s.size == 1).count() != 4) {
      throw new RuntimeException("submarine (size 1) count != 4");
    }

    // ok
  }

  private static Ship discoverShip(int[][] field, boolean[][] discoveredShipCells, int shipStartRow, int shipStartCol) {
    Ship ship = new Ship();
    ship.row = shipStartRow;
    ship.col = shipStartCol;

    int horizontalSize = 0;
    for(int col = ship.col; col < SIZE && field[ship.row][col] == 1; col++) {
      horizontalSize++;
      discoveredShipCells[ship.row][col] = true;
    }

    int verticalSize = 0;
    for(int row = ship.row; row < SIZE && field[row][ship.col] == 1; row++) {
      verticalSize++;
      discoveredShipCells[row][ship.col] = true;
    }

    if(horizontalSize > 1 && verticalSize > 1) {
      throw new RuntimeException("ship extending both horizontally and vertically at (" + (ship.row + 1) + "," + (ship.col + 1) + ")");
    }

    ship.horizontal = verticalSize == 1;
    ship.size = ship.horizontal ? horizontalSize : verticalSize;

    // validate ship surrounded by ocean cells
    if(ship.horizontal) {
      // left & right
      validateOceanCell(ship, field, ship.row, ship.col - 1);
      validateOceanCell(ship, field, ship.row, ship.col + ship.size);
      // top & bottom
      for(int col = ship.col - 1; col <= ship.col + ship.size; col++) {
        validateOceanCell(ship, field, ship.row - 1, col);
        validateOceanCell(ship, field, ship.row - 1, col);
      }
    }
    else {
      // top & bottom
      validateOceanCell(ship, field, ship.row - 1, ship.col);
      validateOceanCell(ship, field, ship.row + ship.size, ship.col);
      // left & right
      for(int row = ship.row - 1; row <= ship.row + ship.size; row++) {
        validateOceanCell(ship, field, row, ship.col - 1);
        validateOceanCell(ship, field, row, ship.col + 1);
      }
    }

    return ship;
  }

  private static void validateOceanCell(Ship ship, int[][] field, int row, int col) {
    if(row < 0 || row >= SIZE || col < 0 || col >= SIZE) {
      return /* outside field, ignore */;
    }

    if(field[row][col] == 1) {
      throw new RuntimeException("ship " + ship + " not surrounded by whater at (" + (row + 1) + "," + (col + 1) + ")");
    }
  }

  private static void print(int[][] field) {
    System.out.println();
    for(int row = 0; row < SIZE; row++) {
      System.out.println(Arrays.stream(field[row]).boxed().collect(Collectors.toList()));
    }
  }
}

And minimal testing:

public class BattleFieldTest {

  @org.junit.Test
  public void test1() {
    int[][] battleField = { //
        { 1, 0, 0, 0, 0, 1, 1, 0, 0, 0 }, //
        { 1, 0, 1, 0, 0, 0, 0, 0, 1, 0 }, //
        { 1, 0, 1, 0, 1, 1, 1, 0, 1, 0 }, //
        { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, //
        { 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 }, //
        { 0, 0, 0, 0, 1, 1, 1, 0, 0, 0 }, //
        { 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 }, //
        { 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }, //
        { 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 }, //
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };
    BattleFieldValidator.validateField(battleField);
  }

  @org.junit.Test
  public void test2() {
    int[][] battleField = { //
        { 0, 0, 0, 1, 0, 1, 0, 1, 0, 0 }, //
        { 0, 0, 0, 0, 0, 1, 0, 1, 0, 0 }, //
        { 0, 0, 1, 0, 0, 1, 0, 1, 0, 0 }, //
        { 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 }, //
        { 1, 1, 0, 0, 1, 0, 0, 0, 0, 0 }, //
        { 0, 0, 0, 0, 0, 0, 0, 1, 1, 0 }, //
        { 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 }, //
        { 0, 0, 0, 0, 0, 1, 0, 0, 1, 0 }, //
        { 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 }, //
        { 0, 1, 1, 0, 0, 0, 0, 0, 0, 0 }, };
    BattleFieldValidator.validateField(battleField);
  }
}

Sample output:

[1, 0, 0, 0, 0, 1, 1, 0, 0, 0]
[1, 0, 1, 0, 0, 0, 0, 0, 1, 0]
[1, 0, 1, 0, 1, 1, 1, 0, 1, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 1, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
discovered ships:
size 4 at (1,1) vertical
size 3 at (3,5) horizontal
size 3 at (6,5) horizontal
size 2 at (1,6) horizontal
size 2 at (2,3) vertical
size 2 at (2,9) vertical
size 1 at (5,9) horizontal
size 1 at (7,9) horizontal
size 1 at (8,4) horizontal
size 1 at (9,8) horizontal

I think @AlexRudenko meant this would be easier to validate:

 {0,0,0,0,0,0,0,2,2,0},
 {0,0,0,0,0,0,0,3,3,3},
 {0,0,0,0,0,4,4,4,4,0},
 {0,2,0,0,0,0,0,0,1,0},
 {0,2,0,0,3,3,3,0,0,0},
 {0,0,0,0,1,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,2,0,0,0,0,2,1,0},
 {0,0,2,0,0,0,0,2,1,0},