Announcement: Be excellent to each other.


Caravel Forum : Other Boards : Anything : Greco-Latin squares
New Topic New Poll Post Reply
Poster Message
disoriented
Level: Smitemaster
Rank Points: 1201
Registered: 08-07-2007
IP: Logged
icon Greco-Latin squares (0)  
Iím trying to construct a fairly efficient algorithm for the following problem: Given some initial entries that make the solution unique, complete the entries of a Greco-Latin Square.

For example, hereís a partial solution for an order 3 square:
1? ?? ?a
?? 1? ?c
2? 3c ??

And the solution:
1c 2b 3a
3b 1a 2c
2a 3c 1b

My algorithm uses a backtracking approach, populating all the unfilled entries of one latin square (being sure not to dupe entries in a row or column) and then trying to place the unfilled entries in the other latin square, backing up if there's a dupe in the row/col or if a pairing was duplicated. Each number or letterís ďcurrently usedĒ pairings are kept in a Set structure for that number/letter.

My algorithm works, but it runs too slowly to be practical for squares above order 4 or 5. I need it to run efficiently on at least order 7 or 8 squares.
Any suggestions from this smart group? Iím not a mathematician so please bear with me. :)


____________________________
34th Skywatcher
12-24-2014 at 11:09 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
TripleM
Level: Smitemaster
Rank Points: 1361
Registered: 02-05-2003
IP: Logged
icon Re: Greco-Latin squares (+2)  
Backtracking is definitely the way to go, but you'll want to optimise it so that rather than processing things in a specific order (one latin square first, then the other), you process them in a way that narrows down wrong paths as soon as possible.

There are two types of constraints you can use:

"There is an x in column(/row) y" [2n^2 constraints]
"The cell at (x,y) must be filled" [n^2 constraints]

For each constraint, you can count how many ways to place a value that satisfies this constraint (without breaking the rules of the grid).

At each stage of the recursion, you should loop over the 3n^2 constraints, and figure out which one leads to the minimum number of possibilities. Just consider that constraint, and try each one in turn. When that constraint has 0 possibilities, you backtrack.

--

There is a clever way of implementing this called 'Dancing Links' - not only does this allow you to narrow down the best possibility at any stage, but also stores things in a single data structure that allows very quick recursion + backtracking without needing to copy data back and forward all of the time, so works many constant factors faster than a straightforward approach.

It's quite complex to code but when done correctly it solves Sudokus instantly, and should perform similarly in this case for the sizes you're describing.

http://garethrees.org/2007/06/10/zendoku-generation/#section-4 has a good write up of how it works.

[Last edited by TripleM at 12-25-2014 02:52 AM]
12-25-2014 at 02:08 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
slimm tom
Level: Smitemaster
Avatar
Rank Points: 1092
Registered: 10-14-2006
IP: Logged
icon Re: Greco-Latin squares (0)  
quote:
TripleM wrote:
http://garethrees.org/2007/06/10/zendoku-generation/#section-4 has a good write up of how it works.

That's a very interesting read! I'm studying algorithms as part of my CS Bachelor and I love logic puzzles (not so uncommon on this forum I guess), so I'm almost tempted to code up the algorithm. :)
12-25-2014 at 09:10 PM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1201
Registered: 08-07-2007
IP: Logged
icon Re: Greco-Latin squares (0)  
Yes, definitely plan on studying more about Knuth's Algorithm X and modeling problems as an Exact Cover problem! Thanks for posting TripleM!
(P.S. This was discovered as recently as 2000?!)

____________________________
34th Skywatcher

[Last edited by disoriented at 12-26-2014 04:36 AM]
12-25-2014 at 11:20 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
TripleM
Level: Smitemaster
Rank Points: 1361
Registered: 02-05-2003
IP: Logged
icon Re: Greco-Latin squares (0)  
Do you have an example 7x7 or 8x8 grid to solve? I have a version of DLX coded up from my ICPC days so I could see whether it does indeed work fast or not.

[Last edited by TripleM at 12-26-2014 08:53 PM]
12-26-2014 at 08:52 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1201
Registered: 08-07-2007
IP: Logged
icon Re: Greco-Latin squares (0)  
quote:
TripleM wrote:
Do you have an example 7x7 or 8x8 grid to solve? I have a version of DLX coded up from my ICPC days so I could see whether it does indeed work fast or not.


I do. I can attach it below.

I found an example implementation of DLX on the web, although it's for regular Sudoku. Right now I'm trying to adapt the precomputed 0-1 matrix for use with Greco-Latin squares. I need to remove the constraint columns dealing with "Sudoku 3x3 blocks" and add columns for the pairing constraints. Not sure how to do that part yet.

____________________________
34th Skywatcher

[Last edited by disoriented at 12-26-2014 09:36 PM]
12-26-2014 at 09:31 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1201
Registered: 08-07-2007
IP: Logged
icon Re: Greco-Latin squares (0)  
Sample problem:

Letters Latin Square (0,0) to (6,6):

?E?????
?????FC
???????
?????C?
??A??D?
?G?????
?C??E??


Numbers Latin Square (0,0) to (6,6):

??53???
????2??
??????5
?762???
7?1????
?37????
?????6?


____________________________
34th Skywatcher

[Last edited by disoriented at 12-26-2014 09:40 PM]
12-26-2014 at 09:39 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
TripleM
Level: Smitemaster
Rank Points: 1361
Registered: 02-05-2003
IP: Logged

File: DLX.java (4.2 KB)
Downloaded 7 times.
License: Public Domain
icon Re: Greco-Latin squares (0)  
So the downside of this approach is that your rows have to be of the form "Place (a,b) at (x,y)", compared with the logic-based approach of filling in a single value at a time.

I feel like there must be some way to improve that, but still, it took 8 seconds to come up with a solution, and another 14 or so to prove it was unique:
FEDCBGA
ADBEGFC
CAEDFBG
EBGADCF
GFABCDE
DGCFAEB
BCFGEAD
2653147
3145276
1427635
4762351
7516423
6374512
5231764


[Last edited by TripleM at 12-26-2014 10:28 PM]
12-26-2014 at 10:11 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1201
Registered: 08-07-2007
IP: Logged
icon Re: Greco-Latin squares (0)  
Wow you're quick! I have more programming challenges that may benefit from this Exact Cover modeling, if you are interested.

____________________________
34th Skywatcher
12-26-2014 at 10:18 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
New Topic New Poll Post Reply
Caravel Forum : Other Boards : Anything : Greco-Latin squares
Surf To:


Forum Rules:
Can I post a new topic? No
Can I reply? No
Can I read? Yes
HTML Enabled? No
UBBC Enabled? Yes
Words Filter Enable? No

Contact Us | CaravelGames.com

Powered by: tForum tForumHacks Edition b0.98.8
Originally created by Toan Huynh (Copyright © 2000)
Enhanced by the tForumHacks team and the Caravel team.