Fill a Matrix with Random Number with no repeat vertically or horizontally

Question

This is more of a logical question . Problem IS:

I need to fill a Matrix with number (1-9) In such a way so that :

1. No number should repeat in row
2. No number should repeat in column
3. Matrix can be from 3X3 to 8X8
4. Matrix should contain Random numbers not in some particular order

I am not good at putting logic what i have tried is below :

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

When i print the 2-d array i see in some places there is still 0 as value . Seems like my code breaks. at some point there is no random number left which can be filled. Output is something like :

I know my algo is not right i just can not find a way to make it done . Can i get some help on this.

Answer 1

I've saved and modified some the code a while ago so as to use if I need another time. I think it's for you ;)

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

Example output:

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 

Answer 2

Define the following matrix during startup:

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

When you need to create a n X n matrix do the following:

1. Randomly pick N numbers between 0-8 (without repeats) for row numbers ->R
2. Randomly pick N numbers between 0-8 (without repeats) for column numbers ->C
3. The elements of the final matrix will be M[x][y] = O[R[x]][C[y]]

The only problem is that the result is still not totally random. (It cannot generate ALL of the possible solutions.) Although the randomness is mentioned only in the title but not in the 3 requirements...

Answer 3

I think the best approach is to use a randomized backtracking algorithm.

The elements of the matrix are filled, one after the other. For each matrix element, we first enumerate all the remaining integers which can be used (based on the previous elements). Then each of them is tried in a random order untill the first solution is found.

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

Output:

4139562
1896375
2613857
9357124
6245931
3482619
8761493

Answer 4

Giving it a wild shot, not writing code. But thinking out:

How about start filling numbers column-wise, such that

mat[0][0]=1

mat[1][0]=2

...

mat[8][0]=9

Then when you starting filling the next column, do like:

mat[1][1]=1

mat[2][1]=2

...

mat[8][1]=8

mat[0][1]=9

and so on.

So its precisely filling the numbers sequentially and diagonally.

Answer 5

Using purely randomization to fill the matrix you will need to redo the last part of the result if you reach a dead end.

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

In some cases changing the last row isn't enough to guarantee that the matrix will be filled. That is why I added a counter which will reset the whole matrix if no solution can be found by changing the last row.