|Programmer Puzzle - Hermit Boxes|
|Written by Joe Celko|
Can you program a solution to this puzzle in which you place 3D boxes on a 2D grid to prevent your opponent being able to make a legal move? Let's hear what the team at International Storm Door & Software think of the problem.
If you've not already met experienced developer Melvin Frammis and his junior programmer sidekick, Bugsy Cottman you'll find they were initially introduced in the Elevator Puzzle, the first in the series of Sharpen Your Coding Skills and they have posed us further challenges ever since.
This particular puzzle is a little different. It isn't a classic. A new game and what programmer can resist the algorithmic attraction of a new game?
(click on cover for details)
“What do you have there?” asked Bugsy Cottman, junior programmer at International Storm door and Software.
“It is the March 2013 issue of GAMES magazine and some stolen building blocks I ripped off my nephew's toy chest this weekend”, answered Melvin Frammis.
“I'll bite; why?”
“I got hooked on Hermit Boxes, the game shown on the cover and wanted to make a set for myself,” replied Melvin. “I glued some blocks together to make one by one by two boxes and ruled out a four by four square grid for the board. You and another player take turns placing one box of any color (red, yellow, or blue) so that it covers either one or two squares of the board.”
Bugsy picked up a box, and experimented with placing it on its side to cover two squares and on end to cover one square. More people came into the break room and drifted over to see what was happening.
“This reminds me a little bit of the Mutilated Chessboard Problem ,a puzzle about covering a checker broad with dominoes", said Frank from accounting who had just walked up. “Each domino has to sit on one black square and one white square, so if you remove two squares of the same color, there is no way to cover the checkerboard.”
“I was thinking it looks like De Bono's L-Game myself," volunteered Mary from Marketing, " I took a critical thinking course from De Bono Institute one summer in college.”
Melvin Frammis was starting to enjoy his audience. “No, the pieces and the board look similar, but this is a different problem. Boxes of the same color may not touch, not even diagonally. Each player takes a turn putting boxes on the grid until of then has no legal placement.”
Mel took a few of the pieces and set up a game.
“Now what is the next move that will give you a win?”
“I got i!” announced Frank, “A red box in the second square on the bottom row. After that, the other guy has to play red on one of the squares in the third column or red in the lower left corner. I play the other and win!
Think you can write program to play this game?
Two players take turns placing one box of red, yellow, or blue so that it covers either one or two squares of the board. Blocks of the same color may not touch, not even diagonally. The aim of the game is on your turn, to choose a combination of colored box and the one or two squares on which to place it so that your opponent has no possible legal placement.
Apart from the fun this could be a good game for a phone or tablet - it only requires a simple playing area and graphics. The challenge is in the algorithm needed to give the human a good game.
Joe Celko is best known as the database expert who writes books on SQL, data and databases. But before that, he was an honest developer obsessed with finding good algorithms and clean code.
More Joe Celko puzzles tackled by Melvin, Bugsy & Co
Jigsaw Puzzles and The MacMahon Squares
Vertex Coverings And The Cool Kids Problem
Sharpen your Coding Skills - Elevator Puzzle
Unshuffling A Square Is NP-Complete
or email your comment to: email@example.com
To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, Facebook, Google+ or Linkedin, or sign up for our weekly newsletter.