Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫  π  -¹ ² ³ °

You are not logged in.

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

White_Owl
Member
Registered: 2010-03-03
Posts: 106

### Random Latin Square generation

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

``````1234
2341
3412
4321``````

are obviously no good.

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

Offline

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

White_Owl
Member
Registered: 2010-03-03
Posts: 106

### Re: Random Latin Square generation

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?

Offline

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

White_Owl
Member
Registered: 2010-03-03
Posts: 106

### Re: Random Latin Square generation

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?

Offline

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

White_Owl
Member
Registered: 2010-03-03
Posts: 106

### Re: Random Latin Square generation

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...

Offline