Hi all! :)
I'm developing a puzzle game and i had a problem.
- You have a "n x n" board where n=5,6,7,8,9 (different values reflects different game levels)
- There are "n" different colors to fill the board

The board must follow these rules:
- Each color must exists only once in each row, column and diagonal (the two main diagonals)

I haven't found yet an IA algorithm that creates a complete board with such rules starting from a blank one.
Accorging to you, is it possible to create a full board that follows all of these rules?

Examples (to be clearer):
5x5 board showing each rule separately

0 1 2 3 4
x x x x x
x x x x x
x x x x x
x x x x x

0 x x x x
1 x x x x
2 x x x x
3 x x x x
4 x x x x

0 x x x x
x 1 x x x
x x 2 x x
x x x 3 x
x x x x 4

x x x x 0
x x x 1 x
x x 2 x x
x 3 x x x
4 x x x x

Thanks in advance! :)

http://en.wikipedia.org/wiki/Latin_square

Quote: Original post by emptyhead
http://en.wikipedia.org/wiki/Latin_square

I'm reading the article, but latin squares doesn't cover the diagonal constraints that i have. Did you post it to say that there's no solution for those diagonal rules?
I experimentally tried to solve a 5x5 board with an algorithm that i've created and it works, but no good solution for boards of more than 5 cells.
Now i'm trying to solve boards of 6,7,8 and 9 cells with a modified version of that algorithm, but i'm really confused.

n = 5

0: 01234
1: 34012
2: 12340
3: 40123
4: 23401

Grid is generated by rotating the first line two spaces to the right on each following line.

n = 6

0: 012345
1: 450123
2: 234501
3: 501234 <-
4: 345012
5: 123450

Grid is generated by using the same algorithm but line n/2 is rotated one extra space. Line n/2 always needs an extra rotation, where n/2 isn't integer this operation isn't necessary. An example:

0: 0123456
1: 5601234
2: 3456012
3: 1234560
4: 6012345
5: 4560123
6: 2345601

n/2 = 3.5
An extra rotation isn't necessary.
Another example:

0: 01234567
1: 67012345
2: 45670123
3: 23456701
4: 70123456 <-
5: 56701234
6: 34567012
7: 12345670

n/2 = 4
Extra rotation necessary on line 4

I already tried it and it doesn't works.
Pay attention that your even grids (mine too) aren't correct, because in one of the main diagonals (top-right to bottom-left) some numbers are repeating.
It only works on 5x5 and 7x7 grids.
I thought that it was only working with odd grids, but i discovered that it doesn't with 9x9.
Some suggestions?

EDIT:
I made a search and discovered what's following.

The kind of latin squares that i've described are called "diagonal latin squares" (or dls), or "double diagonal latin squares" (or ddls).
This kind of latin squares follow this theorem:

Sufficient condition for a diagonal latin square of order n: if n is odd and not a multiple of 3 then there is a diagonal latin square of order n.

Source: Discrete mathematics using Latin squares - Charles F. Laywine,Gary L. Mullen

This deletes any doubt about the creation of those grids!
Now it's obvious that I cannot create a diagonal latin square of order 6,8,9!
In the range of n that I require, i can only generate a 5x5 and 7x7.
Thanks to all!

[Edited by - infinite dev on December 8, 2010 5:51:59 AM]

Quote: Original post by xor
n = 5

0: 01234
1: 34012
2: 12340
3: 40123
4: 23401

Grid is generated by rotating the first line two spaces to the right on each following line.

n = 6

0: 012345
1: 450123
2: 234501
3: 501234 <-
4: 345012
5: 123450

Grid is generated by using the same algorithm but line n/2 is rotated one extra space. Line n/2 always needs an extra rotation, where n/2 isn't integer this operation isn't necessary. An example:

0: 0123456
1: 5601234
2: 3456012
3: 1234560
4: 6012345
5: 4560123
6: 2345601

n/2 = 3.5
An extra rotation isn't necessary.
Another example:

0: 01234567
1: 67012345
2: 45670123
3: 23456701
4: 70123456 <-
5: 56701234
6: 34567012
7: 12345670

n/2 = 4
Extra rotation necessary on line 4

These don't work. They don't all conform to the restriction the OP stated.

For example, in your n=8 (last one), there are two 0's in one diagonal and two 7's in the other diagonal.

In the n=6 there are two 0's or two 5's in the diagonals.

You're both right, I was under the impression the diagonals didn't need to be sorted that way. It's in the OP though, I missed it.

From here, you should be able to swap rows without losing the horizontal and vertical correctness, right? Can you follow the above algorithm by looking for row swaps that will fix the diagonals?

Quote: Original post by infinite dev


Sufficient condition for a diagonal latin square of order n: if n is odd and not a multiple of 3 then there is a diagonal latin square of order n.

Source: Discrete mathematics using Latin squares - Charles F. Laywine,Gary L. Mullen

This deletes any doubt about the creation of those grids!
Now it's obvious that I cannot create a diagonal latin square of order 6,8,9!
In the range of n that I require, i can only generate a 5x5 and 7x7.
Thanks to all!

Actually that doesn't say that. If if were a necessary condition it would, but you that theorem doesn't say you can't have a 6,8,9 latin square, just that odds and not a multiple of 3 definitely have latin squares. It doesn't say that other numbers don't, just that some do.

Yes, you're right!
But i'm not finding a diagonal latin square outside of the range described by the theorem above ... becoming crazy!