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.


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:


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