Jump to content
  • Advertisement
Sign in to follow this  
infinite dev

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.

If you intended to correct an error in the post then please contact us.

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

Thanks in advance! :)

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!