Programming 1
Week 12: Exercises

1. Subsets

Write a function subsets() that takes an integer N ≥ 0 and prints a list of all subsets of {1, 2, …, N}. For example:

>>> subsets(3)
{}
{3}
{2, 3}
{2}
{1}
{1, 3}
{1, 2}
{1, 2, 3}

2. Combinations

Write a function combinations() that takes a list l and an integer k, and prints all combinations of k elements of l. For example:

>>> combinations([2, 4, 6, 8, 10], 3)
2 4 6
2 4 8
2 4 10
2 6 8
2 6 10
2 8 10
4 6 8
4 6 10
4 8 10
6 8 10

3. Eight Queens

Write a program using pygame that displays an 8 x 8 chessboard. If the user clicks in a square, display a queen there, or remove a queen if it is already present. If any two queens attack each other, display their squares in red. If the user successfully places 8 queens in a way so that no two queens attack each other, display a message "You win".

4. Eight Queens Solver

Write a program that can search for a solution to the eight queens problem and print it in this form:

. . Q . . . . .
Q . . . . . . .
. . . Q . . . .
…

5. Graph Coloring

Write a function that takes an undirected graph G in adjacency-list representation. The function should determine whether it is possible to color the graph with three colors (red, green, blue) such that no two adjacent vertices have a same color. If it is, it should print out a valid coloring.

6. Clique

A clique of a graph is a subgraph that is connected, i.e. in which there are edges between all pairs of vertices. Write a function clique that takes an undirected graph in adjacency-matrix representation and an integer N, and returns true if the graph has any clique of size N. (No efficient algorithm is known to solve this problem, so you will need to enumerate all possible cliques.)

7. Connected Maze

Write a program that reads a rectangular maze from standard input in the following format, where '#' represents a wall:

########
# #  # #
# # #  #
#   # ##
##     #
########

The maze will be surrounded by walls.

The program should print True if the maze is connected, i.e. every two empty squares in the maze are connected by some path. Otherwise print False.

8. Showing the Path

Write a function that takes a 2-dimensional array of booleans representing a maze. There will be no wall in the upper-left or lower-right corner.

The procedure should print out the maze, indicating the shortest path from the upper-left corner to the lower-right corner. For example, the output might look like this:

..######
#.#    #
#.# #  #
#...#  #
## ....#
######..

If no such path exists, print the maze without any path.

Programming 1 Week 12: Exercises