Complete Contact Configurations

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 complete configuration, meaning a valid contacting arrangement using all available cards.

With the power of stochastically driven brute-force, however, finding such complete 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 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 500 is moderately quickly computed (~ 30 sec @ 4.00 GHz), whilst lower maximum dimensions appear to be less likely.

This slideshow requires JavaScript.

From an implementation 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 rotation, reflection and match determination being implemented thru integer bit fiddling.
The stochastic process is driven by an (ideally assumed) uniformly distributed random number generator, being recursively applied until all cards are consumed. Finally, an image is created as a portable pixmap .ppm and resized to a .png using ImageMagick.

Source code: contact.c

Sudoku Generation

Over two years ago, I wrote a basic 3×3-sudoku solver which uses both fundamental rule-based elimination and guessing to arrive at the solution. Revisiting the topic of computer-aided sudoku manipulation, I wrote a generalized sudoku generator (sudoku.hs).

    | 4  
  3 |    
---------
  2 | 1  
  4 |    

./sudoku 5 2

Continue reading

JSweeper

Adding to my collection of clones of popular, well-known games, I created back in November of 2016 a Java-implementation of the all-time Windows classic game, Minesweeper.

Minesweeper was pre-installed on every installation of Windows up to and including Windows 7 and has been ported to a variety of different systems. Because of this, nearly everyone has at least once in their life played Minesweeper or at least heard of it.
In Minesweeper you are presented with a square grid of covered tiles containing either numbers or mines. Your task is it to uncover all tiles which are not mines in the least amount of time. When you uncover a mine, it explodes and the game is lost. To aid in figuring out which tiles are mines and which are not, every tile that is not a mine tells you how many mines are in the neighbouring eight tiles. Tiles which have no neighbouring mines are drawn gray and uncover neighbouring non-mine tiles once uncovered.
More on Minesweeper can be found in this Wikipedia article — I am linking to the German version, as the current English version has major flaws and lacks crucial information. If you are so inclined, feel free to fix the English Minesweeper Wikipedia article.

In my clone, there are three pre-defined difficulty levels, directly ported from the original Minesweeper game, and an option to freely adjust the board’s width and height as well as the number of bombs which will be placed. Gameplay is nearly identical to the original, as my clone also uses a square grid and the tile’s numbers correspond to the number of bombs in the eight tiles surrounding that tile.
The game has a purposefully chosen pixel-look using a self-made font to go along with the pixel-style.

Controls

  • Arrow keys and enter to navigate the main menu
  • Arrow keys or mouse movement to select tiles
  • Space, enter or left-click to expose a tile
  • ‘f’ or right-click to flag a tile
  • ‘r’ to restart game when game is either won or lost
  • Escape to return to the main menu when game is either won or lost
  • F11 toggles fullscreen

To play the game, you can either download the .jar file or compile the source code for yourself. The source code is listed below and can be downloaded as a .java file.

Level select screen Successfully played an easy game A failed attempt at solving a hard game


// Java 1.6 / 1.8 code
// Jonathan Frech  5th of November, 2016
//         edited  7th of November, 2016
//         edited 11th of November, 2016
//         edited 13th of November, 2016
//         edited 14th of November, 2016
//         edited 15th of November, 2016
//         edited 17th of November, 2016
//         edited 19th of November, 2016
//         edited 19th of May     , 2017
//         edited 22nd of May     , 2017
//          * fixed max mine cap when
//            using custom settings

Continue reading