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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**White_Owl****Member**- Registered: 2010-03-03
- Posts: 104

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

**White_Owl****Member**- Registered: 2010-03-03
- Posts: 104

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

**White_Owl****Member**- Registered: 2010-03-03
- Posts: 104

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

**White_Owl****Member**- Registered: 2010-03-03
- Posts: 104

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

Pages: **1**