用随机数填充矩阵,不垂直或水平重复

我刚才已经保存和修改了一些代码,以便在需要时使用。我想是给你的;)

import java.util.Arrays;
import java.util.Random;

class Test {
    public static void main(String[] args){
        int size = 9;

        int[][] matrix= new int[size][];
        matrix[0] = MatrixOps.createOrderedArray(size, 1);

        for(int x=0; x < size; x++) {
            matrix[x] = MatrixOps.createOrderedArray(size, 1);
            do {
                MatrixOps.shuffle(matrix[x]);
            } while(! MatrixOps.compare2DArray(matrix[x], matrix, 0, x));
        }
        MatrixOps.print(matrix);
    }
}

class MatrixOps {

    public static void shuffle(int[] arr){
        Random random = new Random();
        for(int x = 0; x < arr.length; x++)
            swap(arr, x, random.nextInt(arr.length));
    }

    public static int[] createOrderedArray(int size, int startValue) {
        int[] num = new int[size];
        for (int x = 0; x < num.length; x++)
            num[x] = x + startValue;
        return num;
    }

    public static boolean compare2DArray(int[] arr1, int[][] arr2, int begin, int end) {
        for (int x = begin; x < end; x++)
            if (!compareArray(arr1, arr2[x]))
                return false;
        return true;
    }

    // https://stackoverflow.com/questions/19648240/java-best-way-to-print-2d-array/41533179#41533179
    public static void print(int[][] array) {
        for (int[] x: array) {
            for (int y: x) {
                System.out.print(y + " ");
            }
            System.out.println();
        }
    }

    private static boolean compareArray(int[] arr1, int[] arr2){
        if(arr1.length != arr2.length)
            return false;
        for(int x=0; x<arr1.length; x++)
            if(arr1[x] == arr2[x])
                return false;
        return true;
    }

    private static void swap(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

实例输出:

5 1 7 2 3 8 9 4 6 
4 3 1 5 7 9 2 6 8 
9 7 3 8 6 2 4 5 1 
6 8 4 3 5 7 1 9 2 
1 5 8 9 2 6 7 3 4 
7 9 2 6 4 1 5 8 3 
8 6 9 4 1 5 3 2 7 
3 2 6 7 9 4 8 1 5 
2 4 5 1 8 3 6 7 9 

启动时定义以下矩阵:

1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8

当需要创建n x n矩阵时,请执行以下操作:

1. 为行号随机选取0-8之间的n个数字(不重复)->r
2. 为列号随机选取0-8之间的n个数字(不重复)->c
3. 最终矩阵的元素将是m[x][y]=o[r[x]][c[y]]]

唯一的问题是结果仍然不是完全随机的。(它不能生成所有可能的解决方案。)尽管随机性只在标题中提到,但在3个要求中没有提到…

我认为最好的方法是使用随机回溯算法。

矩阵的元素被依次填充。对于每个矩阵元素,我们首先枚举所有可以使用的剩余整数(基于前面的元素)。然后按随机顺序尝试每个问题,直到找到第一个解决方案。

public static void main(String[] args) {
    int[][] matrix = getMatrix(7, 0L);
    if (matrix != null) {
        for (int row = 0; row < 7; ++row) {
            for (int column = 0; column < 7; ++column) {
                System.out.print(matrix[row][column]);
            }
            System.out.println();
        }
    }
}


public static int[][] getMatrix(int size, long seed) {
    int[][] matrix = new int[size][size];
    Random random = new Random(seed);
    if (!backtrack(matrix, size, 0, random))
        return null;
    return matrix;
}

// returns true when the backtracking could succesfully fill the matrix
private static boolean backtrack(int[][] matrix, int size, int index, Random random) {
    if (index == size * size) {
        // all elements are filled without conflict
        return true;
    } else {
        // find the row and column of the next element which need to be filled
        int column = index % size;
        int row = index / size;

        // an array which indicates whether the numbers in range [1 - 9] can be used
        // canUse[x] encodes whether number (x+1) can be used
        boolean[] canUse = new boolean[9];
        Arrays.fill(canUse, true);

        // check the previous rows and column elements
        for (int c = 0; c < column; ++c)
            canUse[matrix[row][c] - 1] = false;
        for (int r = 0; r < row; ++r)
            canUse[matrix[r][column] - 1] = false;

        // generate the list of possible entries
        List<Integer> possibilities = new ArrayList<Integer>();
        for (int i = 1; i <= 9; ++i)
            if (canUse[i - 1])
                possibilities.add(i);

        // backtrack if there are no possible entries
        if (possibilities.isEmpty())
            return false;

        // shuffle the list (to randomly fill the matrix)
        Collections.shuffle(possibilities, random);

        // enter the number
        for (int possiblity : possibilities) {
            matrix[row][column] = possiblity;

            if (backtrack(matrix, size, index + 1, random))
                return true;
        }

        return false;
    }
}

输出:

4139562
1896375
2613857
9357124
6245931
3482619
8761493

给它一个疯狂的尝试,而不是写代码。但是想一想:

开始按列填充数字,这样

mat[0][0]=1

mat[1][0]=2

...

mat[8][0]=9

然后,当您开始填充下一列时,请执行以下操作:

mat[1][1]=1

mat[2][1]=2

...

mat[8][1]=8

mat[0][1]=9

等等。

所以它精确地按顺序和对角线填充数字。

使用纯粹的随机化来填充矩阵,如果到达死胡同,您将需要重做结果的最后一部分。

public static void call(){
    int repeats = 0;
    for (int i = 0; i < max; i++) {
        for (int j = 0; j <max ; j++) {
            for (int k = 0; k <max ; k++) {
                int num=numbers.get(k);
                if(!isExist(num,i,j)){
                    arr[i][j]=num;
                    break;
                }
            }
        }
        if(containsZero(arr[i]){
            i--;
            repeats++;
            if(repeats > 1000){
                i = 0;
                repeats = 0;
            }
        }
        Collections.shuffle(numbers);
    }
}
private static boolean containsZero(int[] array){
    for(int i = 0; i < array.length; i++){
        if(array[i] == 0){
            return true;
        }
    }
    return false;
}

在某些情况下,更改最后一行不足以保证矩阵将被填充。这就是为什么我添加了一个计数器,如果通过更改最后一行找不到解决方案,它将重置整个矩阵。