Generating "su doku" random matrices in MATLAB

I need to create multiple 5x6 matrices in MATLAB. They must consist of randomly generated integers in the range 1-6, however, an integer cannot appear more than once in a particular row or column.

Here is the script I am using to generate 5x6 random matrices:

mat=zeros(5,6);

rows=5;
columns=6;
for i=1:rows
  for j=1:columns
      mat(i,j)=round(rand*(high-low)+low);
  end
end
disp(mat)

      

But I don't know how to insert the repetition rule into it.

I'm sure this is a relatively simple problem, but I am very new to MATLAB and have not been able to create something that satisfies these conditions. I would be grateful for any help anyone can give.

+3


source to share


3 answers


Don't try to completely fill the matrix with completely random ints. The likelihood that this is a valid puzzle grid is vanishingly low.

Instead, use the same method as for Sudoku generators - start with an empty matrix and fill in the items one at a time, as constrained by your rules.

If you have several options to choose from, pick one at random.

You can progress something like this (example 4x4 for brevity - valid numbers 1-4)

x x x x
x x x x
x x x x
x x x x

      

Select the first number by rolling the dice: 3.

3 x x x
x x x x
x x x x
x x x x

      

Select the second number from the list of valid numbers: [1, 2, 4].

3 1 x x
x x x x
x x x x
x x x x

      

Select the third number from the list of valid numbers, [1, 4]:



3 1 4 x
x x x x
x x x x
x x x x

      

Etc.

If your "list of valid numbers" is an empty set at any stage of insertion, then your matrix cannot be saved and you may need to start over.

Also a 10x10 matrix with 5 unique integers is clearly not possible - insert some logic to check for this trivial error case.


Edit: Since this is not homework in the traditional sense, but since it was an interesting problem ...

function arena = generate_arena(num_rows, num_cols, num_symbols)
    % Generate an "arena" by repeatedly calling generate_arena_try
    % until it succeeds.
    arena = 0;
    number_of_tries = 0;
    while ~(arena)
        arena = generate_arena_try(num_rows, num_cols, num_symbols);
        number_of_tries = number_of_tries + 1;
    end
    sprintf('Generating this matrix took %i tries.', number_of_tries)
end

function arena = generate_arena_try(num_rows, num_cols, num_symbols)
    % Attempts to generate a num_rows by num_cols matrix of random integers
    % from the range 1:num_symbols, with no symbols repeated in each row or
    % column.
    %
    % returns 0 on failure, or the random matrix if it succeeds.

    arena = zeros(num_rows, num_cols);
    symbols = 1:num_symbols;
    for n = 1:num_rows
        for m = 1:num_cols
           current_row = arena(n,:);
           current_col = arena(:,m);
           % find elements in $symbols that are not in the current row or col
           choices = setdiff ( symbols, [current_row current_col'] );
           if isempty(choices)
               arena = 0;
               return;
           end
           % Pick one of the valid choices at random.
           arena(n,m) = choices(randi(length(choices)));
        end
    end
    return;
end

      

The call and output looks like this:

>> generate_arena(5,6,6)

ans =

Generating this matrix took 5 tries.


ans =

     2     3     6     4     5     1
     6     1     5     3     4     2
     1     5     4     2     6     3
     4     6     2     1     3     5
     3     4     1     5     2     6

      

Don't say that I never gave you anything.;)

+3


source


Try the following:



    m = zeros(5,6);

    for row = 1:5
        flag = 1;
        while(flag)
            flag = 0;
            R = randperm(6);
            for testRow = 1:row
                flag = flag + sum(m(testRow,:) == R);
            end;
            if (~flag)
                m(row,:) = R;
            end;
        end;

    end;

    m

      

+4


source


Here's another way to do it:

Start with a known valid solution, say:

>> A = mod(meshgrid(1:size) - meshgrid(1:size)', size) + 1

A =

     1     2     3     4     5     6
     6     1     2     3     4     5
     5     6     1     2     3     4
     4     5     6     1     2     3
     3     4     5     6     1     2
     2     3     4     5     6     1

      

Then change the rows and columns arbitrarily. You can prove that every swap keeps the "no-repeatts" property on every row and column.

Say you are changing line 1 and line 2. You have not changed the content of the rows, so the "no repeatits in each row" property remains true. Likewise, you haven't changed the content of any of the columns - just the ordering - so the "no repeatits in each column" property also remains true.

This is what I came up with:

function arena = gen_arena_2 (size)
    arena = mod(meshgrid(1:size) - meshgrid(1:size)', size) + 1;
    %repeatedly shuffle rows and columns
    for i = 1:10
        arena = arena(:,randperm(size))'; %shuffle columns and transpose
    end
end

      

Usage example:

>> gen_arena_2(6)

ans =

     3     5     4     2     1     6
     6     2     1     5     4     3
     5     1     6     4     3     2
     4     6     5     3     2     1
     1     3     2     6     5     4
     2     4     3     1     6     5

      

I'm not sure if this is probably "as random" as it is otherwise, but this way is fast and doesn't need any logic to detect failure (because it (provably) always gives the correct result.)

+3


source







All Articles