代码之家 › 专栏 › 技术社区 › ADM

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

sudoku algorithm java

ADM · 技术社区 · 6 年前

这更符合逻辑。问题是:

我需要用数字(1-9)填充矩阵,这样:

行中不应重复任何数字
列中不应重复任何数字
矩阵可以从3x3到8x8
矩阵应该包含随机数,而不是特定的顺序

我不擅长将我尝试过的逻辑表述为:

公共类randmatrix{ 静态int max=8; static arraylist<integer>numbers=new arraylist<gt;(); 静态int[][]arr=new int[max][max]; 公共静态void main(string[]a){ //填充数字对于(int i=1;i<=9;i++){ 加上(i); } //随机播放数集合。随机播放(数字); 调用(); } 公共静态void调用()。{ 对于(int i=0;i<max;i++){ 对于(int j=0;j<max;j++){ 对于(int k=0;k<max;k++){ int num=数字。get(k); 如果(!)I存在(num,i,j))。{ ARR[i] [j]=num; 断裂; } } } 集合。随机播放(数字); } } 私有静态布尔ISexist(int num,int row,int col){ 对于(int i=row;i>=0;i--){ 如果(arr[i][col]==num){ 回归真实; } 对于(int j=col;j>=0;j--){ if(arr[行][j]=num){ 回归真实; } } 返回错误; } } < /代码>

当我打印二维数组时,我看到在某些地方仍然有0作为值。似乎我的代码中断了。在某一点上,没有剩余的可以填充的随机数。输出类似于:

我知道我的算法不对,我只是找不到一种方法来完成它。我能得到一些帮助吗?

列中不应重复任何数字

矩阵可以从3x3到8x8

矩阵应该包含随机数,而不是特定的顺序

我不擅长将我尝试过的逻辑表述为:

public class RandMatrix {
static int max=8;
static ArrayList<Integer> numbers=new ArrayList<>();
static  int[][] arr=new int[max][max];
public static void main(String[] a){
    // To fill number
    for (int i = 1; i <=9; i++) {
        numbers.add(i);
    }
    // Shuffle number
    Collections.shuffle(numbers);
    call();
}

public static void call(){
    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;
                }
            }
        }
        Collections.shuffle(numbers);
    }
}

private static boolean isExist(int num,int row, int col){
    for (int i = row; i >=0; i--) {
        if(arr[i][col]==num){
            return true;
        }
    }
    for (int j = col; j >=0; j--) {
        if(arr[row][j]==num){
            return true;
        }
    }
    return false;
}
}

当我打印二维数组时,我看到在某些地方仍然有0作为值。似乎我的代码中断了。在某一点上,没有剩余的可以填充的随机数。输出类似于:

我知道我的算法是不对的,我只是找不到一种方法来完成它。我能得到一些帮助吗?

5 回复 | 直到 6 年前

Soner from The Ottoman Empire 6 年前

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

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

Selindek 6 年前

启动时定义以下矩阵:

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矩阵时,请执行以下操作:

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

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

Niels Billen 6 年前

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

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

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

输出:

Kagemusha 6 年前

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

开始按列填充数字,这样

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

等等。

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

Turamarth 6 年前

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

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

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