# Does such algorithm exists? Puzzle game IA problem

This topic is 2872 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites
http://en.wikipedia.org/wiki/Latin_square

##### Share on other sites
Quote:

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.

##### Share on other sites
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

##### Share on other sites
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]

##### Share on other sites
Quote:
 Original post by xorn = 50: 012341: 340122: 123403: 401234: 23401Grid is generated by rotating the first line two spaces to the right on each following line.n = 60: 0123451: 4501232: 2345013: 501234 <-4: 3450125: 123450Grid 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: 01234561: 56012342: 34560123: 12345604: 60123455: 45601236: 2345601n/2 = 3.5An extra rotation isn't necessary.Another example:0: 012345671: 670123452: 456701233: 234567014: 70123456 <-5: 567012346: 345670127: 12345670n/2 = 4Extra 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.

##### Share on other sites
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.

##### Share on other sites
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?

##### Share on other sites
Quote:
 Original post by infinite devSufficient 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. MullenThis 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.

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

1. 1
Rutin
32
2. 2
3. 3
4. 4
5. 5

• 11
• 13
• 91
• 11
• 10
• ### Forum Statistics

• Total Topics
632973
• Total Posts
3009621
• ### Who's Online (See full list)

There are no registered users currently online

×