Validating a Battleship board

Question

Do you know the game Battleship? Well, I want to play with my little brother, but before we can begin we need to set up our ships on the board. This is your input.

Now, we need to check that the ships that we set up are valid. This is where you come in to help. Your task is to write a program or function which checks whether the given 2d array (your board/input) is a valid board or not.

The input will be a 2d array, where 1 represents part of a ship and 0 represents part of the ocean.

The rules:

• There must be:
  • One battleship (size 4)
  • Two cruisers (size 3)
  • Three destroyers (size 2)
  • Four submarines (size 1)
• Any additional ships are not allowed, and neither are missing ships
• Each ship must be either vertical or horizontal (aside from submarines, which are a single grid space)
• The ships cannot overlap, but may be adjacent

in addition, you must solve this with a BF function (naturally the class will be called BF) which receives the 2d array(input) and uses a validate function. Afterward, you are free to manipulate the 2d array however you want and add any functions that you want.

here are some more examples(inputs) that your code must pass: is valid:

 {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},
 {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,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},

InvalidShapeOfBoat which is invalid->

 {1,0,0,0,0,1,1,0,0,0},
 {1,0,0,0,0,0,0,0,1,0},
 {1,1,0,0,1,1,1,0,1,0},
 {0,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,1,0,1,0,0,0,0,0,0},
 {0,1,0,0,0,0,0,1,0,0},
 {0,0,0,0,0,0,0,0,0,0},

wrong ships, result is 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,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,1,0,0},
 {0,0,0,0,0,0,0,0,0,0},

missing ships, is false->

 {0,0,0,0,0,1,1,0,0,0},
 {0,0,1,0,0,0,0,0,1,0},
 {0,0,1,0,1,1,1,0,1,0},
 {0,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},

check contact, is true->

 {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},

check another one with contact->

 {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},

check invalid, is false->

 {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},

random board which is false->

{0,1,0,0,0,0,0,0,0,0},
 {1,1,1,1,0,0,0,0,0,0},
 {1,0,1,1,1,0,0,0,0,0},
 {1,1,0,0,0,0,0,0,0,0},
 {1,1,0,0,0,0,0,0,0,0},
 {0,1,0,0,0,0,0,0,1,0},
 {0,0,1,0,0,0,0,0,1,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,1,0,0,0,0,0},

Who's code will be the shortest byte solution that passes all these examples successfully?! Good luck. ;)

Any language is allowed.

on the 16th I will award the winner with a nice green tick:)

Answer 1

JavaScript (ES6),  162  158 bytes

Returns 0 if the grid is invalid, or a positive integer otherwise.

m=>(o=0,g=u=>m.some((r,y)=>r.some((v,x)=>v&&[0,1].map(d=>(r=(w,X=x+!d*w,R=m[y+d*w]||0)=>R[X]&&R[R[X]--,u&(k=1<<w*3)*7&&g(u-k),r(-~w),X]++)``)))|u||++o)(668)*o

Try it online!

Commented

m => (                       // m[] = input matrix
  o = 0,                     // o = result
  g = u =>                   // g is a recursive function taking a bit mask u
                             // holding the ship counters on 4 x 3 bits
  m.some((r, y) =>           //   for each row r[] at position y in m[]:
    r.some((v, x) =>         //     for each value v at position x in r[]:
      v &&                   //       abort if v is not set
      [0, 1].map(d =>        //       otherwise, look for a horizontal ship (d = 0)
        (                    //       or a vertical ship (d = 1):
          r = (              //         r is a recursive function taking:
            w,               //           w = ship width - 1
            X = x + !d * w,  //           X = position of the cell in ...
            R = m[y + d * w] //           ... R[] = row of the cell
                || 0         //           (force it to 0 if undefined)
          ) =>               //
          R[X] &&            //           abort if R[X] is not set
          R[                 //
            R[X]--,          //           otherwise, set the cell to 0
            u & 7 *          //           if there's still at least one ship of
            (k = 1 << w * 3) //           width w to be found in the grid:
            && g(u - k),     //             do a recursive call to g with u updated
            r(-~w),          //           do a recursive call to r with w + 1
            X                //
          ]++                //           restore the cell afterwards
        )``                  //         initial call to r with u zero'ish
      )                      //       end of map()
    )                        //     end of some()
  )                          //   end of some()
  | u || ++o                 //   increment o if the grid has been cleared and all
                             //   boats have been found
)(668)                       // initial call to g with u = 668 (001 010 011 100)
* o                          // multiply by o

Answer 2

R, 211 bytes

v=function(b,f=c(3:1,2,1,1))`if`(any(f),{any(sapply(list(b,t(b)),function(m)any(apply(h<-which(m[1:(dim(m)[1]-f[1]),]>0,T),1,function(x)`if`(all(m[y<-t(x+rbind(0:f[1],0))]),{m[y]=0;v(m,f[-1])},F)))))},sum(b)==4)

Try it online!

How?
Pseudo-code version:

# recursive function:
validate_battleships= 
v=function(board,fleet_without_submarines)
    if there's nothing left in the fleet,
    and the board contains the right number of submarines:
        return(TRUE)                        
    else if any of these:
        try all positions:
            if we can place the first ship in the fleet:
                return result of recursive call
                after removing this ship from the board and the fleet
        return(TRUE)
    else return(FALSE)

And the actual, ungolfed R code:

validate_battleships= 
v=function(b,f=c(3:1,2,1,1))        # f=fleet=ship sizes minus 1, without submarines
  `if`(any(f),{                     # if there are any ships in the fleet:
    any(                            # return TRUE if any of these are true:
      sapply(list(b,t(b)),          # test the board and the transpose of the board (to try horizontal & vertical ship-placements)
        function(m)any(             # check if any of these are true:
          apply(h<-                 # test each nonzero position on the board (excluding the last rows that would make the ship go off the edge)
            which(m[1:(dim(m)[1]-f[1]),]>0,T),1,
              function(x)           # consider the first ship: f[1] (first item in fleet argument)
                `if`(all(m[y<-t(x+rbind(0:f[1],0))]),
                                    # if all the adjacent positions up to the ship size are nonzero (so we can place this ship),
                  {m[y]=0;          # set all these positions to zero
                   v(m,f[-1])}      # and return the result of a recursive call without this ship;
                ,F)                 # otherwise return FALSE
                ))))}
  ,sum(b)==4)                       # if there were no ships in the fleet, check that the nonzero positions on the board 
                                    # add-up to 4 (number of submarines): if they do, return TRUE.

Answer 3

Here is my answer in Java, I am definitely not skilled enough to get it down to a minimal amount of bytes and I prefer not to say(shortest byte solution for this code is down at the bottom of this post, credit to @ceilingcat for getting my code down to 482 bytes:P) try it, it works!

thanks to ceilingcat with the 482bytes solution:

int k,R[][],a[]=new int[]{4,3,3,2,2,2},d,e,s,x,y;boolean H(int[][]b,int I){var q=I==6;if(!q)for(int L=a[I++],r=d=b.length,c,M,N,i;r-->0;)for(c=e;c-->0;)for(M=N=i=1;b[x=r][y=c]>0&i<L;i++)q|=(M+=r+(s=L)>d?0:b[r+i][c])==L&&H(R(b,1),I)||(N+=c+L>e?0:b[r][c+i])==L&&H(R(b,0),I);return q;}int[][]R(int[][]n,int o){for(R=new int[k=d][e];k-->0;)R[k]=n[k].clone();for(;s-->0;)R[x+s*o][y-s*~-o]=0;return R;}boolean v(int[][]f){e=f[k=0].length;for(var y:f)for(var x:y)k+=x;return k==20&H(f,0);}

so here is my solution. (I went with a recursive solution for finding the ships)

public class BF {
    private static int[][] fields;
    public BF(int[][] field) {
        fields=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);
    }


    public static boolean checkBoard(int[][] board,int[] allBoats,int index){
        if (index == allBoats.length) {
            return true;
        }
        int boatLen = allBoats[index];
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[0].length; col++) {
                if(board[row][col]==1 && row+ boatLen <=board.length) {//vertically
                    int cnt=1;
                    for(int i=1;i<boatLen;i++) {//check vertically
                        if(board[row+i][col]==1) {cnt++;}
                    }
                    if(cnt>=boatLen) {
                        int[][] newBoard = deepcopy(board);
                        newBoard= remove(newBoard , row, col, boatLen, "ver");
                        if(checkBoard(newBoard,allBoats,index+1)) { return true;}
                    }
                }
                if(board[row][col]==1 && col+boatLen<=board[0].length) {//horizontally
                    int cnt=1;
                    for(int i=1;i<boatLen;i++) {//check horizontally
                        if(board[row][col+i]==1) {cnt++;}
                    }
                    if(cnt>=boatLen) {
                        int[][] newBoard = deepcopy(board);
                        newBoard= remove(newBoard , row, col, boatLen, "hor");
                        if(checkBoard(newBoard,allBoats,index+1)) { return true;}
                    }
                }
            }
        }
        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;
           }
           return removedBoard;
       }
       else if(orien=="hor") {
           for(int i=0;i<size;i++) {
               removedBoard[row][col+i]=0;
           }
           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;
      }
}

here is my Pseudo code on the Check board function

/*
 * 
 * function gets length of boat(field, size, ships){{3,2,1};
 * loop go through each position in field
 * checks vertically {
 *  finds option for where the boat can be 
 *  copies the board
 *  removes the boat from the copy
 *  call remove boat(function gets length of boat) for size-1, deepcopy
 *  if true then return true
 * }
 * check horizontal{
 *  finds option for where the boat can be 
 *  copies the board
 *  removes the boat from the copy
 *  call remove boat(function gets length of boat) for size-1, deepcopy
 *  if true then return true
 * }
 * else find next size 4 option
 * }
 */

let me know what u think:P

if you want to test it, here is some code for testing in my Java Solution:

import org.junit.Test;
import static org.junit.Assert.*;
public class SolutionTest {
    @Test
    public void testContact() {
          int[][] field = {};
        assertTrue("Must return true", new BF(field).validate());
    }
}