Sign in to follow this  
infinite dev

Does such algorithm exists? Puzzle game IA problem

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
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
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
Quote:
Original post by Kevin Dill
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?


Yep.

Sorry if Im being rude, but whats the problem here? The solution is pretty darn straightforward. Row/column swaps will only ever effect the diagonals and never the rows/columns themselves.

Initialize it in the form:

0123456789
1234567890
2345678901
3456789012
4567890123
5678901234
6789012345
7890123456
8901234567
9012345678

then perform a large number of random row and column swaps.

After that, you check to see if the diagonal has any problems. Identify rows/column pairs with these problems. Randomly switch the first one have a problem with. Repeat until all conflicts are resolved.

Since you have such reasonable size square, and this is presumably not needed to be done constantly during game play, it'll work fine.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this