Solving Draught Puzzle - FAQ
◀ Solving Draught Puzzle - Step 4▶ General Traps and Tips Amazon
Here is a list of questions and answers about this program that you may find helpful:
Q: Why do I have a struct and what is that for?
A: To explain this, I need you to understand that the maximum number of orientations of any piece is 8, but that doesn’t mean it’s always 8. Consider this piece
AAAAA
There are only 2 possible orientations of this piece, which are:
AAAAA
A
A
A
A
A
But to tell your program not to store identical orientations, you need to store previous patterns somewhere for comparisons later. I use a struct that holds a two-dimensional array. Then I push the struct’s objects onto a vector. Other functions such as sameArray(), repeated(), and arrayInit() are necessary to make sure only unique orientations are stored.
Q: Why is board a global variable?
A: There are several reasons why board is a global variable. For starters, many functions need access to board, including outputBoard(), Trans::place(), Trans::clear(), and solve(). Also, at any point board always represents the current board layout. Even if a piece is misplaced by Trans::place(), it is removed by Trans::clear().
If you go through by hand several iterations of the recursive function, solve(), then you will convince yourself that keeping board global is not a bad idea. Again you should avoid using global variables but you can do it in this practice assignment.
Q: There are default constructors in Trans and Piece but are never used. Can I remove them?
A: Yes, definitely. Although they are not used, I included them just in case I might need them later.
Q: What does the constructor of Piece do?
A: It finds all orientations of the given piece and stores proper values into patterns.
Q: Why does impasse() take as an argument the array that represents the board? I thought you already made board a global variable.
A: There are many if blocks inside impasse(), as you can see. The conditions in those if blocks are very long, and if the name of the array is board instead of b, the conditions will look much longer and affect readability. This may sound a little funny but it is the reason.
Q: Can you explain what impasse() does? There are so many if blocks but I am a little confused.
A: This is an optimization function that assists the program with finding a solution to the octogram puzzle. I scan the entire board and see if there are one, two, three, or four unfillable holes. If there are, I need to clear the last piece I placed because that piece caused the board to lead nowhere.
Without this function, the program would keep on trying new pieces although the board definitely would lead to an impasse.
Q: How many unique solutions to the octogram puzzle exist?
A: I modified the program a bit so that it can accumulate solutions. I don’t need to run the program nonstop; I can stop it today and run it tomorrow and it will automatically pick up where it left off. I ran this program over a couple of weeks, and I got more than 16,000 UNIQUE solutions! I checked to make sure every solution it finds is unique.
If your optimization function allows you to find out the number of total possible solutions in a short period of time, then you are a truly exceptional software engineer, or you’ve got some Mega-Peta-Herz machine from the future.
Incidentally, to make sure that every solution is unique, you need to store somewhere all solutions the program has found. Every time the program finds a new solution, it compares it with every possible orientation of each of the previous solutions. It is no small task but with strong passion for programming and the challenging octogram puzzle, you can do it!
Next let’s look at common traps and tips in the C++ programming language!
LCD panels consume less power, produce less heat, and are more durable than their plasma counterparts. So why buy plasma panels?
◀ Solving Draught Puzzle - Step 4▶ General Traps and Tips
