2D数组，行和列中没有重复项

时间：2022-07-08 21:31:43

I need to construct a 8x8 array filled with numbers from 0 to 7, but there can't be any duplicates in rows and columns. Also, the seqence produced should be random.

我需要构造一个8x8数组,其中填充0到7之间的数字,但行和列中不能有任何重复。此外,产生的序列应该是随机的。

For instance:

0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 0
2 3 4 5 6 7 0 1
3 4 5 6 7 0 1 2
4 5 6 7 0 1 2 3
5 6 7 0 1 2 3 4
6 7 0 1 2 3 4 5
7 0 1 2 3 4 5 6

is a valid array since there are no duplicates in any row / column.

是一个有效的数组,因为任何行/列中都没有重复项。

I started off with this code, however it obviously crashes whenever it runs out of possible numbers to choose from.

我开始使用这个代码,但是当它用尽可能的数字时它显然会崩溃。

int[][] array = new int[8][8];
List <Integer> numbers = new ArrayList<Integer>(Arrays.asList(0,1,2,3,4,5,6,7));
Collections.shuffle(numbers);

//populate first row
for(int i = 0; i <= 7; i++) {
   array[0][i] = numbers.get(i);
}

//populate the rest of array
for(int i = 1; i <= 7; i++) {

   Collections.shuffle(numbers);

   for(int j = 0; j <= 7; j++) {
      Deque<Integer> numbersToPickFrom = new ArrayDeque<>(numbers);

      //Remove duplicates from above
      for (int k = 0; k < i ; k++)
         numbersToPickFrom.remove(array[k][j]);

      //Remove duplicates from left
      for (int k = 0; k < j ; k++)
         numbersToPickFrom.remove(array[i][k]);

      array[i][j] = numbersToPickFrom.pop();
      System.out.print(array[i][j]+" ");
   }

   System.out.print("\n");

}

Output:

3 4 5 7 6 0 2 1 
4 5 6 2 0 7 3 Exception in thread "main" java.util.NoSuchElementException
    at java.util.ArrayDeque.removeFirst(ArrayDeque.java:280)
    at java.util.ArrayDeque.pop(ArrayDeque.java:517)
    at kamisado_logic.Board.createRandomSquares(Board.java:209)
    at kamisado_util.ThreadDriver.main(ThreadDriver.java:17)

I feel like my approach is faaar from the best one, any tips would be much appreciated.

我觉得我的方法是最好的方法,任何提示都会非常感激。

1 个解决方案

#1

2  

Your problem is very similar to generating sudoku grid, with a few constraints removed :

您的问题与生成数独网格非常相似,删除了一些约束:

  • you have only 8 rows and columns instead of 9

    • 你只有8行而不是9行

  • you don't have to have unique values in subsquares

    • 您不必在子方格中具有唯一值

You could look at sudoku generation algorithm, and remove the parts you don't need. Here are a few hints to start :

您可以查看数独生成算法,并删除不需要的部分。以下是一些提示:

#1

2  

Your problem is very similar to generating sudoku grid, with a few constraints removed :

您的问题与生成数独网格非常相似,删除了一些约束:

  • you have only 8 rows and columns instead of 9

    • 你只有8行而不是9行

  • you don't have to have unique values in subsquares

    • 您不必在子方格中具有唯一值

You could look at sudoku generation algorithm, and remove the parts you don't need. Here are a few hints to start :

您可以查看数独生成算法,并删除不需要的部分。以下是一些提示:

标签：

相关文章