1. Computing

Programming Challenge 66 - Solve a jigsaw puzzle

Completed

By

I've always liked jigsaws so this programming challenge is about solving one. It's not graphical though but uses text characters so the jigsaw is a big square of 18 x 18 characters where each jigsaw piece is a bunch of letters all the same.

This shows what part of the jigsaw puzzle might look like:

bbbbbhhhkkkk
bbbbhhhhhkkk
cbbchhhkkkkk
cccchxxxkkkk
cccxxxxuuuuu
ccyyyyyyuuuu
...

In this example you can see a b piece, a c piece, k piece and others etc.

This is a speed programming challenge. You are given a set of jigsaw pieces (25 in all - named b-z (no a) that fit into an 18 x 18 grid. The letters in each jigsaw piece are all next to each other aptobliquely (it means horizontally or vertically but not diagonally).

These pieces are all odd shapes that fit in a rectangle with holes (i.e. where other pieces fit in) defined as a period. For instance the u piece is 4 across x 5 down and looks like this:

uuuu
uuu.
uu..
uu..
uu..

Input File

The pieces are provided in the pieces.txt text file which is in the same location as your exe. Each piece has several lines in that text file. First is one line with the word 'n' Piece followed by the characters in rows, all the same width which either have that letter or a period. Here is what that u piece looks like:

u Piece
uuuu
uuu.
uu..
uu..
uu..

Note it's 5 rows that fit in a maximum of four columns.

Output

The output file called results.txt (please create in the same location as your exe) consists of printing the entire 18 x 18 jigsaw with all characters in the grid with no holes. The input file has 25 pieces made of 324 characters.

Print each of the 18 rows into the file using the letters b to z in their correct place and use the timing code (see General Tips below) to show how quickly your program took to solve the jigsaw. and output that time on the end of results.txt.

Four Color Coding

I'm not sure if this helps or not but when I created the puzzle, I made sure all the pieces were color coded using four colors. The four color theorem which was proved not many years ago says that you can color any map with just four colors, such that no two countries that touch will have the same color. You don't get red next to red for example.

These are the color of each piece:

  • Green: b,e,g,h,l and v
  • Red: i,w and y
  • Yellow: c,k,n,o,q,t,x and z
  • Blue: d,f,m,j,p,r,s and u

So you'll never get for example a i piece next to a w or y piece.

?

Winning Criteria

Correctly solving it in the fastest time wins. Note there will be a different pieces.txt used than the one given here.

Final Results

Unless there were other entries, Mark Mammel's entry was the only one and correctly solved it in 76 milli-seconds. Thanks to Mark for entering!

  1. Mark Mammel(C++) Result=ok, Time = 0.07752282 (USA)

General Tips on Entering

This is a single page article with tips on things to do and not do when entering challenges. Please read it!

These tips contain code for C,C++ and C# (Not Go, yet) that can do very high precision timing.

Rules

This is for glory only. About.com does not permit prizes to be given.

Please submit your source code and the output file to the cplus@aboutguide.com?subject=Programming Contest 66 email address with the subject line Programming Contest 66.

It must compile with Open Watcom, Microsoft Visual C++ 2008/2010 Express Edition/Microsoft Visual Studio 2008/2010, CC386 or Borland Turbo C++ Explorer, Microsoft Visual C# 2010/2012 Express Edition, GCC/G++ and any Google Go compiler. If it doesn't compile, it can't be run so is automatically disqualified.

Please include your name, age (optional), blog/website url (optional) and country. Your email address will not be kept, used or displayed except to acknowledge your challenge entry. You can submit as many entries as you like before the deadline which is February 3, 2013.

The top ten entries in each challenge will be listed, judged on highest score and in the case of a draw, the fastest time. A condition of entry is that you allow your source code to be published on this website, with full credits to you as the author.

  1. About.com
  2. Computing
  3. C / C++ / C#
  4. Programming Challenge List
  5. Programming Challenge 66 - Jigsaw Puzzle

©2014 About.com. All rights reserved.