package knights_tour
-
knights_tour
Legend:
Library
Module
Module type
Parameter
Class
Class type
Library
Module
Module type
Parameter
Class
Class type
package knights_tour
Legend:
Library
Module
Module type
Parameter
Class
Class type
Library
Module
Module type
Parameter
Class
Class type
A Polyomino is a puzzle piece composed of a number equally sized grid-squares. Depending on the number of squares they can go by different names.
- 5 squares: 5-omino or pentomino
- 2 squares: 2-omino or domino
We represent polyominos as a Set of points with an x and y coordinate.
Typically puzzles and games involving polyominos have physical puzzle pieces that can be flipped over and rotated. The pieces can also be placed down on the puzzle board at different locations.
This means that to decide whether two sets of points represent the same Polyomino puzzle piece, we need to consider them equivalent under these transformations:
- rotate 90, 180 or 270 degrees
- flipped around (mirroring along the vertical or horizontal axis)
- translated
An unplaced polyomino puzzle piece. It is characterized by a normalized PointSet, making it invariant to any combination 90 degree rotation, mirroring, and translation.
val name : t -> charGets the 'name' of a polyomino. The name is unique for polyomino of a the same order (i.e. if two polyominos have the same order and the same name, it means they are the same polyomino)
Compares two polymoninos to see if they represent the same shape; invariant to rotation, mirroring and translation
val order : t -> intThe number of squares in a polyomino is called its 'order'.
val points : t -> PointSet.tGets the canonical PointSet that characterizes this Polyomino
val variants : t -> PointSet.t List.tGets all variants of a given Polyomino. A variant is simlar shape obtained by applying rotation and mirroring transformations (but no translation). I.e. it is a specific orientation of Polyomino that has not yet been placed on a specific location of the board.
val to_string : t -> stringCreate a 'string-image' of the polyomino
val of_order : int -> t listObtain all unique polymino of order n
val pp_poly : Format.formatter -> t -> unitPrint string image of polyomino to a formatter
Find the first polyomino that is completely assymetric and remove all but one of its variants. This is a 'hack' that allows eliminating equivalent symmetric solutions from a puzzle.
Randomize the order of puzzle pieces and their variants. This can make running puzzle solvers more interesting as it then tends to produce different solutions each time you run it.
val save : out_channel -> t list -> unitWrites a list of polyominos and all their variants in a textual format that is human readable; but can also be used to restore that same list of pieces and variants by loading the file later.
val save_fmt : Format.formatter -> t list -> unitLike save but writes the data to Format.formatter instead of a out_channel
val load : in_channel -> t listReads a list of polyominos and all their variants from a file that was previously written using save
val load_lines : Knights_tour.Lines.t -> t listReads a list of polyominos and all their variants from sequence of lines, as previously written using save