Question Travelling Salesman Problem Implementation

Hi,

I'm creating a jigsaw solver, I've got the piece identification all done, including calculating a match likeliness for each side of the pieces to other sides of other pieces. The data structure for a piece is as follows:

Code (CSharp):

1. Piece
2.       -> Side (north)
3.               -> Match[] (Matching Side and match likeliness)
4.       -> Side (east)
5.               -> Match[]
6.       -> Side (south)
7.               -> Match[]
8.       -> Side (west)
9.               -> Match[]

Where Match could be a class as follows:

Code (CSharp):

1. class Match
2. {
3.     Side matchingSide;
4.     double matchLikeliness;
5. }

Using the pieces of the jigsaw, and the matches, we can apply the Travelling Salesman Problem to calculate a "best fit" for all the pieces at once based on the precalculated match likeliness values.

My problem is implementation of an algorithm to create this behaviour. The final goal is to create a tree that represents all possible (pruned) combinations for solving the jigsaw.

To simplify the process, I'm trying to only consider the edge pieces to start with so that we can consider it to be just one long line in terms of the tree structure.

I suppose my issue is that the implementation I would need relies on having two sides to each piece, so it's not just as simple as having a "Node" with a "distance", since I need more information than that. I need something more like this:


Where each node is a Piece with two separate (known) sides, and a "distance" between each. The goal is to create a path for every combination of the pieces (with pruning for performance). But I'm really struggling to implement this in code.

More info:
Piece:

Code (CSharp):

1. class Piece
2. {
3.     // Unordered, Side holds directional info
4.     List<Side> sides;
5. }

Side:

Code (CSharp):

1. class Side
2. {
3.     // The direction this side is facing
4.     Direction dir;
5.     // where Side is the connecting side and the double is the match likeliness
6.     Dictionary<Side, double> matches;
7. }

How would you go about implementing this? Feel free to change the structure of the Piece and Side classes if it proves favourable. I'd greatly appreciate any help with this.

Cheers!

 

The task is very difficult for me, but interesting.
Can the pieces rotate? Is the width and height of the completed puzzle known?

Do all the pieces always belong to the same completed puzzle? Or is it necessary to assemble the largest possible rectangle from an unknown set of pieces?

 

Yeah, I'm having a hard time with it too.

Pieces can rotate, yes, direction is an arbitrary value simply used for relative directions for each piece.
Width and height unknown.
All pieces always belong to the same completed puzzle. The set of pieces will always contain the correct number of pieces to solve the puzzle.

 

Sounds like a job for recursion. Specifically a recursive data structure. Which as you stated already is going to be a tree structure. How many pieces are you talking here btw? Cause I could see this blowing up real real fast. I guess pruning could help with that but I'm not sure what heuristic you'd actually use in this case to decide you've 'probably gone too deep in the wrong direction'.

EDIT: Ha, just re-read the first post. You already DO have a recursive data structure. lol

 

So yeah, actually I'm gonna go with my original assessment. You don't have a way for a side to reference back to a piece. If you did it would 'simply' be a matter of traversing from any given piece through all possibles sides of all possible remaining pieces and then finding the best score. Of course I say 'simply' cause you know, that's the definition of the salesman problem. Easy on paper. Not so easy when combinations start to explode.

 

Yeah the magnitude of the tree could end up being rather large, but there are ways to very effectively reduce this number.

Consider this: A piece may only match with another piece if piece 1 has a blank and piece 2 has a tab, or vice versa, so already we're effectively halving the number of comparisons that we need to do. Equally, for the edge pieces, each successive piece must have an edge in the same direction as the previous edge piece, I.E. If a tab and a blank of a piece fit together but adjacent sides don't share an edge (where applicable), these pieces cannot be a match, this further prunes the data and is especially useful when the number of centre pieces surpasses the number of edge pieces. There are other methods, such as pruning "bad" fits, where the shape of an edge or the colours along it aren't relatively close; these results are also removed from the solving process.

What we end up with is a recursive data structure where Pieces hold data about their sides, and the Sides hold data about all matches that they can have. In essence, the information is already there, it's available, ready to use, I just don't know how to use it! I don't know how to design an algorithm that will work through this problem.

The jigsaws can range, but my test jigsaw has 12 pieces, but it will scale to 24 when further testing is conducted.

The Sides themselves do hold a reference to the piece their attached to if that helps.

If your point is that the travelling salesman problem is not the correct approach, do you have an alternative that would work better here?

 

Honestly it sounds like you've done all the hard work. At this point it's should just be a recursive walk through the data structures where you apply the filters you mentioned above. Then compare the 'total distance' for each tree you've built to see which is the best.

So here's a suggestion based on my own similar problem recently. I had to write a knapsack solver. I know the theory and I generally know what to do but it's just an annoying and frankly boring task to write the code for that algorithm since it mostly just relies on not mistyping stuff more than anything. So what do we do when we are faced with a boring repetitive problem? We make the computers do it. Have you considered stuffing your data structures into "the ol' chatbot 2000" and seeing what it pops back out?

 

Just for the heck of it I stuffed the first half of your first post in and more-or-less got the answer 'do it a recursive walk'. So I asked it to pop some code out of that process.

Code (CSharp):

1. using System;
2. using System.Collections.Generic;
3.  
4. class JigsawPuzzleSolver
5. {
6.     class Piece
7.     {
8.         public int id;
9.         public Dictionary<Direction, List<Match>> matches;
10.  
11.         public Piece(int id)
12.         {
13.             this.id = id;
14.             this.matches = new Dictionary<Direction, List<Match>>();
15.             foreach (Direction dir in Enum.GetValues(typeof(Direction)))
16.             {
17.                 this.matches[dir] = new List<Match>();
18.             }
19.         }
20.     }
21.  
22.     enum Direction { North, East, South, West }
23.  
24.     class Match
25.     {
26.         public Piece piece;
27.         public Direction dir;
28.         public double likeliness;
29.  
30.         public Match(Piece piece, Direction dir, double likeliness)
31.         {
32.             this.piece = piece;
33.             this.dir = dir;
34.             this.likeliness = likeliness;
35.         }
36.     }
37.  
38.     static double GetSolutionCost(List<Piece> solution)
39.     {
40.         double cost = 0;
41.         for (int i = 0; i < solution.Count - 1; i++)
42.         {
43.             Piece p1 = solution[i];
44.             Piece p2 = solution[i + 1];
45.             cost += p1.matches[GetOppositeDirection(p2.matches[p1.id].dir)][p2.id].likeliness;
46.         }
47.         return cost;
48.     }
49.  
50.     static Direction GetOppositeDirection(Direction dir)
51.     {
52.         switch (dir)
53.         {
54.             case Direction.North: return Direction.South;
55.             case Direction.East: return Direction.West;
56.             case Direction.South: return Direction.North;
57.             case Direction.West: return Direction.East;
58.             default: throw new ArgumentException("Invalid direction: " + dir);
59.         }
60.     }
61.  
62.     static List<Piece> SolveJigsawPuzzle(List<Piece> pieces)
63.     {
64.         List<Piece> bestSolution = null;
65.         double bestCost = double.PositiveInfinity;
66.  
67.         Stack<List<Piece>> stack = new Stack<List<Piece>>();
68.         stack.Push(new List<Piece> { pieces[0] });
69.  
70.         while (stack.Count > 0)
71.         {
72.             List<Piece> solution = stack.Pop();
73.             double cost = GetSolutionCost(solution);
74.             if (cost >= bestCost) continue;
75.             if (solution.Count == pieces.Count)
76.             {
77.                 bestSolution = solution;
78.                 bestCost = cost;
79.                 continue;
80.             }
81.             Piece lastPiece = solution[solution.Count - 1];
82.             foreach (Match match in lastPiece.matches.Values[0])
83.             {
84.                 if (solution.Contains(match.piece)) continue;
85.                 List<Piece> newSolution = new List<Piece>(solution);
86.                 newSolution.Add(match.piece);
87.                 stack.Push(newSolution);
88.             }
89.         }
90.  
91.         return bestSolution;
92.     }
93. }

I haven't verified the validity of any of this but there ya go. A jumping board to start from.

 

I haven't, but I will I totally forgot about that. I'll just keep shoving in prompts until it knows my exact problem.

That's quite interesting, that's almost exactly how I have it set up now, so that's good! But it doesn't do much of the branch and bounding like what I need, but I'm sure with a few extra prompts I can get it to start doing that.

I'll let you know if I have any luck with it, cheers!

 

Super awesome update on this, I managed to get it working, I have an algorithm that compares every combination of matches, and prunes the data where necessary to get perfect results every time (whoop!). Here in lies the issue though, my pruning is not good enough, I really don't think there's anything I can do in terms of pre-processing to optimise the result. For reference, here are the current results and times:

Code (CSharp):

1. 4X3 Puzzle: 83 matches, <10,000 iterations, takes about 3 seconds
2. 4X4 Puzzle: 177 matches, <10,000 iterations, takes about 5 seconds
3. 4X5 Puzzle: 355 matches, <3,700,000 iterations, takes about 45 MINUTES
4. 4X6 Puzzle: 552 matches, unknown iterations, takes too long for my patience

So of course the 4X3 and 4X4 puzzles are great, plenty fast enough, but things start to go down hill, VERY fast. It makes perfect sense, the more matches, the exponentially more processing the solving algorithm has to do. The matches are very much optimised though, I'm not sure there's much else I could do to get these values down. 552 matches for a 4X6 puzzle is, to be honest, pretty damn good.
I should mention, these values are actually probably a bit lower than shown because pruning is done pre-solve to only use edge pieces, so you could expect those values to be about 70% of what they actually are.

To keep memory usage to a minimum, I'm using a PriorityQueue (not the C# implementation, my .NET version is too far back for this) to store the 'queued' solution attempts. It simply uses a SortedDictionary to order the data, with a Descending Comparer applied to it that sorts by "average match likeliness of all pieces used * number of pieces used".

The PriorityQueue usually has at most about 30 items in it.

Current pruning that exists:
- Checking only edge pieces to create the edge
- If the first side is longer than half of the pieces, it can't be a solution
- If the second side + the first side is greater than half of the pieces, it can't be a solution
- If the third side doesn't match the first side in length, it can't be a solution
- If we don't have a length for the first or second side by the time half of the pieces are used, it can't be a solution

Can you think of any other optimisations that can be done? Including changes to the PriorityQueue class, which, given the amount of items in it, I doubt is the problem.

Cheers!

 

Thanks for your response. I have something like this working, but I'm facing a problem with the O(n) time complexity. Small puzzles work well, 4x3 for example take around 3 seconds to solve. Larger puzzles like 4x5 are taking upwards of 45 minutes. Do you have any advice for this problem?

 

You're actually dealing with O(n!) (big oh sub n-factorial). That's the big number problem you have. Brute force can be a brute.

As with any graph search that operates on a nontrivial dataset, your wins are likely to come from being able to implement a choice-reducing heuristic, just like the way AStar uses the "estimated path to goal" heuristic to dramatically improve search times by prioritizing what the heuristic says is a "better path" first.

In your problem space (ad-hoc puzzle faces matching each other), the only thing I can think of is some kind of signature quantifying problem to collapse all the possible faces into a smaller number of distinct different buckets.

For example, if you simply separated matching faces purely based on a key generated from the apparent gap of the neck of the puzzle tab/blank you would have reduced the possible choices. If you broke the piece faces into small, medium, large tab sizes and then only considered small->small and medium->medium and large->large tabs you would reduce your search space.

Of course due to quantization and computer vision you might miss a piece that is right on the edge of medium/large: the tab gets classified as large, the blank gets classified as medium, so they never get considered.

This can be countered by putting tabs/blanks that are near a boundary into BOTH buckets, which costs you additional search time.

If you further analyze the pieces and made a key based on the tab/blank width AND the tab/blank depth, you will have increased the possible buckets, but each bucket would get even smaller.

That's really the only way I can think to reduce this brute force.