Random Latin Square generation

White_Owl · 2011-04-27 05:53:11

For the purpose of number puzzles like Sudoku or KenKen first we need to generate a randomized Latin Square.
Squares like this:

are obviously no good.

So the question is: How to generate a randomized Latin Square?

White_Owl · 2011-04-27 06:00:39

Here is one promising algorithm which does not work:

for each Number
   for each Row
        take a random Column with an empty cell in the Row
        check that all cells above it do not contain Number
        if this column already occupied by this Number - find a new Column and repeat.
        once non-occupied row is found write Number in the cell
   next Row
next Number

Problem here is that in some cases this algorithm can stuck:
Working with 4x4 board:
For number 1: put it in 1, 2, 3, 4 positions in rows
For number 2: put it in 2, 3, 1, .... No where to put 2 in fourth row

12..
.12.
2.1.
...1

Any ideas why this promising algorithm fails and how to improve it to prevent blocks like this?

White_Owl · 2011-04-27 06:14:13

Here is another approach:

for each Row
   make a String of all numbers
   make a random permutation of the String
   attempt to apply the randomized String to a Row
   if there is a conflict with some of previously filled rows - make a new permutation and repeat applying process
next Row

It looks like this algorithm works always, for example if we filled two first rows with 1234 and 4123, then there is no way to put in the third row a string with "2.1." pattern.

The only problem here is that I cannot find a more or less rigorous proof that this algorithm will always work.
Also, it is a little time consuming, especially on the last rows there can be a lot of tries to find a permutation which would work. And even on a 9x9 grid and a fast computer I can see a delay. Any ideas on how to speed up the search for a next permutation which would satisfy the rules of Latin Square?

White_Owl · 2011-04-27 06:24:26

And the third approach which always work:

take a Latin Square
randomly exchange two columns or two rows in it
repeat several times

This would generate almost random Latin Square, but it would be isomorphic to the original, so not a really random.
And it is also not a very fast procedure...

Math Is Fun Forum

#1 2011-04-27 05:53:11

Random Latin Square generation

#2 2011-04-27 06:00:39

Re: Random Latin Square generation

#3 2011-04-27 06:14:13

Re: Random Latin Square generation

#4 2011-04-27 06:24:26

Re: Random Latin Square generation

Board footer