Backtracking

Last week’s assignment introduced you to the intriguing world of recursion and built your solid base of recursive fundamentals. This week we pivot towards applying the powerful nature of recursive backtracking to real-world problems. As is typical in recursive problem-solving, you’ll likely spend the bulk of your time wrapping your head around the “thinking recursively” part, but once writing the actual code, you’ll find that a rather concise algorithm is all that’s needed to solve the task. That sparse elegance can sometimes seem incongruous with how hard you had to work for it. Start early to give yourself enough time to let these deep and powerful ideas percolate to full understanding. When you put the finishing touches on these problems, you will have earned your rightful place as a master in the way of recursive problem-solving.

Learning goals

After completing this assignment, you will be able to…

• Appreciate the elegance and power of recursive problem-solving and identify problems that are well-suited to be solved recursively
• Implement more advanced recursive algorithms to solve problems that cannot be easily solved using an iterative approach

Assignment parts

This assignment consists of a warmup exercise and three separate problems to solve using recursive backtracking.

• Warmup

  Practice with testing and debugging recursive functions, using the classic Towers of Hanoi puzzle.

• Solving a marble solitaire game

  Solve a marble board game.

• Computational redistricting

  Determine if there is a fiar geometric division of a state’s population into equal-size electoral districts.

Getting started

When you download the starter code, you’ll be redirected to our MQE. You’ll get the starter code download upon completion of the MQE! Thank you for your feedback – we read it all and really appreciate it.

📦 Starter code

The source files you will edit are MarbleBoard.cpp and marbles.cpp (possibly MarbleBoard.h, if you make helper functions, but not required), redistrict.h. Additionally, you will answer questions in short_answer.txt.

Resources

Here are some resources that you might find helpful for this assignment:

• The CS106B Guide to Testing
• The CS106B Style Guide
• Resolving Common Build/Run Errors, compiled by section leader Jillian Tang.
• Section: see Section 4
• Textbook Chapter 9.

Getting help

If you have questions for us, the Ed forum is open 24/7 for general discussion. Always start by searching first to see if your question has already been asked and answered before making a new post. To troubleshoot a problem with your specific code, your best bet is to bring it to the [LaIR] helper hours or office hours.

Submit

Before you call it done, run through our submit checklist to be sure all your ts are crossed and is dotted. Then upload your completed files to Paperless for grading.

Please submit the following files:

• MarbleBoard.cpp
• MarbleBoard.h
• marbles.cpp
• redistrict.cpp
• short_answer.txt

🏁 Submit to Paperless

Note: On Paperless, all due dates and submission times are expressed in [Pacific time][PT].