You are not logged in.
- Index
- » Coder's Corner
- » Random Latin Square generation
Post a reply
Topic review (newest first)
- 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 NumberProblem 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?