Complete Contact Configurations (#225)

Contact is a board game designed by Ken Garland in which players draw square tiles containing colored connections from a pile, attempting to form matches. Whilst the game is enjoyable to play — allowing the odd trading of cards in unfortunate circumstances — it seldom leads to a com­plete configuration, meaning a valid contacting arrangement using all avail­able cards.

With the power of stochastically driven brute-force, however, finding such com­plete configurations turns out to be feasible — at least when playing with the 𝟣𝟦𝟢 cards my Contact version contains. Not surprisingly, many solutions are of rather linear nature since the game only contains two branching cards, i. e. cards where three sides boast connections.
Thus, the search is further narrowed in by demanding a maximum dimension, that is the final configuration has to lie in a card rectangle of a given area. From my testing, a maximum dimension of 𝟧𝟢𝟢 is moderately quickly computed (~ 𝟥𝟢 sec @ 4.00 GHz), whilst lower maximum dimensions appear to be less likely.

From an im­ple­men­ta­tion point of view, a generalized Contact card (defined as four sides, each with three nodes being blank or colored one of three colors) snuggly fits into 𝟤𝟦 bits, allowing for card ro­ta­tion, re­flec­tion and match determination being implemented through integer bit fiddling.
The stochastic process is driven by an (ideally assumed) uniformly distributed ran­dom num­ber gen­er­a­tor, being recursively applied until all cards are consumed. Finally, an image is created as a por­ta­ble pix­map .ppm and resized to a .png using ImageMagick.

Source code: com­plete-contact-configurations.c