title: Validating a Battleship board, 2d array, how to check possibilities for boards validity?
body: <p>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:</p>
  <p>-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.</p>
  <p>-Each ship must be a straight line, except for submarines, which are just single cell.</p>
  <p><strong>-The ship cannot overlap, but can be contact with any other ship.</strong></p>
  <p>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-&gt;</p>
  <pre><code>  {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},
  </code></pre>
  <p>or
  which should be false but mine returns true-&gt;</p>
  <pre><code> {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},
  </code></pre>
  <p>here is an example where the code works when it should return true:</p>
  <pre><code> {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},
  </code></pre>
  <p>but when I have this example:</p>
  <pre><code>{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},
  </code></pre>
  <p>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?</p>
  <p>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:</p>
  <pre><code>import java.util.*;
  
  class Permute{
      public static List&lt;int[]&gt; l;
      Permute(){
          this.l=new ArrayList&lt;int[]&gt;();
      }
      static void permute(java.util.List&lt;Integer&gt; arr, int k){
          for(int i = k; i &lt; 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 -&gt; (i == null ? 0 : i))
              .mapToInt(Integer::intValue)
              .toArray()); 
          }
      }
       public static List&lt;int[]&gt; 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&lt;int[]&gt; list=p.get();//gets our specific permution
          for (int i = 0; i &lt; 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 &amp;&amp; cnt1==4)return true;
          }
          return false;
      }
     public static boolean check(int[][] field,int[] ships){
             for(int i=0;i&lt;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 [&lt;=0,0,0,0,0]
             }
             int counter=0;
             for(int i=2;i&lt;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=&quot;row&quot;;
       for (int col = 0; col &lt; fields[0].length; col++) {
          for (int row = 0; row &lt; 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=&quot;row&quot;;dire=row;
                 for(int j=0;j&lt;2;j++) {//go horizontal then vertical
                     if(j==1) {length=field[0].length;dir=&quot;col&quot;;dire=col;}//change length to vertical
                      if(dire+num-1&lt;length) {//make sure we don't get outofbounds error
                          int cnt=0;
                          for(int i=0;i&lt;num;i++) {//checks each coor according to type of boat we are checking
                              if(dir.equals(&quot;row&quot;)) {r=row+i;c=col;}
                              else if(dir.equals(&quot;col&quot;)){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&lt;num;k++) {
                                      if(dir.equals(&quot;row&quot;)) {r=row+k;c=col;}
                                      else if(dir.equals(&quot;col&quot;)){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 &lt; f[0].length; col++) {
          for (int row = 0; row &lt; 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 &lt; field.length; row++) {
              for (int col = 0; col &lt; field[0].length; col++) {
                  if(col&lt;field[0].length-1 &amp;&amp; col!=0) {
                      System.out.print( field[row][col]+&quot;,&quot;);
                  }
                  else if(col==field[0].length-1){
                      System.out.print( field[row][col]+&quot;},&quot;);
                  }
                  else if(col==0) {
                      System.out.print(&quot; {&quot;+ field[row][col]+&quot;,&quot;);
                  }
              }
              System.out.println(&quot;&quot;);
              }
    System.out.println(&quot;\n&quot;);
      }
  
  }
  </code></pre>
  <p>the code seems to run well now but doesn't return true when its suppose to.</p>
  <p>here are some examples where the code should return true but returns false:</p>
  <pre><code>{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},
  </code></pre>
  <p>true here:</p>
  <pre><code> {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},
  
  </code></pre>
  <p>true here:</p>
  <pre><code> {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},
  </code></pre>
  <p>true here:</p>
  <pre><code> {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},
  </code></pre>
  <p>and true here:</p>
  <pre><code>{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},
  </code></pre>
  <p>but the code returns false on these examples</p>
  <p>so in this example</p>
  <pre><code> {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},
  </code></pre>
  <p>it valid because:</p>
  <p>[![enter image description here][1]][1]</p>
  <p>but my code takes the first option of size and this is what happens which my code returns as false-</p>
  <p>[![enter image description here][2]][2]</p>
  <p>so what do I need to add to fix this problem?</p>
  <pre><code>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 &lt; board.length; row++) {
             for (int col = 0; col &lt; board[0].length; col++) {
               if(board[row][col]==1 &amp;&amp; row+SizePlacement[k]&lt;board.length) {//vertically
                 cnt=1;
                 for(int i=1;i&lt;SizePlacement[k];i++) {//check vertically
                     if(board[row+i][col]==1) {cnt++;}
                     }
                 if(cnt&gt;=SizePlacement[k]) {
                     int[][] newBoard = deepcopy(board);
                     newBoard= remove(newBoard , row, col, SizePlacement[k], &quot;ver&quot;);
                     shipAmount[SizePlacement[k]-2]--;
                     if(shipAmount==new int[]{0,0,0}) {return true;}
                     if(k+1&lt;SizePlacement.length &amp;&amp; checkBoard(newBoard,SizePlacement,k+1,shipAmount)) {return true;}
                    shipAmount[SizePlacement[k]-2]++;   
                 }
             }
              if(board[row][col]==1 &amp;&amp; col+SizePlacement[k]&lt;board[0].length) {//horizontally
                 cnt=1;
                 for(int i=1;i&lt;SizePlacement[k];i++) {//check horizontally
                     if(board[row][col+i]==1) {cnt++;}
                     }
                 if(cnt&gt;=SizePlacement[k]) {
                    int[][] newBoard = deepcopy(board);
                    newBoard= remove(newBoard , row, col, SizePlacement[k], &quot;hor&quot;);
                     shipAmount[SizePlacement[k]-2]--;
                     if(shipAmount==new int[]{0,0,0}) {return true;}
                     if(k+1&lt;SizePlacement.length &amp;&amp;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==&quot;ver&quot;) {
             for(int i=0;i&lt;size;i++) {
                 removedBoard[row+i][col]=0;
             }
             print(removedBoard);
             return removedBoard;
         }
         else if(orien==&quot;hor&quot;) {
             for(int i=0;i&lt;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 &lt; fields.length; row++) {
          for (int col = 0; col &lt; 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 &lt; f[0].length; col++) {
              for (int row = 0; row &lt; 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 &lt; field.length; row++) {
                  for (int col = 0; col &lt; field[0].length; col++) {
                      if(col&lt;field[0].length-1 &amp;&amp; col!=0) {
                          System.out.print( field[row][col]+&quot;,&quot;);
                      }
                      else if(col==field[0].length-1){
                          System.out.print( field[row][col]+&quot;},&quot;);
                      }
                      else if(col==0) {
                          System.out.print(&quot; {&quot;+ field[row][col]+&quot;,&quot;);
                      }
                  }
                  System.out.println(&quot;&quot;);
                  }
        System.out.println(&quot;\n&quot;);
          }
  }
  </code></pre>
  <p>this seems to have some kinda bug(different from the solution), not sure help on this would be appreciated
  [1]: <a href="https://i.stack.imgur.com/bX32n.png" rel="nofollow noreferrer">https://i.stack.imgur.com/bX32n.png</a>
  [2]: <a href="https://i.stack.imgur.com/tFP1N.png" rel="nofollow noreferrer">https://i.stack.imgur.com/tFP1N.png</a></p>