paikin_tal_solver package

Submodules

paikin_tal_solver.inter_piece_distance module

Inter-Puzzle Piece Distance Object

class paikin_tal_solver.inter_piece_distance.InterPieceDistance(pieces, distance_function, puzzle_type)[source]

Bases: object

Master class for managing inter-puzzle piece distances as well as best buddies and the starter puzzle pieces as defined by the Paikin and Tal paper.

all_best_buddies(p_i)[source]

Gets an array of all best buddies information as a list for a specified puzzle piece.

Parameters:p_i (int) – Piece identification number
Returns (List[Tuple[int, PuzzlePieceSide]]):
Best buddy information for the specified piece.
assert_valid_type1_side(p_i_side, p_j_side)[source]

Valid Side Checker

For type 1 puzzles, this function is used to verify that two puzzle piece sides are a valid pair.

Parameters:
  • p_i_side (PuzzlePieceSide) – Side of the primary piece (p_i) where p_j will be placed.
  • p_j_side (PuzzlePieceSide) – Side of the secondary piece (p_j) where p_i will be placed.
asymmetric_compatibility(p_i, p_i_side, p_j, p_j_side)[source]

Asymmetric Compatibility Accessor

Returns the asymmetric compatibility for p_i’s side (p_i_side) relative to p_j on its side p_j_side.

Parameters:
  • p_i (int) – Primary piece for asymmetric distance
  • p_i_side (PuzzlePieceSide) – Side of the primary piece (p_i) where p_j will be placed
  • p_j (int) – Secondary piece for the asymmetric distance.
  • p_j_side (PuzzlePieceSide) – Side of the secondary piece (p_j) which is adjacent to p_i
Returns (int):
Asymmetric compatibility between puzzle pieces p_i and p_j.
asymmetric_distance(p_i, p_i_side, p_j, p_j_side)[source]

Asymmetric Distance Accessor

Returns the asymmetric distance for p_i’s side (p_i_side) relative to p_j on its side p_j_side.

Parameters:
  • p_i (int) – Primary piece for asymmetric distance
  • p_i_side (PuzzlePieceSide) – Side of the primary piece (p_i) where p_j will be placed
  • p_j (int) – Secondary piece for the asymmetric distance.
  • p_j_side (PuzzlePieceSide) – Side of the secondary piece (p_j) which is adjacent to p_i
Returns (int):
Asymmetric distance between puzzle pieces p_i and p_j.
best_buddies(p_i, p_i_side)[source]

Gets the best buddy information (if any) for a specified piece’s side

Parameters:
  • p_i (int) – Identification number of the piece who best buddy information is to be retrieved
  • p_i_side (PuzzlePieceSide) – Side of piece whose best buddy is being retriefed
Returns (List[int]):
List of best buddy piece id numbers
calculate_inter_piece_distances(pieces)[source]

Inter-Piece Distance Calculator

Calculates the inter-piece distances between all pieces. Also calculates the compatibility between two parts.

Parameters:pieces ([PuzzlePiece]) – All pieces across all puzzle(s).
calculate_mutual_compatibility(is_piece_placed=None)[source]

Mutual Compatibility Calculator

Calculates the mutual compatibility as defined by Paikin and Tal.

Parameters:is_piece_placed (Optional [Bool]) – List indicating whether each piece is placed
find_best_buddies(is_piece_placed=None)[source]

Finds the best buddies for this set of distance calculations.

The best buddies information is stored with the inter-piece distances.

Parameters:is_piece_placed (Optional [Bool]) – List indicating whether each piece is placed
find_start_piece_candidates(is_piece_placed=None)[source]

Creates a list of starter puzzle pieces. This is based off the criteria defined by Paikin and Tal where a piece must have 4 best buddies and its best buddies must have 4 best buddies.

This list is sorted from best starter piece to worst.

Parameters:is_piece_placed (Optional [Bool]) – List indicating whether each piece is placed
static get_p_j_side_index(puzzle_type, p_j_side)[source]

Secondary Piece Side Index Lookup

Parameters:
  • puzzle_type (PuzzleType) – Either type1 (no rotation) or type 2 (with rotation)
  • p_j_side (PuzzlePieceSide) – Side for the secondary piece p_j.
Returns (int):
For type 1 puzzles, this normalizes to an index of 0 since it is the only distance for two puzzle pieces on a given side of the primary piece. For type 2 puzzles, the index is set to the p_j_side value defined in the PuzzlePieceSide enumerated type.
get_total_best_buddy_count()[source]

Get the total number of best buddies.

This function is mostly used for assert checking.

Returns (int): Total number of best buddies

static get_valid_neighbor_sides(puzzle_type, p_i_side)[source]

Valid Puzzle Piece Determiner

For a tuple of puzzle_type and puzzle piece side, this function determines the set of valid PuzzlePieceSide for any neighboring piece.

For example, if the puzzle is type 1, only complementary sides can be placed adjacent to one another. In contrast, if the puzzle is type 2, then any puzzle piece side can be placed adjacent.

Parameters:
  • puzzle_type (PuzzleType) – Puzzle type being solved.
  • p_i_side (PuzzlePieceSide) – Side of p_i puzzle piece where p_j will be placed.
Returns (List[PuzzlePieceSide]):
List of all valid sides for a neighboring puzzle piece.
mutual_compatibility(p_i, p_i_side, p_j, p_j_side)[source]

Mutual Compatibility Accessor

Returns the mutual compatibility for p_i’s side (p_i_side) relative to p_j on its side p_j_side.

Parameters:
  • p_i (int) – Primary piece for asymmetric distance
  • p_i_side (PuzzlePieceSide) – Side of the primary piece (p_i) where p_j will be placed
  • p_j (int) – Secondary piece for the asymmetric distance.
  • p_j_side (PuzzlePieceSide) – Side of the secondary piece (p_j) which is adjacent to p_i
Returns (int):
Mutual compatibility between puzzle pieces p_i and p_j.
next_starting_piece(placed_pieces=None)[source]

Next Starting Piece Accessor

Gets the puzzle piece that is the best candidate to use as the seed of a puzzle.

Parameters:placed_pieces (Optional [bool]) – An array indicating whether each puzzle piece (by index) has been placed.
Returns (int):
Index of the next piece to use for starting a board.
recalculate_remaining_piece_compatibilities(is_piece_placed, is_piece_placed_with_no_open_neighbors)[source]

Compatibility Recalculator

When no best buddy is in the pool, this function is called to recalculate the best buddies and compatibilities.

Parameters:
  • is_piece_placed ([Bool]) – List indicating whether each piece is placed
  • is_piece_placed_with_no_open_neighbors ([Bool]) – Subset of the elements in the array “is_piece_placed.” It is only those pieces that are placed AND have no open locations amongst their direct neighbors.
class paikin_tal_solver.inter_piece_distance.PieceDistanceInformation(id_numb, numb_pieces, puzzle_type)[source]

Bases: object

Stores all of the inter-piece distance information (e.g. asymmetric distance, asymmetric compatibility, mutual compatibility, etc.) between a specific piece (based off the ID number) and all other pieces.

add_best_buddy(p_i_side, p_j_id_numb, p_j_side)[source]

Best Buddy Puzzle Piece Adder

Adds a best best buddy to a puzzle piece’s side.

Parameters:
  • p_i_side (PuzzlePieceSide) – Identification number for a side of the puzzle piece p_i
  • p_j_id_numb (int) – Identification number for the best buddy puzzle piece
  • p_j_side (PuzzlePieceSide) – Identification number for the side of p_j where p_i is placed
all_best_buddies()[source]

Best Buddy Accessor

Gets all the best buddies of a piece

Returns (List[int]): List of best buddy pieces

asymmetric_compatibility(p_i_side, p_j, p_j_side)[source]

Puzzle Piece Asymmetric Compatibility Accessor

Gets the asymmetric compatibility for a piece (p_i) to another piece p_j on their respective sides.

Parameters:
  • p_i_side (PuzzlePieceSide) – Side of the primary piece (p_i) where p_j will be placed
  • p_j (int) – Secondary piece for the asymmetric distance.
  • p_j_side (PuzzlePieceSide) – Side of the secondary piece (p_j) which is adjacent to p_i
Returns (double):
Asymmetric compatibility between the two pieces on their respective sides
asymmetric_distance(p_i_side, p_j, p_j_side)[source]

Asymmetric Distance Accessor

Returns the asymmetric distance between p_i and p_j.

Parameters:
Returns (int):
Asymmetric distance between pieces p_i (implicit) and p_j (explicit) for their specified sides.
best_buddies(side)[source]

Best Buddy Accessor

Gets a list of best buddy piece ids for a puzzle piece’s side. If a puzzle piece side has no best buddy, this function returns an empty list.

Parameters:side (PuzzlePieceSide) – Side of the implicit puzzle piece.
Returns ([int]):
List of best buddy pieces
best_buddy_candidates(side)[source]

Best Buddy Candidate Accessor

Gets the list of possible best buddies for this set of distance information.

Parameters:side (PuzzlePieceSide) – Reference side of the puzzle piece
Returns (List[ Tuple[int] ]):
Returns an array of the ID numbers and the respective side for the ID number for possible best buddies.
calculate_asymmetric_compatibility(is_piece_placed=None)[source]

Asymmetric Compatibility Calculator

Calculates the asymmetric compatibility for this piece with respect to all other pieces.

Parameters:is_piece_placed (Optional [Bool]) – For each puzzle piece, True if the piece is placed and false otherwise.
calculate_inter_piece_distances(pieces, distance_function)[source]

Calculates the inter-piece distances between all pieces.

Parameters:
  • pieces ([PuzzlePiece]) – All pieces across all puzzle(s).
  • distance_function – Function to measure the distance between two puzzle pieces
clear_best_buddy_information()[source]

Best Buddy Information Clearer

Clears the best buddy candidates and best buddy list for a puzzle piece.

get_mutual_compatibility(p_i_side, p_j, p_j_side)[source]

Puzzle Piece Mutual Compatibility Accessor

Gets the mutual compatibility for a piece (p_i) to another piece p_j on their respective sides.

Parameters:
  • p_i_side (PuzzlePieceSide) – Side of the primary piece (p_i) where p_j will be placed
  • p_j (int) – Secondary piece for the asymmetric distance.
  • p_j_side (PuzzlePieceSide) – Side of the secondary piece (p_j) which is adjacent to p_i
Returns (double):
Mutual compatibility between the two pieces on their respective sides
minimum_distance

Minimum (Best) Distance Property

For this piece’s inter-piece distance information, this function is used to access the MINIMUM (i.e. best) distance between it and any other piece.

Returns(float):
Minimum (i.e. best) distance for this puzzle piece
piece_id

Piece ID Accessor

Gets the piece identification number for a PieceDistanceInformation object

Returns (int):
Piece identification number
second_best_distance

Second Best Distance Property

For this piece’s inter-piece distance information, this property returns the second best distance.

Returns (float):
Second best distance for this puzzle piece
set_mutual_compatibility(p_i_side, p_j, p_j_side, compatibility)[source]

Puzzle Piece Mutual Compatibility Setter

Sets the mutual compatibility for a piece (p_i) to another piece p_j on their respective sides.

Parameters:
  • p_i_side (PuzzlePieceSide) – Side of the primary piece (p_i) where p_j will be placed
  • p_j (int) – Secondary piece for the asymmetric distance.
  • p_j_side (PuzzlePieceSide) – Side of the secondary piece (p_j) which is adjacent to p_i
  • compatibility (float) – Mutual compatibility between p_i and p_j on their respective sides.

paikin_tal_solver.paikin_tal_tester module

Unittest Module for the Paikin Tal Solver

class paikin_tal_solver.paikin_tal_tester.PaikinTalTester(methodName='runTest')[source]

Bases: unittest.case.TestCase

test1()[source]

paikin_tal_solver.solver module

Paikin Tal Solver Master Module

class paikin_tal_solver.solver.BestBuddyHeapInfo(bb_id, bb_side, neighbor_id, neighbor_side, location, mutual_compatibility)[source]

Bases: object

A heap is used to store the best buddy matches. This class encapsulates all the requisite data for the heap objects.

It must implement the “__cmp__” method for sorting with the heap. Note that cmp is used to create a maximum heap.

class paikin_tal_solver.solver.BestBuddyPoolInfo(piece_id)[source]

Bases: object

Used to encapsulate best buddy objects in the pool of pieces to be placed.

key

Returns (int) – Best Buddy Pool Info Key.

class paikin_tal_solver.solver.PaikinTalSolver(numb_puzzles, pieces, distance_function, puzzle_type=None, new_board_mutual_compatibility=None, fixed_puzzle_dimensions=None)[source]

Bases: object

Paikin & Tal Solver

DEFAULT_MINIMUM_MUTUAL_COMPATIBILITY_FOR_NEW_BOARD = 0.5
DEFAULT_PUZZLE_TYPE = <PuzzleType.type1: 1>
best_buddy_accuracy

Access all of the best buddy accuracy information associated with the puzzle.

Returns (List[BestBuddyAccuracy]):
All the best buddy accuracy results in the puzzle.
static get_side_of_primary_adjacent_to_other_piece(primary_piece_location, other_piece_location)[source]

Given two adjacent pieces (i.e. a primary piece and an other piece), return the side of the primary piece that is adjacent (i.e. touching) the other piece.

Parameters:
  • primary_piece_location (PuzzleLocation) – Location of the primary piece
  • other_piece_location (PuzzleLocation) – Location of the other piece
Returns (PuzzlePieceSide):
Side of the primary piece adjacent to the other piece.
get_solved_puzzles()[source]

Paikin and Tal Results Accessor

Gets the results for the set of the Paikin and Tal solver.

Returns (List[PuzzlePiece]):
Multiple puzzles each of which is a set of puzzle pieces.
puzzle_type

Puzzle Type Accessor

Gets whether the puzzle is type 1 or type 2

Returns (PuzzleType):
Type of the puzzle (either 1 or 2)
run(skip_initial=False)[source]

Runs the Paikin and Tal Solver.

Parameters:skip_initial (Optional bool) – Used with Pickling. Skips initial setup.
use_best_buddy_placer = False
class paikin_tal_solver.solver.PuzzleOpenSlot(location, piece_id, open_side)[source]

Bases: object

As pieces are placed in the puzzle, invariably open slots on the puzzle board will be opened or closed.

This data structure stores that information inside a Python dictionary.

key

Dictionary key for the an open slot in the dictionary.

Module contents