Exercise #6: Solving Draught Puzzle

◀ Creating A Random Maze - Step 4▶ Solving Draught Puzzle - Step 1
Amazon You probably have seen a draught puzzle before: You are given a set of pieces of different shapes and are asked to arrange them in such a way that they fit into the given panel which is usually a square.

You often have to experiment with each piece at different locations and get a solution by trial and error. When you do find a solution, you think to yourself that there aren’t many solutions and you are a genius to come up with one. I thought this was true until I wrote a program to solve this puzzle.

Amazingly, there are many more unique solutions than I ever thought there were!
There are only several basic ideas behind writing a program to solve this puzzle, but implementing them is a challenge. Let me start by giving you an idea how to approach this program. First you read the pieces in a file and store them somewhere. Then you find all orientations of each piece and store them somewhere, too.

There will be 13 pieces and the maximum number of orientations of each piece is 8. Finally, you write a recursively function that tries all possible arrangements of the pieces until you find a solution.

Now there should be several things you are wondering about, and the first of which should be, “How do you find all orientations of each piece?” Obviously there are several subtle points about this program. So let’s get on with the discussion. If you have the following piece
AAAA
A
then here is a list of its possible orientations:
AAAA   A      A   AA   AA   A       A   AAAA
A      A   AAAA    A   A    AAAA    A      A
       A           A   A            A
       AA          A   A           AA
There are two functions you will use to find a piece’s orientations: transpose() and rotate().

transpose() is to change the piece to its reflection across the line y = -x; rotate() is to rotate the piece by 90 degrees clockwise or counterclockwise.

For example, consider that you have a two-dimensional char array that holds the piece like:
piece p[5][5] = { {\'A\', \'A\', \'A\', \'A\', \' \'},
                  {\'A\', \' \', \' \', \' \', \' \'},
                  {\' \', \' \', \' \', \' \', \' \'},
                  {\' \', \' \', \' \', \' \', \' \'},
                  {\' \', \' \', \' \', \' \', \' \'} };
After you transpose it, it should now become:
piece p[5][5] = { {\'A\', \'A\', \' \', \' \', \' \'},
                  {\'A\', \' \', \' \', \' \', \' \'},
                  {\'A\', \' \', \' \', \' \', \' \'},
                  {\'A\', \' \', \' \', \' \', \' \'},
                  {\' \', \' \', \' \', \' \', \' \'} };
After you rotate it by 90 degrees counterclockwise, then it should become:
piece p[5][5] = { {\'A\', \' \', \' \', \' \', \' \'},
                  {\'A\', \'A\', \'A\', \'A\', \' \'},
                  {\' \', \' \', \' \', \' \', \' \'},
                  {\' \', \' \', \' \', \' \', \' \'},
                  {\' \', \' \', \' \', \' \', \' \'} };
transpose() is a no brainer but rotate() takes some thinking and experimenting. You’d better make sure that after you rotate the piece, the first element of the array is at the leftmost uppermost tip of the piece. Otherwise, the piece above could also look like
piece p[5][5] = { {\' \', \' \', \' \', \' \', \' \'},
                  {\' \', \' \', \' \', \' \', \' \'},
                  {\' \', \' \', \' \', \' \', \' \'}, 
                  {\'A\', \' \', \' \', \' \', \' \'},
                  {\'A\', \'A\', \'A\', \'A\', \' \'} };
And it will make things more complicated.

After you store all orientations of each piece, things become much smoother. Write a simple recursive function that tries all arrangements of pieces on a board; after you find a solution, display the board onscreen (in Figure 15.2 you can see the board’s size).

The recursive function takes only several lines; however, without an optimization function to assist it, it will take an extremely long time. This optimization function is the key to solving this puzzle in a reasonable amount of time.

If your program has a great optimization function, it can find a solution dramatically faster than if your program has a poor one.
To write such a function, you basically scan the current board and see if its current layout will definitely lead nowhere. If so, stop trying to put on any more pieces. For instance, consider the following board:

Figure 15.2 – a sample board with pieces
**********
*ABBBBCCD*
*AFFFBCCD*
*AFFE  DD*
*AEEE J D*
*AEG JJJ *
*IGGG JH *
*IG    H *
*III  HHH*
**********
Right between D and J, we see a hole. No matter how hard the program tries to fill the remaining holes on the board, it will lead nowhere.

In this case, you should stop putting on more pieces; instead, you should move pieces so that it is at least possible for the current board to lead to a solution.

Here is the input file that contains all 13 pieces:
###
# #

  ##
###

  #
 ##
##

#####

####
   #

##
##

####
 #

  #
###
#

###
##

 #
###
#

###
 #
 #

###
  #
  #

 #
###
 #
Note that there is one line between any two pieces. Another important factor that affects the speed of your program is the order in which you put on the pieces.

Your program should work with any order of pieces the program takes in. With a good optimization function, you are likely to get a solution in a timely manner regardless of the order.

My program does something extra. It keeps on finding solutions, and every time it finds one, it outputs the solution as well as the time it took to find it.
Get out some scratch paper (I used five sheets of paper) and start the designing process of this program. You can’t afford to lose another minute. This program is bigger than all the earlier ones, so I won’t go as detailed as I did regarding how I followed the four golden steps of programming.

If you have worked through all the earlier programs with me, you will not have difficulty understanding my skeletons and comments.

Here is a list of suggestions about how you should approach this program:

  • Read the pieces from the file line by line by using getline(). You get an entire line, and then see what it contains and if it contains a single newline character, you know that you have done collecting the current piece and should start collecting the next one.
  • Make sure the function that rotates a piece works perfectly. After you have transpose() and rotate(), write a small program to print out all unique orientations of a given piece. If you succeed, the rest is a breeze.
  • Many pieces have 8 unique orientations, but there are pieces that have only 2 or 4 unique orientations. In that case, discard repeated ones and store only distinct ones.
  • The heart of the program is the recursive function that recursively tries all possible arrangements of the pieces. As horrible as it may sound, it actually takes only several lines of code. Your job is to use loops to try all orientations of all pieces at all possible locations. No catch here.
  • The second most important function is the optimization function. There are many ways to optimize the searching process, but you need to find one fast. In my program, I simply scan the entire board for unfillable holes. If that’s the case, I stop going any further and look for other possibilities. Keep in mind that all pieces take 5 1-by-1 spots except the square piece, which takes 4 spots.

Let's apply our favorite Four Step Programming Model described in Chapter 11.8!
◀ Creating A Random Maze - Step 4▶ Solving Draught Puzzle - Step 1

fShare
Questions? Let me know!