I have been trying to tackle this problem, but no solution comes to mind mainly bc I'm an idiot. I want to write a jigsaw-puzzle solver, being the rules of the puzzle the following:
1. Each piece has four sides. In order to describe a piece, we list the shape of the top, right, down, left sides. Each possible shape is given by a number. Pieces with equal numbers are meant to be able to fit together, and the only exception is the number 0, which describes an edge. A piece with a 0 will be on the edge of the puzzle and a piece with two 0's will be in a corner. Therefore, an example for a piece could be: 0 3 2 1. This means the top side of the piece is an edge, and then we have a type-3 edge on the right side, a type-2 edge on the down side, and a type-1 edge on the left side.
2. The pieces are all specified together, along with the dimensions of the puzzle. This means we have a list of pieces specified as a list of four digit numbers. If the puzzle is a 3x3 puzzle, we will have a list of 9 pieces.
3. The pieces can be rotated, but not flipped. That is, a piece represented by 1 2 0 4 will be exactly the same piece as a piece represented by 4 1 2 0 (we just applied a 90 degree clockwise rotation).
4. Each piece can be used only one time and of course the pieces corresponding to edges will need to be on the edge.
I can't think of a way to solve this algorithmically. I think starting from the edges could be a good start, but I don't know how to proceed. I think backtracking could be used, but I don't know how. I am not looking for a finished code, of course, I just need some help.
1. Each piece has four sides. In order to describe a piece, we list the shape of the top, right, down, left sides. Each possible shape is given by a number. Pieces with equal numbers are meant to be able to fit together, and the only exception is the number 0, which describes an edge. A piece with a 0 will be on the edge of the puzzle and a piece with two 0's will be in a corner. Therefore, an example for a piece could be: 0 3 2 1. This means the top side of the piece is an edge, and then we have a type-3 edge on the right side, a type-2 edge on the down side, and a type-1 edge on the left side.
2. The pieces are all specified together, along with the dimensions of the puzzle. This means we have a list of pieces specified as a list of four digit numbers. If the puzzle is a 3x3 puzzle, we will have a list of 9 pieces.
3. The pieces can be rotated, but not flipped. That is, a piece represented by 1 2 0 4 will be exactly the same piece as a piece represented by 4 1 2 0 (we just applied a 90 degree clockwise rotation).
4. Each piece can be used only one time and of course the pieces corresponding to edges will need to be on the edge.
I can't think of a way to solve this algorithmically. I think starting from the edges could be a good start, but I don't know how to proceed. I think backtracking could be used, but I don't know how. I am not looking for a finished code, of course, I just need some help.
