Module assignment: Puzzle Lab in Python

Why this assignment

This assignment brings lessons 1 to 4 together. You will write four small Python programs, and each one uses a different part of what you have learned. Task A counts N-Queens placements, which needs the row-by-row search, the column and diagonal checks, and the undo step from lesson 4. Task B counts the subsets that hit a target sum, which needs the skip-or-take pattern and a running total from lesson 3. Task C lists valid bracket strings, which needs pruning on two counters, also from lesson 4. Task D lists every arrangement of a set of letters, which needs the used list and the choose, explore, undo pattern from lesson 3.

The four tasks share one skill. You must decide what the base case is, which choice you make at each step, which check prunes the branch, and what the undo restores. If you can explain those four things for each task, you have learned the module. The grade reflects both the answers and your ability to explain them.

Work on one task at a time. Each task has its own program, its own input, and its own expected output. Do not start a task until the previous one prints the expected output for its examples.

Setting up

Create one Python file for each task, named main.py, in four separate folders. Each file reads its input with input(), which reads one line from the keyboard and returns it as text, and then int() or split() turns that text into numbers or words. Run each program from a terminal with python3 main.py, then type the input when the program waits for it. You can also send the input from a file with python3 main.py < input.txt, which is handy for the longer examples.

Print exactly what the task asks for, and nothing else. Extra text such as a label, a blank line or a prompt will not match the expected output, so do not add words to the output unless the task says to. A prompt such as input("Enter n: ") prints text, so leave the prompt empty.

Task A: count the queen placements

Spec. Read one whole number n, where 1 <= n <= 10. Print one line containing the number of ways to place n queens on an n by n board so that no two queens attack each other. A queen attacks along its row, its column and both diagonals.

Input and output examples. These are the examples the checker uses.

input:  6
output: 4
 
input:  4
output: 2
 
input:  1
output: 1

Approach. Place one queen per row, so the search goes row by row. Before each placement, check the column and the two diagonals. Use three lists of True and False flags, one for columns, one for the sum row + c, and one for the difference row - c + n - 1. When a row is complete, count one solution. Undo every flag you set before you try the next column.

Task B: count the subsets that hit a target

Spec. Read three values in order. First, a whole number n with 1 <= n <= 20. Second, n whole numbers, each from -100 to 100, on one line, separated by spaces. Third, a whole number target from -1000 to 1000. Print one line with the number of subsets whose sum equals target. The empty subset counts when target is 0. Two items with the same value are still two different items.

Input and output examples.

input:
4
1 2 3 4
5
output: 2
 
input:
3
2 2 2
4
output: 3
 
input:
3
-1 1 0
0
output: 4

The third example has four subsets that sum to 0: the empty subset, {-1, 1}, {0}, and {-1, 1, 0}. Check your method against this one, because it tests the empty subset and the negative values.

Approach. Walk through the items by index. At each item, make two calls: skip the item, or take it and add its value to a running total. The base case is the end of the list, where you return 1 if the total equals the target and 0 otherwise. Add the two branch counts together. You do not need to store any subsets, so there is no copy and no undo step.

Task C: list the valid bracket strings

Spec. Read one whole number n, where 1 <= n <= 8. Print every string made of n opening brackets and n closing brackets that is valid, one per line. A string is valid when every closing bracket has an earlier opening bracket to match, and the brackets pair up without crossing. Print the strings in the order your method finds them, with an opening bracket tried before a closing bracket at each step. After the last string, print one line in the form total = X, where X is the number of strings.

Input and output examples.

input:  2
output:
(())
()()
total = 2
 
input:  3
output:
((()))
(()())
(())()
()(())
()()()
total = 5

Approach. Build the string one character at a time in a list of characters, and join it with "".join when you print. Keep two counters, the number of opening brackets used and the number of closing brackets used. You may add an opening bracket only while the opening count is less than n. You may add a closing bracket only while the closing count is less than the opening count. When the string reaches length 2 * n, print it and count it. Undo each character you add by removing the last character with pop before you return.

Task D: list the arrangements of letters

Spec. Read one word from the input. The word has 1 to 6 different lowercase letters with no spaces. Print every arrangement of those letters, one per line, in alphabetical order. An arrangement uses each letter exactly once.

Input and output examples.

input:  cab
output:
abc
acb
bac
bca
cab
cba

The output has six lines, which is 3!. For a word of 6 letters, the output would have 720 lines, which is the largest case you must handle.

Approach. Sort the letters first, so the arrangements come out in alphabetical order. Use a used list of True and False flags, one for each letter. At each position, try every letter that is not used. Mark it used, add it to the answer, explore, then remove it and clear its flag. Print the answer when it has as many letters as the word.

What to hand in

Before you submit, check each item on this list. Each item is a requirement of the spec, and the checker looks for all of them.

• Task A prints the correct count for 1, 4, 6 and 8 queens.
• Task A uses lists of flags with an index of row - c + n - 1 for the difference diagonal.
• Task B counts the empty subset when the target is 0.
• Task B handles negative values in the list and in the target.
• Task C prints the strings in the order given in the example, and prints the total line last.
• Task C never builds a string that breaks the two rules, so it prunes instead of filtering afterwards.
• Task D sorts the letters before the search, so the output is in alphabetical order.
• Task D clears the used flag every time it removes a letter.
• Each program prints only the output the spec asks for, with no extra text.
• Each program has a comment above its main code that names the base case and the undo step.

Grading rubric

Your mark depends on how many of the four tasks give correct output, and on how well you explain your choices. The three levels below describe what each mark looks like.

60 percent. Two tasks print the correct output for their examples. Your code runs for those two tasks. For the other two tasks, the logic is partly right, but one of the examples fails, or the output has extra text. You can describe the base case of each task, but you cannot yet explain the undo step.

80 percent. All four tasks print the correct output for their examples. Each task has a base case and a choose, explore, undo pattern, or a clear counting method for Task B. Your comments name the pruning check in Tasks A and C. You can explain the time cost of each task in one or two sentences. Some of the extra cases in the checklist, such as the 8 queens count or the negative target, may still fail.

100 percent. All four tasks print correct output for the examples and for the extra cases in the checklist. Your code is clean: names are clear, each undo is paired with its choose, and no state leaks between branches. Your comments explain the pruning rule and why it is safe, and you can state the time and space cost of each program. You can say how you would change Task B to handle a list of 100 items, which would rule out the plain recursion.

Hints

Use these hints only after you have tried the task. Each hint is a question you can answer yourself with a pencil and a short example.

Hints for Task A

Start with n equal to 1, where the answer is 1, and then n equal to 2, where the answer is 0. Those two cases tell you whether your base case and your checks are right. For the diagonal lists, write down the values of row + c and row - c + n - 1 for a 3 by 3 board on paper before you write the code, and check that the largest index is inside the list. Python would wrap a negative index to the end of the list without an error, so check the smallest value as well.

Hints for Task B

Test the function on the list [5] with target 0. The only subset that sums to 0 is the empty one, so the answer is 1. If your function returns 0, check the base case: the empty subset is reached when the index is at the end of the list, and its total is 0. A function that starts the total at the wrong value, or that returns 0 when the list is empty, gives this bug.

Hints for Task C

Trace n equal to 2 by hand, writing each string as you build it. Check that the string )) never appears, and that the string (() is extended to (()) and not to (()(. If your output contains a string with more closing brackets than opening brackets at some point, check the condition on the closing counter.

Hints for Task D

Test the function on the two-letter word ab first, which should print ab and ba. If you get only one line, the used flag is probably not cleared. If you get repeated lines, the flag is probably not set before the explore call. Remember to sort the letters before you start the search, or the output will be in the order the letters were typed. Use sorted(word), which returns a list of letters.

Reference solutions

Each reference solution is a complete program. Save it as main.py and run it as described in the setup section. Try your own program first, and compare only after you have a working version or have spent a real attempt on the problem. The programs use the same ideas as the lessons, so reading them with the lesson open is a good way to check your understanding.

Reference solution for Task A

Run it and type 6. The output should be 4.

# Base case: every row has a queen, so count one solution.
# Undo: clear the column and both diagonal flags before trying the next column.
def count_queens(n: int) -> int:
    cols = [False] * n
    diag1 = [False] * (2 * n - 1)  # indexed by row + c
    diag2 = [False] * (2 * n - 1)  # indexed by row - c + n - 1
    count = [0]
 
    def place(row: int) -> None:
        if row == n:
            count[0] += 1
            return
        for c in range(n):
            d1 = row + c
            d2 = row - c + n - 1
            if cols[c] or diag1[d1] or diag2[d2]:
                continue
            cols[c] = diag1[d1] = diag2[d2] = True
            place(row + 1)
            cols[c] = diag1[d1] = diag2[d2] = False
 
    place(0)
    return count[0]
 
 
n = int(input())
print(count_queens(n))

Reference solution for Task B

Run it and type these three lines. The output should be 3.

3
2 2 2
4

# Base case: every item is decided, so return 1 if the total matches, else 0.
# No undo is needed, because the running total is passed down as a value.
def count(nums: list[int], i: int, total: int, target: int) -> int:
    if i == len(nums):
        return 1 if total == target else 0
    return count(nums, i + 1, total, target) + count(nums, i + 1, total + nums[i], target)
 
 
n = int(input())
nums = list(map(int, input().split()))
target = int(input())
print(count(nums[:n], 0, 0, target))

Reference solution for Task C

Run it and type 2. The output should be the two strings and total = 2.

# Base case: the string has 2n characters, so print it and count it.
# Pruning: add "(" only while open < n, and ")" only while close < open.
# Undo: remove the last character before returning.
total = [0]
 
 
def build(n: int, open_count: int, close: int, current: list[str]) -> None:
    if len(current) == 2 * n:
        print("".join(current))
        total[0] += 1
        return
    if open_count < n:
        current.append("(")
        build(n, open_count + 1, close, current)
        current.pop()
    if close < open_count:
        current.append(")")
        build(n, open_count, close + 1, current)
        current.pop()
 
 
n = int(input())
build(n, 0, 0, [])
print(f"total = {total[0]}")

The total list holds one number so that build can change it. A plain number would need global total inside the function, which works too.

Reference solution for Task D

Run it and type cab. The output should be the six arrangements in alphabetical order.

# Base case: the answer has as many letters as the word, so print it.
# Undo: remove the letter and clear its used flag before the next choice.
def permute(letters: list[str], used: list[bool], current: list[str]) -> None:
    if len(current) == len(letters):
        print("".join(current))
        return
    for i in range(len(letters)):
        if used[i]:
            continue
        used[i] = True
        current.append(letters[i])
        permute(letters, used, current)
        current.pop()
        used[i] = False
 
 
word = input().strip()
letters = sorted(word)
permute(letters, [False] * len(letters), [])

Testing your work

Test each program with the examples first, then with the extra inputs below. The extra inputs check the edge cases in the checklist. Work out the expected answer on paper or with a known count before you run the program, so that a surprising output is easy to spot.

• Task A: 1 gives 1, 2 gives 0, and 8 gives 92. The count for 8 is the famous result, and it is a good check for the diagonal lists.
• Task B: 1 with the value 5 and target 0 gives 1, because only the empty subset sums to 0. The list 2 2 2 with target 6 gives 1, because only all three items sum to 6.
• Task C: 1 gives (), with total = 1. The input 4 gives 14 strings, which is the Catalan number for 4, so the last line should read total = 14.
• Task D: a gives a. The word ba gives ab and then ba. The word abcd gives 24 lines, the first abcd and the last dcba.

If an output is wrong, do not change the code at random. Trace the smallest input that fails, write the calls on paper, and find the first step where the state is not what you expected. Most mistakes in this module are a missing undo, a check placed after the choice, or a base case that does not match the problem.

Explaining your work

A short written explanation is part of the mark. For each task, write three or four sentences in your own words. Name the base case, name the choice made at each step, name the check that prunes the search (or say that there is none, for Task B), and give the time cost in terms of the input. For example, for Task D you might write that the base case is a full-length answer, each step chooses one unused letter, the used list prevents repeats, and the cost is n! arrangements, each of length n.

The explanation is also the part of the assignment that matters most in interviews. An interviewer will not ask you to type the code from memory. They will ask what the base case is, why a branch is cut, and what happens if the undo is removed. If you can answer those three questions for each task, you are ready for the backtracking questions in a technical interview.

What you now know

• Backtracking builds an answer one choice at a time, and each choice is undone before the next one is tried.
• A check placed before the choice prunes the search, and it must never cut a branch that holds a valid answer.
• Counting problems can avoid storing answers by passing a running value down the recursion.
• The base case decides what one complete answer looks like, and the undo restores the state for the next branch.
• Test small inputs first, because their answers can be checked by hand.