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

You are not logged in.

|
Options

White_Owl
2011-04-28 04:24:26

And the third approach which always work:

#### Code:

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

White_Owl
2011-04-28 04:14:13

Here is another approach:

#### Code:

```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-28 04:00:39

Here is one promising algorithm which does not work:

#### Code:

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

#### Code:

```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-28 03:53:11

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

#### Code:

```1234
2341
3412
4321```

are obviously no good.

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