验证战舰游戏棋盘，2D数组，如何检查棋盘有效性的可能性？

Question

验证战舰游戏棋盘，2D数组，如何检查棋盘有效性的可能性？

javapuzzle

4

使用Java编写代码来验证战舰版，给定一个由1和0组成的二维数组，其中1是船的一部分，0是海洋。以下是需要了解的规则：

- 必须有一个单独的战舰（4个单元大小），2个巡洋舰（3个单元大小），3个驱逐舰（2个单元大小）和4艘潜艇（1个单元大小）。不允许任何额外的船只，也不允许缺少船只。

- 每艘船必须是一条直线，除了潜艇，它们只是单个单元格。

- 船不能重叠，但可以与任何其他船接触。

我的方法只是计算大小为2,3,4的船只的所有可能的连接，并确保它们比所需的船只数量更大。这对于每种情况都不起作用，还可以帮助检查是否恰好有20个放置点。问题在于，如果我们有0 1 1 1 1 0 0 0 0 0，它会告诉我它是有效的，尽管它明显不是（因为它是一行和一艘船），当我有以下内容时：应该是错误的，但我的返回值是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},

或者，应该是错误的，但我的代码返回了真。

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

这是一个例子，当代码应该返回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},

但是当我有这个例子时：

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

应该是false，但我的代码返回true。所以我应该如何重构我的代码或者有一个解决方案，当我给定一个棋盘时，我不会真正知道它是否有效，但我的Java程序会知道？

这是我的代码，我尝试了一下，我的方法是制作一个列表，列出从最大到最小检查特定船只的所有变化（最大的将是[4 3 3 2 2 2]，不包括1，因为它会显著增加变化的数量，我可以用不同的方式更高效地检查它，最小的变化将是[2 2 2 3 3 4]，4最后，它们被重复是因为对于2有x3艘船，所以2 2 2，x2大小3艘船，所以3 3和x1大小4艘船，所以只有一个），这是代码：

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");
    }

}

这段代码现在似乎运行良好，但是当它应该返回true时却没有。

以下是一些例子，其中代码应该返回true，但实际上返回了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：

 {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：

 {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：

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

这里是真的：

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

但是代码在这些示例中返回false。

因此，在这个示例中。

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

它是有效的，因为：

[![enter image description here][1]][1]

但我的代码选择了尺寸的第一个选项，这就是我的代码返回false的原因-

[![enter image description here][2]][2]

那么我需要添加什么来解决这个问题？

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");
        }
}

这似乎有一些程序上的错误（不同于解决方案），不确定是否需要帮助。[1]: https://istack.dev59.com/bX32n.webp [2]: https://istack.dev59.com/tFP1N.webp

- Rocky cohn

你能检查每一行/列是否包含连续的1，如果是，则将它们添加到每艘船的计数器中吗？最后，请确保每种类型的船已被正确计数。 - Adrian Russo

1

为什么不用每艘船的编号来标记它们，比如1-战舰，2、3-巡洋舰等。这样可以更容易地验证游戏板。 - Nowhere Man

是的，你可以在@AdrianRusso处进行操作，但也可能有不同的选项，例如111是尺寸3和尺寸2。 - Rocky cohn

@AlexRudenko 我有点这样做了，我创建了一个名为num（猜我应该称其为ships）的数组，它存储数字 - 我现在会更改它)... 所以是的，我做了。 - Rocky cohn

@Abra，你的程序需要遍历所有可能性并确定棋盘是否有效。设置棋盘的人不会告诉你它是潜艇还是驱逐舰...我理解你的担忧，但我更喜欢使用1和0。 - Rocky cohn

我删除了我的初始答案，因为正如@Maurice Perry指出的那样，它不起作用。需要使用回溯算法。 - areus

5个回答

2

由于我们无法确定船只的区别，因此我们需要尝试不同的可能性。尝试将一艘船放置在可能的位置（保留该位置），然后递归地尝试下一艘船。（这也可能是其他人建议的方法）。对于一个10x10的棋盘，这么少的船只计算非常快。

以下是我的实现尝试：

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 +
                    '}';
        }
    }
}

首先验证棋盘，确保它只包含0和1，并且包含正确数量的1
从最大到最小遍历非大小为1的船只列表。
搜索当前大小的可能位置，移除一个并检查下一个大小的分支
当只剩下1时，棋盘就是OK的（我们依赖于验证中的计数正确）

- DarkMatter

1

我认为最好的方法是迭代地放置船只，从最大的开始。一个粗略的算法概述如下：

选择未放置的最大船只
考虑所有可能的放置位置列表
对于每个可能的放置位置，从数组中删除那些1，并重复该过程，不包括刚刚放置的船只

由于您没有对某些点的船只类型进行编码，因此可以从放置的船只中删除点，并继续尝试放置船只。随着船只数量的增加，这将变得非常复杂，但我认为对于这个小问题来说足够快速。

- Carson

这是我所做的，但它运行了太多的示例，因此不够好。另外，我想一次检查多个板子。此外，我的代码有一些错误。 - Rocky cohn

这差不多是我的方法，现在好像有点用了，但我不确定为什么我的代码还没有起作用。 - Rocky cohn

0

一种不允许接触的解决方案尝试：

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()));
    }
  }
}

还有最小化的测试：

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);
  }
}

示例输出：

[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

- Reto Höhener

谢谢，虽然我已经尝试并解决了战舰验证问题，而且其他规则也是一样的，所以我不需要这个。此外，没有接触比有接触更容易检查。不过你的代码应该返回棋盘是否有效的 true/false 值！ - Rocky cohn

我为你之前的问题编写了那段代码。返回一个布尔值并不困难：尝试/捕获整个验证方法，在发生异常的情况下返回false，否则返回true。但这样做会很可惜，因为你将失去所有可以向用户显示的良好错误信息。 - Reto Höhener

0

我认为@AlexRudenko的意思是这样更容易验证：

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

- Reto Höhener

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Edwin Buck · Accepted Answer

如果所有船只的位置都有效，则该棋盘是有效的。

这意味着你需要一个关于船只的数据结构。最简单的数据结构可能是 [ 船只类型, [ 位置1 , 位置2, 位置3 ] ]

一旦你有了船只的数据结构，检查所有船只是否在棋盘上、没有两艘船共享一个位置以及每种类型的船只数量是否正确就变得非常简单了。每种类型的正确数量可以放入一个名为 Fleet 的数据结构中。

有了船只，你很快会意识到，对于知道自己舰队的一方来说，棋盘可以用字母来表示它们的船只。但另一个棋盘则是“特殊”的，因为没有船只可见性。这意味着（就像真正的游戏一样）战舰游戏由两种棋盘组成，即命中检测棋盘和船只定位棋盘。它们看起来相似只是制造的副作用。

现在对于 HitBoard 来说，AI 如何尝试追踪一艘船只呢？好吧，他们会从随机的放置或模式开始。这两种方法都有优点。一旦发现击中，AI 就会查询场上剩余船只的数量，并开始沿着水平和垂直轴探测，以找到船只的完整位置。一旦它被告知“你击沉了我的”，它就会知道该沉没的船只必须从游戏中移除。

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

由两艘战列舰、一艘驱逐舰、一艘潜艇和一艘巡洋舰组成。没有额外的信息，大多数船只是左右或上下定向将不可能知道。

有时，在进行游戏时甚至无法知道船只的定位。有趣的是，这可能并不总是足够的信息来知道船只的位置。当船只处于紧密包装的编队中，并且您通过在已经注册了命中的方格的行或列（或两者）中放置攻击来击沉船只时，有时会发生这种情况。在这种情况下，您的命中可能不定义沉没物品的结束。

如果目标是验证板子而没有超出位置的任何其他信息，则需要采取不同的方法。

1.按大小对船只进行排序。 2.在当前板位内重复，直到没有可用的船只为止。 3.选择最大的船只。 4.搜索最大船只的所有可能定位，生成新的板子，不带有船只位置的标记。 5.如果无法放置船只，则该板子不是有效的板子配置。 6.如果船只列表为空且板子有标记，则该板子不是有效的板子配置。 7.如果船只列表为空且板子为空，则标记位于有效的板子配置中。 8.重复，在步骤2生成的板子中独立处理所有板子。

这是一种蛮力方法;但是，在蛮力方法中有许多优化是可能的。