Deliverable #3: Paikin & Tal Solver

Paikin & Tal Solver - zip

• OpenCV: An open-source computer vision library
• NumPy: A package that simplifies large matrix computations.
• Pickle (Optional): An object serialization library

• hammoudeh_puzzle_solver: Excluding the driver, this package is independent of the solver algorithm being used. Its main classes are below. There are other classes as well, but the ones below encapsulate those an average user may encounter.
  • Puzzle: This encapsulates a puzzle. The parameters passed to its constructor are: a path to an image file and an object specifying the PuzzleType.
  • PuzzlePiece: These are created by the Puzzle class in the make_pieces method. A puzzle is composed of one or more PuzzlePiece objects. Generally a user should not be creating PuzzlePieces.
  • PuzzleType: An enumerated type that defines whether the problem is a type 1 or type 2 puzzle (see my Jigsaw puzzle problem literature review for more details on puzzle types).
• paikin_tal_solver: This package's implementation is specific to the requirements of the Paikin & Tal solver. Its primary classes are described below.
  • PaikinTalSolver: This is class is the sole interface between a user and the solver. Its constructor is passed:
    • A list of PuzzlePiece objects.
    • The number of puzzles from which the PuzzlePieces were drawn.
    • A function that calculates the distance between two PuzzlePieces.
    • (Optional) The PuzzleType. If the user does not specify the type, it defaults to type1.
    • (Optional) When solving multiple simultaneous puzzles, a new board is spawned when the mutual compatibility of the next piece to place falls below a certain threshold. The user can either specify the threshold in the constructor or use the default which is 0.5.
    • (Optional) Paikin and Tal's default approach only requires the user to specify the number of boards. A variant of the problem they also discuss allows the user to specify the dimensions of the board. If no dimensions are specified, the board grows organically without boundaries.
  • InterPieceDistance: This encapsulates and manages all of the inter-puzzle piece distances (e.g. asymmetric distance, asymmetric compatibility, mutual compatibility, best buddies, starter piece, etc). Given a set of n PuzzlePiece objects, an InterPieceDistance object contains n objects of type PieceDistanceInformation.
  • PieceDistanceInformation: Each puzzle piece has an associated object of this type that stores its specific inter-puzzle piece distance information with respect to all other PuzzlePieces. Objects of this type are only members of the class InterPieceDistance and are not directly accessible by the user.

	Original Image	Solved Image
Image #1:    (672 Pieces)
Image #2:    (540 Pieces)

Original Image
Solved Image