Need some help with data structure [C#]

[Zalosath]

Hi,

 

I'm creating a jigsaw solver and I've run into a bit of a wall with a data structure when it comes to matching the pieces together. 

 

Each piece has an instance of the Piece class, the Piece class stores a List of Sides which are just the four sides of the piece.

class Piece
{
    List<Side> sides = new List<Side>();
}

A Side is just a representation of a physical side, it contains a direction and a type, the direction is the local direction taken from the side of the piece, and the type is whether it's a male or female connection. 

class Side
{
    Direction direction;
    SideType type;
}

 

Now, I need some way of storing the matches between pieces, the intuitive approach suggests to convert the sides List in Piece to a Dictionary that holds <Side, Side>, where the first side is the side of the current piece, and the second side is the side of the piece its attached to, but the system needs to support back tracking, i.e. remember previous match attempts in-case the matching algorithm falls apart half way through. 

 

Something that I've tried is a Wrapper class that just holds a Piece and its side, along with a List of all sides it can connect to, and an index to declare which one it's currently trying to connect with.

class PieceMatch
{
    Piece firstPiece;
    Side firstSide;
    List<Side> matches; // All of the matches that are possible for firstSide
    int currentMatchIndex = 0; // The current index to use for the matches List
}

But this just makes everything too complicated and I can't wrap my head around how to effectively use it.

 

Even if you had to start from scratch, how would you arrange everything? A Piece must contain 4 sides, a Side must have a direction and a type, and a match must support back tracking of some description.

 

Let me know if you need any more information, any ideas?

Cheers!

[evievi]

So I’m not a C# guy, more of a Java guy, but have some thoughts.

 

This does remind me of a parallel NQueens solution counter I wrote in Java a while back. I think what I did for that was very similar to what you had, where I basically wrote a class for a board that kept track of the queens and then wrote some helper functions to check a board to see if it was possible to place a queen at a specific board space. The way that my code worked was that I iterated through each column and then forked at each row of the column if it was possible to put a queen there. It was pretty memory intensive, but then I passed a new copy of the board class containing the new queen into the fork and went from there. I returned 0 if I ever reached a “hopeless case” and returned 1 if I was able to get to the end of the board through my forks.

 

For your problem, I think you’d do the same thing, just instead of trying one queen, you’d try n puzzle pieces that can fit on the compatible edges, but the same rough pseudo code applies. If you don’t need to do parallelism, don’t worry about “forking” just write a for loop and it will be a sequential implementation of the same thing.

 

I think this would solve your backtracking issue, hope this helps!

[Zalosath]

4 minutes ago, evievi said:

So I’m not a C# guy, more of a Java guy, but have some thoughts.

 

This does remind me of a parallel NQueens solution counter I wrote in Java a while back. I think what I did for that was very similar to what you had, where I basically wrote a class for a board that kept track of the queens and then wrote some helper functions to check a board to see if it was possible to place a queen at a specific board space. The way that my code worked was that I iterated through each column and then forked at each row of the column if it was possible to put a queen there. It was pretty memory intensive, but then I passed a new copy of the board class containing the new queen into the fork and went from there. I returned 0 if I ever reached a “hopeless case” and returned 1 if I was able to get to the end of the board through my forks.

 

For your problem, I think you’d do the same thing, just instead of trying one queen, you’d try n puzzle pieces that can fit on the compatible edges, but the same rough pseudo code applies. If you don’t need to do parallelism, don’t worry about “forking” just write a for loop and it will be a sequential implementation of the same thing.

 

I think this would solve your backtracking issue, hope this helps!

Interesting idea, could definitely work. My main issue right now is how to store the match data, would you be happy to share your Java code? I could perhaps use it for inspiration. No worries if not!

Cheers!

[evievi]

2 minutes ago, Zalosath said:

Interesting idea, could definitely work. My main issue right now is how to store the match data, would you be happy to share your Java code? I could perhaps use it for inspiration. No worries if not!

Cheers!

 

I really wish I could but it was for a university class. Takedown requests and legal stuff have been known to happen to people publishing code that references the proprietary modules

 

I can give you some rough pseudocode (forgive me am typing on a tablet and my code is from memory):

 

//Assume utility functions

getCandidateRows(int c) // returns possible safe rows for a columns

IsSafe(int r, int c) //returns true if you can place a queen there

 

Int nQueensKernel(Board board, int row){

 

//Yay we found a solution

if(row == Board.n){

Return 1;

}

 

List<Integer> candidates = getCandidateColumnsInRow()

 

//we have locked ourselves into an unsolvable board

if(candidates.length == 0){

Return 0;

}

// keep track of a sum. If done synchronously this works, but parallel requires you to finish all of the tasks and take the scan of their result.

Int sum = 0;

 

//Using synchronous for loop as parallel library is proprietary

for(int i : candidates){

// Create a copy (don’t mutate original board) and up the row to keep advancing

sum += NQueensKernel( board.copy().addQueen(row, i), row+1 );

 

}

 

Return sum;

 

Best of luck! Hope you figure it out

 

 

 

 

 

 

 

 

[Franck]

a match between pieces include rotation of both pieces so you need a object to represent that and how would you represent 3 pieces together ?

 

The trick is to use a layout. If you match 2 pieces in a real physical puzzle what do you do with it ? lay it down on the table somewhere. This set of 2-3-5-60 puzzle pieces form an irregular grid. That being said you simply need to store the piece rotation in a random grid cell and push it's sides to the cell sides then lay down the other pieces. All cell side facing a cell with a piece in it is not usable for match detection. Once you match 2 cells in 2 different grids you have to check if either grid would also fit in the other grid so making sure no cell are filled that would need to be taken, and all cells that end up touching also matches side wise.

[Zalosath]

On 3/6/2023 at 11:13 PM, evievi said:

-snip-

 

On 3/7/2023 at 11:52 AM, Franck said:

-snip

 

19 hours ago, Sakuriru said:

 

-snip-

Thanks for all the replies I greatly appreciate the help.

 

The problem I'm facing is converting the steps that I have in my head into code, which isn't usually a problem for me! 

 

The approach that I'm currently trying to get working is as follows:

Take a corner piece, any, and rotate it so that WEST and NORTH are edges:

 

 

And then computing the best match for the EAST side of the piece, when it finds a good match, the current piece is set to that new piece and the process repeats. When we get to a corner piece, we rotate the entire row found, like the following:

 

And then the process is repeated with the most recently added piece, until we eventually end up with the borders of the piece. From there it's a case of filling in the blanks and it should be a much simpler process. Currently, I've got one iteration working fine, I now just need to extend the edge finding method to consider many more possibilities than just one, ensuring the best one is picked each time.

 

If you have any insight on the best ways to do that, I'd appreciate that too! Cheers

[Franck]

36 minutes ago, Zalosath said:

If you have any insight on the best ways to do that, I'd appreciate that too! Cheers

You need to define your problem properly. What you are doing only work if  all the piece are completely unique and in perfect grid with also disregard for color matching.

[Zalosath]

Just now, Franck said:

You need to define your problem properly. What you are doing only work if  all the piece are completely unique and in perfect grid with also disregard for color matching.

My actual problem as of now is creating multiple versions of the border and picking the best one, since creating just one border will not always create ideal results based on inaccuracies in the match process. I'm looking into methods of doing this, such as the travelling salesman problem which evaluates the whole set of pieces at once based on how well the pieces fit, but implementation of the different ways of matching the pieces is the current trouble. I can't figure out how to create a loop that'll generate a unique layout each time. But perhaps it's too specific of a problem for generalised solutions, I'll keep working on it and see what I can do.

[Franck]

17 hours ago, Zalosath said:

My actual problem as of now is creating multiple versions of the border and picking the best one

Like i said, the solution path you are taking is only working for perfectly unique pieces and if that's the case any border will work you don't need the best one. If it doesn't work it mean your puzzle doesn't have completely unique pieces and therefore your current solution is not all the correct way to go at it.

[Zalosath]

2 hours ago, Franck said:

Like i said, the solution path you are taking is only working for perfectly unique pieces and if that's the case any border will work you don't need the best one. If it doesn't work it mean your puzzle doesn't have completely unique pieces and therefore your current solution is not all the correct way to go at it.

The pieces are unique in terms of colour, but not always shape. The matching algorithm can still make errors because when extracting the contours of the piece (I'm using computer vision), there is still room for error, the sides are not always perfect for that reason. The colours remain relatively even throughout, but changes in lighting can and will effect the pieces, equally distorting the matches.

 

Hence, it's important that I create multiple versions of a border to see which one is actually the correct one, calculating a score based on how well ALL of the pieces fit together, rather than just two pieces.