Skip to content

Exercise 7: Recursions

Prerequisite

You have completed Exercise 6.

Learning Outcomes

Able to model a problem as a search problem and solve it recursively.

Deadline

This exercise is part of the CS1010 formative assessment. Submit your solution before 6 November 2023, 23:59 to receive feedback and earn your achievement "badges".

The link to accept the exercise is not available publicly. Visit Canvas for the link.

Concepts and Difficulty

Question Recursion Branch-and-Bound Difficulty
1 Fill
2 Maze
3 Walk
4 Sudoku

Question 1: Fill

One of the basic operations in a drawing application is the fill operation (aka bucket fill). You will implement this operation in this assignment.

An image can be considered as a 2D array of pixels. Each pixel has a color, represented by three integers, corresponding to the red, green, and blue components of the color. We say that two pixels are adjacent to each other if they share a common edge. So a pixel can have at most four adjacent pixels.

We denote the top left pixel to be (0,0). The indices increase towards the right and down. For instance, if we have an image of width 20 by 30, then the top-right pixel has the coordinate (0, 19); the bottom-left pixel has the coordinate (29, 0); and the bottom-right has the coordinate (29, 19).

An image can be divided into one or more segments. A segment is a set of pixels (i) with the same color, and (ii) given any two pixels \(p\) and \(q\) in a segment, we can find a series of adjacent pixels in the segment going from \(p\) to \(q\).

The fill operation takes in as an input the (\(x\),\(y\)) coordinate of a pixel \(p\), and a color \(c\) to fill. The operation then replaces the color of all pixels belonging to the same segment as \(p\) with the given color \(c\).

Write a program, fill.c, that reads from standard input two positive integers \(m\) and \(n\) in the first line. \(m\) refers to the number of rows, and \(n\) is the number of columns.

Then read \(3mn\) integers representing an \(m\) by \(n\) image from the standard inputs. Each tuple of 3 integers refers to the color of a pixel. The pixels are read from left to right, top to bottom. Thus, the first three integers refer to the color of the pixel at (0, 0); the next three integers refer to the color of the pixel at (0, 1), etc.

The next input is a positive integer \(q\), which is the number of fill operations. Following this, there are \(q\) lines. Each line has two integers \(x\), \(y\), and three integers, \(r\), \(g\), and \(b\), corresponding to a color. Each line specifies a fill operation, to fill the segmented pixel \((x, y)\) is in with the color \((r, g, b)\).

The program shall print to standard output, the image after executing all the given fill operations. The image should be printed in the following format:

  • The first line starts with a string "P3", followed by a space, followed by two integers, \(n\), and \(m\), that correspond to the width and height of the image. This is followed by a space, and then the number 255.
  • The remaining lines contain the color of each pixel, one color (i.e., three integers) per line. The pixels should be printed from left to right, top to bottom.

An example output: 

1
2
3
4
5
P3 2 2 255
0 0 0
0 10 79
140 120 30
50 30 255

You should use recursion to implement the fill operation.

Your solution must take no more than \(O(mnq)\) time.

You can visualize the resulting image using the viu command:

1
./fill < inputs/fill.3.in | ~cs1010/bin/viu -``

Note that viu might rescale your image if your terminal is too small.

Tips

Similar to social, your code would be simpler if you separate the representation of the image from the underlying 2D array. Writing functions to retrieve, update, and compare the color of a pixel of an image would make your code much simpler and easier to read, write, and debug.

Your solution must take no more than \(O(mnq)\) time to be categorized as "Excellent".

Question 2: Maze

Agent Scully woke up and found herself in the dark. She figured out that she was in a maze. She has to find her way out if there is one!

The maze can be simplified as a grid of (\(m \times n\)) cells. Each cell can be of the following:

  1. '#' denotes a segment of a wall. No one can pass through the walls.

  2. '.' denotes an empty space.

  3. '@' denotes where Scully is currently. It is also an empty space.

Anytime Scully reaches a border cell (a cell in either the top-most or bottom-most row or left-most or right-most column), she escapes the maze and can go save her partner Agent Mulder. She can only move from one empty space to another adjacent cell in one step. Two cells are adjacent if they share a common edge.

Scully took CS1010, and she got a concrete plan to seek a way out by trial and error. She follows strictly the following strategy to find a way through the maze starting from her initial position. At each time step,

  1. She looks for an empty adjacent cell that has never been visited yet, in the sequence of up/right/down/left to the current cell she is at. If there is an empty adjacent cell, she moves to that cell. The cell she moves to is now visited.

  2. If no empty, unvisited, adjacent cell exists, she backtracks on the path that she comes from, moving one step back, and repeats 1 again.

In this way, Scully systematically explores the maze, with no repetitive visit of any cell more than once except when she backtracks. She will stop when successfully escapes the maze, or finds that there is no way out after backtracking all the way back to the original position. She is completely trapped within the maze and now must wait for her partner Agent Mulder to come and free her.

Write a program maze.c, that reads from standard input. First, read two positive integers \(m\) and \(n\), followed by \(m\) lines of \(n\) characters in each line that represents the maze setup. One and only one @ will be present in the maze setup.

The program then prints, to standard output, an animation of \(k\) iterations. The output should only contain \(m\) rows with \(n\) characters in each row, with an additional row at last. Similarly, you must use # to represent a wall, a . to represent empty space, and @ to represent where Scully is at. After printing the maze, your program prints the number of steps that Scully has made.

You should use recursion to explore the maze and look for a way out.

Here is an example. The following is the starting position of Scully and the maze.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
###########
#.#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#.....#
#.#.##.#.##
#@#.#..#..#
#...#.#.#..
###########
0

Scully first moves five steps up: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
###########
#@#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#.....#
#.#.##.#.##
#.#.#..#..#
#...#.#.#..
###########
5

At this point, Scully is stuck since there is no more adjacent empty cell that has not been visited. Scully then backtracks: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
###########
#.#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#.....#
#.#.##.#.##
#@#.#..#..#
#...#.#.#..
###########
10

Scully then moves down: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
###########
#.#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#.....#
#.#.##.#.##
#.#.#..#..#
#@..#.#.#..
###########
11

Then right: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
###########
#.#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#.....#
#.#.##.#.##
#.#.#..#..#
#..@#.#.#..
###########
13

Then up: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
###########
#.#.....#.#
#.#####.#.#
#.#@..#.#.#
#.#.#.....#
#.#.##.#.##
#.#.#..#..#
#...#.#.#..
###########
17

Then right (two steps) and then down (two steps) and then right (two steps):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
###########
#.#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#..@..#
#.#.##.#.##
#.#.#..#..#
#...#.#.#..
###########
22

Then Scully moves up and left, and she is stuck again.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
###########
#.#@....#.#
#.#####.#.#
#.#...#.#.#
#.#.#.....#
#.#.##.#.##
#.#.#..#..#
#...#.#.#..
###########
29

At this point, she backtracks:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
###########
#.#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#..@..#
#.#.##.#.##
#.#.#..#..#
#...#.#.#..
###########
36

Moves right, and up, and stuck again!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
###########
#.#.....#@#
#.#####.#.#
#.#...#.#.#
#.#.#.....#
#.#.##.#.##
#.#.#..#..#
#...#.#.#..
###########
41
She backtracks again,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
###########
#.#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#...@.#
#.#.##.#.##
#.#.#..#..#
#...#.#.#..
###########
45

This time she found her way out!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
###########
#.#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#.....#
#.#.##.#.##
#.#.#..#..#
#...#.#.#.@
###########
50

It took her a total of 50 steps to exit the maze.

Your solution must take no more than \(O(mn)\) time to be graded as "Excellent".

Hint: You need to strictly follow the described strategy and sequence of exploration. Do not forget to print the initial maze and the final maze.

We have provided a function print_maze to draw the maze in the skeleton file.

Sample Run

You can use the sample program ~cs1010/ex07/maze on the given inputs to view the animation.

Note that how the maze is printed on the standard output is different from when it is written to a file.

Question 3: Walk

Many cities in the world, such as New York City, are laid out as a grid, with streets running in north-south directions and east-west directions. Buildings between two streets are called blocks.

Suppose we start at a junction of two streets, and we wish to walk to another junction that is \(y\) blocks to the north and \(x\) blocks to the east, how many possible paths are there to walk to the destination?

For example, suppose we want to walk to a junction that is one block to the north and one block to the east, and we can only walk eastward and northward, there are two possible paths. We can walk east for one block, then walk north for another block. Or, we can walk north first for one block, then walk east for another block.

The figure below illustrates the scenario, where we are positioned at source D and we wish to go to destination B. The two possible paths are DAB and DEB.

1
2
3
A---B---C
|   |   |
D---E---F

Suppose now we want to walk to C, a junction that is two blocks to the east, and one block to the north. There are three different possible paths. The three paths are DABC, DEBC, and DEFC.

Write a program walk that reads in two integers \(x\) and \(y\) \((x \ge 0, y >= 0)\), and prints the number of possible paths we can walk to the destination that is \(x\) block to the east and \(y\) block to the north.

Your solution must take no more than \(O(xy)\) time.

Hint: Think recursively, but solve iteratively.

Sample Runs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
ooiwt@pe111:~/as08-ooiwt$ walk
10 0
1
ooiwt@pe111:~/as08-ooiwt$ walk
1 1
2
ooiwt@pe111:~/as08-ooiwt$ walk
2 2
6
ooiwt@pe111:~/as08-ooiwt$ walk
20 20
137846528820

Question 4: Sudoku

This question is inspired by The Prime Minister of Singapore, Lee Hsien Loong, who once wrote a sudoku solver in C++:

In the game of sudoku, we are given a \(9 \times 9\) grid, with some of the cells filled with numbers 1 to 9. We must fill up the rest of the cells with 1 to 9, such that no number repeats itself in each row, in each column, and in each of the nine $3 \times 3$ subgrids.

Write a program, sudoku.c, that reads in a sudoku puzzle, and search for a solution to the puzzle, using the following algorithm:

  • Start from the top left, and scan left to right, top to bottom.

  • If an empty cell is encountered, try to fill it up with a digit, starting with 1, 2, .. until 9. For each digit we try, check if it is possible to find a solution, and if so, solve the updated puzzle recursively.

  • If a solution is found, print the solution and stop searching. Otherwise, (backtrack and) try a different digit, until either we have tried all digits or a solution is found.

The input to the program consists of 9 lines, 9 characters in each line, representing the puzzle. The input contains only the digits 1 to 9 and the . character, which represents the empty cell.

The output contains the steps of the search, printed with the print_sudoku function provided. At the end of the program, either the solution is printed or the string "no solution" if the sudoku cannot be solved.

Your code should take less than 5s to run for each test case given.

Sample Run

You can try to run the program ~cs1010/ex07/sudoku to see the animation of how the solution is expected to work.

Note that how the puzzle is printed on the standard output is different from when it is written to a file.