Generating random 'su doku' type matrices

Question

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

Here is the script I am currently using to generate random 5x6 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 rule about repeats into this.

I'm sure this is a relatively simple problem but I'm very new to MATLAB and haven't been able to generate something that satisfies these conditions. I'd be greatful for any assistance anyone can give.

Answer 1

Don't try to fill the matrix with completely random ints all at once. The likelihood of that being a valid puzzle grid is vanishingly low.

Instead, use the same method as used by Sudoku generators - start with a blank matrix and fill in elements one at a time, as restricted by your rules.

Where you have more than one choice for the entry, pick one of them at random.

You might progress something like this (4x4 example for brevity - allowable numbers 1-4)

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

Pick first number by dice roll: 3.

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

Pick second number from list of allowable numbers: [1, 2, 4].

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

Pick third number from list of allowable numbers, [1, 4]:

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

And so on.

If your "list of allowable numbers" at some insertion step is an empty set, then your matrix can't be salvaged and you may need to start again.

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

---

Edit: Since it's not homework in the traditional sense, and 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

Invocation and output are like:

>> 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 I never gave you nothing. ;)

Answer 2

Here's another way of doing it:

Start off with a known valid solution, say this one:

>> 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 swap rows and columns at random. You can prove that each swap preserves the "no-repeats" property in each row and column.

Say you swap row 1 and row 2. You haven't changed the contents of the rows, so the "no repeats in each row" property remains true. Similarly, you haven't changed the contents of any of the columns - just the ordering - so the "no repeats in each column" property also remains true.

Here 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

Example usage:

>> 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 this is probably "as random" as the other way - but this way is fast and it doesn't need any logic to detect a failure (because it will (provably) always produce a correct result.)

Answer 3

Try this:

    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