Reputation: 81
Validating a Battleship board, 2d array, how to check possibilities for boards validity?
writing a code in Java to validate a battleship board when given a 2d array with 1's and 0's where 1 is a part of a ship and the 0 is the sea. here are the rules to know:
-There must be single battleship (size of 4 cells), 2 cruisers (size 3), 3 destroyers (size 2) and 4 submarines (size 1). Any additional ships are not allowed, as well as missing ships.
-Each ship must be a straight line, except for submarines, which are just single cell.
-The ship cannot overlap, but can be contact with any other ship.
my approach was just to count all the possible connections for the size 2 size 3 size 4 ships and make sure they are bigger than the amount of the size ship required, this doesn't work for every scenario, also I would help check if there are exactly 20 placements with 1's problem is that if we have 0 1 1 1 1 0 0 0 0 0 it will tell me that it is valid although it is definitely not(since its one row and one ship) and when I have the following: should be false but mine returns true->
{0,0,0,0,0,0,0,1,1,0},
{0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,1,1,1,0},
{0,1,0,0,0,0,0,0,0,0},
{0,1,0,0,1,1,1,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,1,0,0,0,0,1,1,0},
{0,0,1,0,0,0,0,1,1,0},
or which should be false but mine returns true->
{0,1,1,1,0,0,0,0,0,0},
{0,0,0,1,1,1,0,0,0,0},
{0,1,1,1,0,0,0,0,0,0},
{0,0,0,1,1,1,0,0,0,0},
{0,1,1,1,0,1,1,0,0,0},
{0,1,0,0,0,0,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},
here is an example where the code works when it should return true:
{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},
but when I have this example:
{0,0,1,0,0,0,0,1,1,0},
{0,1,1,0,0,0,0,0,0,0},
{1,1,1,1,1,0,0,0,0,1},
{0,0,1,1,1,1,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,1,1,0,0,0,0,0,0,0},
{0,0,0,0,0,0,1,0,0,1},
{0,0,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},
should be false but my code returns true. so how can I find a way to restructure my code or have a solution which when I am given a board I wouldn't really know whether its valid or not. but my Java program will?
here is my code with what I attempted for this, my approach here is to make a list with all the variations of checking specific ships from biggest to smaller(biggest would be [4 3 3 2 2 2] not including 1's since it will significantly raise the amount of variations and I can just check it differently and more efficiently, smallest variation would be [2 2 2 3 3 4] 4 last the reason they are repeated is because for 2 there are x3 ships so 2 2 2, x2 size 3 ships so 3 3 and x1 size 4 ship so just one) here is the code:
import java.util.*;
class Permute{
public static List<int[]> l;
Permute(){
this.l=new ArrayList<int[]>();
}
static void permute(java.util.List<Integer> arr, int k){
for(int i = k; i < arr.size(); i++){
java.util.Collections.swap(arr, i, k);
permute(arr, k+1);
java.util.Collections.swap(arr, k, i);
}
if (k == arr.size() -1){
l.add(arr.stream()
.map(i -> (i == null ? 0 : i))
.mapToInt(Integer::intValue)
.toArray());
}
}
public static List<int[]> get(){
Permute.permute(java.util.Arrays.asList(2,2,2,3,3,4), 0);Collections.reverse(l);
return l;
}
}
public class BF {
private static int[][] fields,copy;
private static int[] ship= {0,0,3,2,1};
public BF(int[][] field) {
fields=field;
// print(field);
this.copy=field;
}
public boolean validate() {
int cnt=counter(fields);
if(cnt!=20)return false;
Permute p= new Permute();//permutation constructor
List<int[]> list=p.get();//gets our specific permution
for (int i = 0; i < list.size(); i++) {//run through each option of our permution list
copy=fields;
ship=new int[]{0,0,3,2,1};//amount of ships needed
boolean flag=check(fields,list.get(i));//checks if the permution variation is true or false
int cnt1=counter(copy);//we checked boats of size 2 3 4 but not 1 which means if its valid then there should be 4 boats left
if(flag && cnt1==4)return true;
}
return false;
}
public static boolean check(int[][] field,int[] ships){
for(int i=0;i<ships.length;i++) {//go through the array and loop through the variation
int num=getBoat(fields, ships[i]);//if the boat is true on the certain boat we are checking
ship[num]--;//then -1 and at the end we want it to be [<=0,0,0,0,0]
}
int counter=0;
for(int i=2;i<ship.length;i++) {
if(ship[i]==0)counter++;//if [0,0,0]
}
if(counter==3) {return true;}//then return true
return false;
}
public static int getBoat(int[][] field,int num) {
int dire=0,r=0,c=0;String dir="row";
for (int col = 0; col < fields[0].length; col++) {
for (int row = 0; row < fields.length; row++) {//loop through each coordinate
if (copy[row][col] == 1) {//check if its part of a boat at the coor
int length=field.length;dir="row";dire=row;
for(int j=0;j<2;j++) {//go horizontal then vertical
if(j==1) {length=field[0].length;dir="col";dire=col;}//change length to vertical
if(dire+num-1<length) {//make sure we don't get outofbounds error
int cnt=0;
for(int i=0;i<num;i++) {//checks each coor according to type of boat we are checking
if(dir.equals("row")) {r=row+i;c=col;}
else if(dir.equals("col")){r=row;c=col+i;}
if(copy[r][c]==1) {//check
cnt++;//copy of battle field becomes 0
}
else copy=fields;//otherwise break this loop since it is not relevant anymore on this coor
if(cnt==num) {
for(int k=0;k<num;k++) {
if(dir.equals("row")) {r=row+k;c=col;}
else if(dir.equals("col")){r=row;c=col+k;}
copy[r][c]=0;//now we know its valid length and make it 0 on the copy
}
return cnt;
}}}} //if num is correct then return it
}
}
}return 0;
}
public static int counter(int[][] f) {// counts amount of tiles on the board with 1's
int cnt=0;
for (int col = 0; col < f[0].length; col++) {
for (int row = 0; row < f.length; row++) {
if (f[row][col] == 1) {
cnt++;
}
}
}
return cnt;
}
public static void print(int[][] field) {//prints the board
for (int row = 0; row < field.length; row++) {
for (int col = 0; col < field[0].length; col++) {
if(col<field[0].length-1 && col!=0) {
System.out.print( field[row][col]+",");
}
else if(col==field[0].length-1){
System.out.print( field[row][col]+"},");
}
else if(col==0) {
System.out.print(" {"+ field[row][col]+",");
}
}
System.out.println("");
}
System.out.println("\n");
}
}
the code seems to run well now but doesn't return true when its suppose to.
here are some examples where the code should return true but returns false:
{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},
true here:
{1,0,0,0,0,0,0,0,1,0},
{0,0,1,0,0,1,1,1,1,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,1,1,1,1,1,0,0,0},
{0,0,1,1,1,0,0,0,0,0},
{0,0,1,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,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
true here:
{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},
{1,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,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},
true here:
{1,1,1,0,0,0,0,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},
{1,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,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},
and true here:
{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},
but the code returns false on these examples
so in this example
{1,1,1,0,0,0,0,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},
{1,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,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},
it valid because:
[![enter image description here][1]][1]
but my code takes the first option of size and this is what happens which my code returns as false-
[![enter image description here][2]][2]
so what do I need to add to fix this problem?
public class BF {
private static int[][] fields;
public BF(int[][] field) {
fields=field;
print(field);
}
public boolean validate() {
int cnt=counter(fields);
if(cnt!=20)return false;
return checkBoard(fields, new int[]{4,3,3,2,2,2},0,new int[] {3,2,1});
}
public static boolean checkBoard(int[][] board,int[] SizePlacement,int k,int[] shipAmount){
if (counter(board)==4 ) {
return true;
}
int cnt=0;//SizePlacement={4,3,3,2,2,2}, ship(changes)={3,2,1}, k(starts at 0) is placement in ships[]
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board[0].length; col++) {
if(board[row][col]==1 && row+SizePlacement[k]<board.length) {//vertically
cnt=1;
for(int i=1;i<SizePlacement[k];i++) {//check vertically
if(board[row+i][col]==1) {cnt++;}
}
if(cnt>=SizePlacement[k]) {
int[][] newBoard = deepcopy(board);
newBoard= remove(newBoard , row, col, SizePlacement[k], "ver");
shipAmount[SizePlacement[k]-2]--;
if(shipAmount==new int[]{0,0,0}) {return true;}
if(k+1<SizePlacement.length && checkBoard(newBoard,SizePlacement,k+1,shipAmount)) {return true;}
shipAmount[SizePlacement[k]-2]++;
}
}
if(board[row][col]==1 && col+SizePlacement[k]<board[0].length) {//horizontally
cnt=1;
for(int i=1;i<SizePlacement[k];i++) {//check horizontally
if(board[row][col+i]==1) {cnt++;}
}
if(cnt>=SizePlacement[k]) {
int[][] newBoard = deepcopy(board);
newBoard= remove(newBoard , row, col, SizePlacement[k], "hor");
shipAmount[SizePlacement[k]-2]--;
if(shipAmount==new int[]{0,0,0}) {return true;}
if(k+1<SizePlacement.length &&checkBoard(newBoard,SizePlacement,k+1,shipAmount)) {
return true;
}
shipAmount[SizePlacement[k]-2]++;
}
}
}
}
return false;
}
public static int[][] remove(int[][] newBoard,int row,int col,int size,String orien){
int[][] removedBoard= deepcopy(newBoard);
if(orien=="ver") {
for(int i=0;i<size;i++) {
removedBoard[row+i][col]=0;
}
print(removedBoard);
return removedBoard;
}
else if(orien=="hor") {
for(int i=0;i<size;i++) {
removedBoard[row][col+i]=0;
}
print(removedBoard);
return removedBoard;
}
return removedBoard;
}
public static int[][] deepcopy(int[][] fields){
int[][] copy= new int[fields.length][fields[0].length];
for (int row = 0; row < fields.length; row++) {
for (int col = 0; col < fields[0].length; col++) {
copy[row][col]= fields[row][col];
}
}
return copy;
}
public static int counter(int[][] f) {// counts amount of tiles on the board with 1's
int cnt=0;
for (int col = 0; col < f[0].length; col++) {
for (int row = 0; row < f.length; row++) {
if (f[row][col] == 1) {
cnt++;
}
}
}
return cnt;
}
public static void print(int[][] field) {//prints the board
for (int row = 0; row < field.length; row++) {
for (int col = 0; col < field[0].length; col++) {
if(col<field[0].length-1 && col!=0) {
System.out.print( field[row][col]+",");
}
else if(col==field[0].length-1){
System.out.print( field[row][col]+"},");
}
else if(col==0) {
System.out.print(" {"+ field[row][col]+",");
}
}
System.out.println("");
}
System.out.println("\n");
}
}
this seems to have some kinda bug(different from the solution), not sure help on this would be appreciated [1]: https://i.sstatic.net/bX32n.png [2]: https://i.sstatic.net/tFP1N.png
Upvotes: 4
Views: 3314
Answers (5)
Reputation: 1017
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)
Upvotes: 2
Reputation: 5858
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},
Upvotes: 0
Reputation: 5858
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
Upvotes: 0
Reputation: 70999
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.
- Order the ships by size.
- Within the current board position, repeat until there are no ships available.
- Select the largest ship.
- Search for all possible positionings of the largest ship, generating new boards without the markings for the ship's position.
- If the ship could not be placed, the board was not a valid board configuration.
- If the ship list is empty and the board has markings, the board was not a valid board configuration.
- If the ship list is empty and the board is empty, the markings were in a valid board configuration.
- 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.
Upvotes: 2
Reputation: 3139
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.
Upvotes: 1
Related Questions
- Chess board that will check if a piece entered onto the board is in a valid position
- Implementing a second ship into one dimensional battleship game Java
- Java - 2D array checking diagonal number board
- How do I number gird arrays for battleship game?
- 2D array board rules
- Java 2D Array for chess board not working
- Checkers board in Java
- Java Battleship check Hit location
- Array programming - check winner in a Tic Tac Toe game for an nxn board with n players
- How to validate Battleship field?