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 140 cards my Contact version contains. Not surprisingly, many solutions are of rather linear nature since the game on­ly contains two branching cards, i. e. cards where three sides boast connections.
Thus, the search is further narrowed in by demanding a maximum di­men­sion, that is the final configuration has to lie in a card rectangle of a given area. From my testing, a maximum di­men­sion of 500 is moderately quickly computed (~ 30 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 24 bits, allowing for card ro­ta­tion, re­flec­tion and match determination being im­ple­ment­ed 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