[7.6] Jigsaw puzzle

1. Example

every piece has four edges with different type: inner, outer or flat
every piece can rotate , we called orientation here
        _ _
  ___|   |___
 |                |
 |                |
 |________|

     
  ___     ___
 |      |__|     |
 |                |
 |________|


   _______
 |                |
 |                |
 |________|

2. Implementation

//
//We grounded the edges by their type. Because inners with outers, and //vice versa, this enables us to go straight to the potential matches.


//We keep track of the inner perimeter of the puzzle (Exposed_Edges) as //we work our way inwards. Exposed_Edges is initialized to be the //corner's edges.



class Edge 
{
   enum Type {inner, outer, flat}
   Piece parent; // NOTE : this edge belong to which piece, it must be some piece's lateral[left, right,top, bottom]
   Type type;
   bool fitsWith(Edge type){...}// Inners & outer fit together
}
class Piece
{
   Edge left, right, top, bottom;
   Orientation solvedOrientation = ....;// 90,180,etc
}



class Puzzle
{




   Piece[][] pieces;// Remaining pieces left to put away 
   Piece[][] solution;
   Edge[] inners, outers, flats;




   
   // NOTE: they are the outmost layer pieces with flat edge outside. 
   // we're going to solve this by working our way in-wards, starting   
   //with the corners. This is a list of the inside edges. 
   
    Edge[] exposed_edges;




   void sort() 
   {
        
        // Iterate through all edges, adding each to inners, outers, 
        // etc. as appropriate. Look for the corners-add those to  
        // solution. Add each non-flat edge of the corner to 
        // exposed_edges.
        
   }




   void solve()
   {
        // NOTE: edge1 here refers the edge inside 
        foreach edge1 in exposed_edges
        {
             // Look for a match to edge1 
             if (  edge.type == Edge.type.inner  )
             {
                   // NOTE: outers refers to those remaining pieces 
                   foreach edge2 in outers
                   {
                       if edge1.fitsWith(edges)
                       {
                             
//we found a match ! 
//1. Remove edge1 from exposed_edges. 
//2. Add edges2'piece to solution. 
//3. Check which edges of edge2 are exposed , and add those to exposed //edges.
                             
                       }
                   }
                   // Do the same thing, swapping inner & outer 
             }
        }
   }



}

3. Similar ones