Description
Objectives & Intended Learning Outcomes
The objective of this assignment is to provide you with practice on arrays, functions, and recursion.0Upon completion of this assignment, you should be able to:
-
Define and use arrays to store data
-
Modularize your program in functions
-
Develop recursive functions to solve computational problems
End of Objectives & Intended Learning Outcomes
“Nonograms” are picture logic puzzles in which cells in a grid must be colored0or left blank according to numbers at the
side of the grid to0reveal a hidden pixel art-like picture. 0
Source:0https://en.wikipedia.org/wiki/Nonogram#/media/File:Nonogram_wiki.svg
Introduction
The goal of this assignment is to implement a text-based “Nonogram” game. You can check this0Wikipedia link here0for a historical overview of this genre of games.
11/25/22, 9:49 PM COMP 2012H Assignment 3: Nonogram
Nonogram is like “a combination of Minesweeper” and “Sudoku”. Each cell on the board must be0colored or left blank according to numbers at the side of the board (we call them0″row constraints” and “column constraints”)0to reveal a hidden pixel art-like picture.
The numbers (i.e., “row constraints” and “column constraints”)0measures how many unbroken lines of filled-in squares there are in any given row or column.0For example, a constraint of “4 8 3” would mean there are sets of four, eight, and three0filled squares, in that order, with at least one blank square0between successive sets.0You may check the banner above to see how constraints work.0That banner is a solved nonogram.
In this assignment, you are required to:
Implement the game mechanisms outlined in Tasks 1 – 4.
Implement a solver, which generate a Nonogram solution0(or any, if there are multiple solutions) that satisfies0all the constraints (Tasks 5 – 9).
End of Introduction
Description
Please read the FAQ section for some common clarifications. You should check that0a day before the deadline to make sure you don’t miss any clarification, even if you have already submitted your work by then.
Gameplay
During each round, the game interface displays a menu asking the user to select an action:
p (print) – print the current board
m (modify) – user set/unset (color/leave blank) a certain cell
c (check) – check if the current board is a valid solution
s (solve) – invoke Nonogram solver to solve the game
q (quit) – quit the game and ends the program
Solver
You are required to write a solver that (most likely) uses recursion.0Please refer to this paper about an overview of how the solver works.0You don’t need to know what is DFS or backtracking, just reading the process in0III. USING DFS TO SOLVE NONOGRAM PUZZLE is good enough.
Don’t worry if you are still confused about how to implement such an algorithm after0reading the paper. We will give you detailed instructions on0implementing some helper functions (Task 5 – 8), and we hope they will0help you come up with an idea about how to design a solver with the help of them.
During grading process, we ensure the board we input has only one valid solution.0So you don’t need to worry the cases when (1) there is no solution, or0(2) there are multiple solutions. When you are implementing the solver, you may choose0either to (1) quit after finding one solution, or (2) quit after finding all solutions.0However, we suggest you do the former, since if your solver takes too much time during0execution, you may lose some scores.
Global variables
Since some variables that representing game states will be used in many functions,0we make them global for simplicity. Here are a list of them:
Global Constants: (defined at the beginning)
11/25/22, 9:49 PM COMP 2012H Assignment 3: Nonogram
const int MAX_ROW = 15, MAX_COL = 15, MAX_CONSTRAINT_NUM = 150- maximum
number of rows/columns/constraints of the game board in this assignment.
For game board: (defined at the beginning)
int num_rows, num_cols – number of rows / columns in the game board.
char board[MAX_ROW][MAX_COL] – the game board represented by a 2D character array,
-
means the cell is left blank,0‘X’ means colored.
int num_row_constraints[MAX_ROW], num_col_constraints[MAX_COL] -0number of constraints for each row / column. For example, if0row 0 has constraint “4 3 5”, then num_row_constraints[0] = 3.0This actually records the length of0int row_constraints[][], col_constraints[][] below.
int row_constraints[MAX_ROW][MAX_CONSTRAINT_NUM],0col_constraints[MAX_COL] [MAX_CONSTRAINT_NUM] -0row / column constraints. For each row / column, there are multiple numbers in its constraint, so we need an array to store it.0The length of array is stored in0int num_row_constraints[], num_col_constraints[]0introduced above.
For solver: (defined after Task 6)
int num_row_perms[MAX_ROW] – number of valid permutations for each row.
char row_perms[MAX_ROW][MAX_PERM][MAX_COL] -0stores all valid permutations for each row.0For example, char row_perms[i][j][k] represents0for row i, in the j-th valid permutation,0whether the cell at column k is colored or left blank.
Additional Remarks
You are allowed to define your own helper functions, but be careful as ZINC won’t be able to know0of their existence. This shouldn’t be a problem as long as the changes to the game state variables0and task function return values are as expected.
All the task functions are in global scope, and you are allowed to have the task functions call0each other for easier implementation. Be careful when two or more functions call each other0reciprocally, as they may enter an infinite loop.
You are free (but not strictly required) to use recursion in any of the task functions. Some recursion hints are given in the tasks, but otherwise the final decision is up to you. Avoid accidental infinite recursion.
You are only allowed to use one header file #include <iostream>.
You are strongly discouraged to modify the main function given in0skeleton. It will be replaced when we grade your program.0You are strictly forbidden to modify the signature of task functions.0However, you can overload them. When we grade your program, if we cannot find0the exact function whose signature is what we described in Tasks section, you will have no score for that task.0This situation is unlikely to occur if you never modified the main function.
End of Description
Tasks
This section describes the functions that you will need to implement.0Please refer to the main function given in0skeleton to see how they are invoked.
Part I: Initialize the board.
Task 1 – Implement the get_input_board() function
Description – This function asks user to input the board size and constraints,0check if the constraints are valid,0store the information in global variables and finally initialize the board.
Read constraints – The function will ask user to input constraints0row by row, and then column by column. For each row / column, user need to0input a list of numbers, separated by a space, to indicate the constraint for0this row / column. Since the constraint can be of any length, the user will0enter -1 at the end, meaning that the constraint for this row / column0is ended. If there is no constraint for this row / column, the user should0simply enter -1. You may refer to the example below for details.
11/25/22, 9:49 PM COMP 2012H Assignment 3: Nonogram
Validity checking – It is not easy to check if the constraints are valid, for example,0you may think if the constraints result in no solution, they are invalid. However,0in current stage we are unable to check such complex stuff. So in this function,0you only need to check if the row / column has enough space to possibly0hold such constraints. For example, if a row constraint is “4 3 5”, since0two adjacent groups require at least 1 blank cell between, we at least need04 + 1 + 3 + 1 + 5 = 14 cells in this row. Hence, if num_cols0is smaller than 14, this is invalid. You only need to check this situation.
void get_input_board();
Notes
You may assume the user always input a valid integer for number of rows / columns,0i.e., an integer between 1 and MAX_ROW / MAX_COL.
You may assume the user always input positive integers for row / column constraints, except for the -1 used to flag input termination.
You may assume the number of user input row/column constraints never exceeds the number of the row/columns, e.g.,0if the board size is 3 row by 4 col, the user will input ≤ 3 row constraints for each row and ≤ 4 column constraints.
If the constraints input by user is not valid, this function will0tell the user “Invalid row / column constraint, please try again.”, and0keep asking user to re-input the constraint. Some code snippets have been given for you in the skeleton.0You may directly use them for output format.
Example: (user input is highlighted in red)0Note that this is just an example, this board may have no solution.
Enter the number of rows: 30
Enter the number of columns: 40
Enter the number of constraints for row 0 (end with -1): -10
Enter the number of constraints for row 1 (end with -1): 1 1 -10
Enter the number of constraints for row 2 (end with -1): 1 1 1 -10 Invalid row constraint, please try again.0
Enter the number of constraints for row 2 (end with -1): 1 3 -10 Invalid row constraint, please try again.0
Enter the number of constraints for row 2 (end with -1): 2 1 -10
Enter the number of constraints for column 0 (end with -1): 1 1 1 -10 Invalid column constraint, please try again.0
Enter the number of constraints for column 0 (end with -1): 1 2 -10 Invalid column constraint, please try again.0
Enter the number of constraints for column 0 (end with -1): 2 -10
Enter the number of constraints for column 1 (end with -1): 1 -10
Enter the number of constraints for column 2 (end with -1): -10 Enter the number of constraints for column 3 (end with -1): 1 1 -10 [Then this function ends, program will print the board. Remaining parts are ignored.]
Task 2 – Implement the print_board() function
Description – This function prints the board and the constraints for each row and column. Constraints should be printed at the bottom of each column (top-aligned) and0on the left of each row (right-aligned).0We will also output row / column index for each row / column.0Row indices are numbered in 0, 1, 2, …, while column indices are numbered in A, B, C, … .0Please note that to distinguish row indices and row constraints,0we will print an extra | between each row index and its constraints.0You may refer to the example below for details.
void print_board();
Notes
11/25/22, 9:49 PM COMP 2012H Assignment 3: Nonogram
Each cell, or each number in constraint, or each index in the same row0is separated by a space, as shown in example below.
Each cell, or each number in constraint, or each column index0occupies one character. However, each row index occupies two characters, and0they should be right-aligned, as shown in example below.
It’s ok to have trailing spaces at the end of each line.0We will ignore them during grading process.
You may assume constraints will never contain numbers larger than 9.0So they are always a single digit.
You may also assume there will be no more than MAX_ROW=15 rows and0MAX_COL=15 columns. The column indices are single characters ranging from0A to O. However, there can be more than 9 rows,0that’s why we said each row index needs to take 2 characters.
Example: (user input is highlighted in red)0Note that this is just an example, this board may have no solution.
-
-
Enter the number
of rows: 50
Enter the number
of columns: 50
Enter the number
of constraints for row 0 (end with -1): 2 2 -10
Enter the number
of constraints for row 1 (end with -1): 2 2 -10
Enter the number
of constraints for row 2 (end with -1): -10
Enter the number
of constraints for row 3 (end with -1): 1 1 -10
Enter the number
of constraints for row 4 (end with -1): 3 -10
Enter the number
of constraints for column 0 (end with -1): 2 1 -10
Enter the number
of constraints for column 1 (end with -1): 2 1 -10
Enter the number
of constraints for column 2 (end with -1): 1 -10
Enter the number
of constraints for column 3 (end with -1): 2 1 -10
Enter the number
of constraints for column 4 (end with -1): 2 1 -10
ABCD
E0
2 2 |
0….
.0
2 2 |
1….
.0
-
-
-
2…..0 11| 3…..0 3| 4…..0 221220 11 110
-
[Then program will print menu, as shown in main function. Remaining parts are ignored.]
Another example: when there are more than 9 rows. Here user inputs are ignored0and only shows the board.
ABCDEFGHIJKL0
2124| 0…………0
52| 1…………0
1131| 2…………0
223| 3…………0
413| 4…………0
118| 5…………0
2111| 6…………0
1223| 7…………0
54| 8…………0
211| 9…………0
26|10…………0
3113|11…………0
1122343216210
5221613112720
-
-
-
-
-
1313
11312120
2
1
1
2
1
10
1
-
-
-
-
11/25/22, 9:49 PM COMP 2012H Assignment 3: Nonogram
Part II: User play on board.
Task 3 – Implement the user_operate_board() function
Description – This function will be called when user choose to set/unset a cell.0It will:
-
Ask user to input which cell he/she wants to modify.0The user will need to first enter the column index, followed0by a space, and then the row index. For example, “A 2”.0You may always assume user will first enter a capital letter,0followed by a space, and then an integer.
-
Check if the user input is a valid cell(i.e., it is within the board).0If invalid, keep asking the user to input until a valid cell is received.
-
Set / unset (color / leave blank) the cell.0If the cell was set before, then unset it, and vice versa.
void user_operate_board();
Example: (user input is highlighted in red,0and original board is highlighted in blue.)0Note that this is just an example, this board may have no solution.
11/25/22, 9:49 PM COMP 2012H Assignment 3: Nonogram
Description – This function will be called after user finish filling the whole board.0You need to check whether his/her solution is correct,0i.e., satisfy all constraints.0You don’t need to print the result, it has been handled in0main() function in the skeleton.
bool check_whole_board_valid();
Return value – true, if the solution is correct,0false, otherwise.
Example: (user input is highlighted in red,0and original board is highlighted in blue.)
11/25/22, 9:49 PM COMP 2012H Assignment 3: Nonogram
11/25/22, 9:49 PM COMP 2012H Assignment 3: Nonogram
Enter ‘c’ to check your solution.0
Enter ‘s’ to invoke solver.0
Enter ‘q’ to quit.0
Your choice: m0
Enter the cell you want to modify (e.g. A 2): A 3
-
Welcome to Nonogram Game =====0
Please enter your choice:0
Enter ‘p’ to print the current board.0 Enter ‘m’ to modify a cell.0
Enter ‘c’ to check your solution.0 Enter ‘s’ to invoke solver.0 Enter ‘q’ to quit.0
Your choice: c0
Congratulations! Your solution is correct!
Part III: A nonogram solver.
Please make sure you have read the paper in description section0about how we are going to implement the solver.
Basically, the steps are:
-
For each row, choose one permutation and fill it on the board
-
Check if current board does not violate column constraints.0(It cannot violate row constraints, since we used a valid row permutation)
If not violate, proceed on next row, until all rows are filled
If violate, go to step 1, choose another permutation
Now the problems are: (1) how to generate permutations for each row,0and (2) how to check a board does not violate column constraints. Notice here0the board is incomplete.
For generating permutations, we can first generate a left-aligned permutation as0a starter. For example, if the row constraint is {2, 1, 3}, and0there are 12 columns, then a left-aligned permutation is:0[X X . X . X X X . . . .], i.e., start filling cells from left most,0and separate each group by only one empty cell.
Then, to generate other permutations based on the starter, we check0if any group can be shifted to the right. In the example above, the last group0can be shifted to the right by 1, 2, 3, or 4 cells (more shifts will hit the boundary),0which will produce 4 other permutations.0And after the last group is shifted, you may also check0if the second group can be shifted. For example, when the last group is shifted0by 2 cells, the second group can be shifted to the right by 1 or 2 cells.0(more shifts will hit the last group)0The same process should be done on the first group. In this way you are able0to generate all permutations for a row.
Task 7 asks you to generate all permutations for a certain row,0and Task 6 asks you to check if a certain group can be shifted, as we described above.0Task 5 acts as a useful helper function, since it’s convenient for us to only0focus on which column does each group start, rather than how the row really looks like.
For checking whether current board violates column constraints, it is similar to what0we have done in check_whole_board_valid(), except for
We don’t need to check the row constraints, since the row permutations we generated must0not violate row constraints.
We don’t check the whole board. The board is not complete yet, we only need to check the rows that we have finished.
You will be asked to implement this function in Task 8.
Finally, you will be asked to implement the complete solver in Task 9.0We expect you to make use of those previous functions that you have written.
11/25/22, 9:49 PM COMP 2012H Assignment 3: Nonogram
you need to be careful that you always pass in valid parameters0when you invoke it in other functions.
Task 7 – Implement the get_row_perms() function
Description – This function gets all valid permutations for a row,0and store all results in global variables row_perms0and num_row_perms. See description section0for explanations about global variables used here.
Hint: you may use recursion. First generate a starter permutation,0then try to shift each of the groups on that row, in order to produce0other permutations. See instructions before Task 5 for more details.
void get_row_perms(int row_idx);
Parameters
int row_idx – which row we will generate permutations for.
Notes
You may assume the parameters passed into this function are always valid0during grading process. However, since this function is used as a helper function0in later tasks, you need to be careful that you always pass in valid parameters0when you invoke it in other functions.
Task 8 – Implement the check_rows_valid() function
Description – This function checks if current state is valid, after0we finish filling
num_complete_rows rows.0For example, if num_complete_rows = 2, it will only check0if the first two rows (with index 0 and 1) do not break column constraints.
As we have discussed before, this function is similar to what0we have done in check_whole_board_valid(), except for
We don’t need to check the row constraints, since the row permutations we generated must0not violate row constraints.
We don’t check the whole board. The board is not complete yet, we only need to check the rows that we have finished.
bool check_rows_valid(int num_complete_rows);
Parameters
int num_complete_rows -0how many rows have we completed. We will only check those rows.
Return value – true, if the current board state is valid;0false, otherwise.
Notes
You may assume the parameters passed into this function are always valid0during grading process. However, since this function is used as a helper function0in later tasks, you need to be careful that you always pass in valid parameters0when you invoke it in other functions.
Task 9 – Implement the solve() function
Description – This function will solve the board, and store the solution0into global variable board directly.0You may assume there are only one solution for the board given.
Hint: you may use recursion. Choose a permutation for first row,0check if the current board is valid: if so, proceed on next row, otherwise,0choose another permutation. End recursion when we have finished0filling the last row.0See instructions before Task 5 for more details.
11/25/22, 9:49 PM COMP 2012H Assignment 3: Nonogram
void solve();
Notes
You may assume the given game has only one solution0during grading process. However, when you are testing your own board / constraints,0the board may have 0 / 1 / more than 1 solutions.
Example: (user input is highlighted in red,0and original board is highlighted in blue.)
ABCDE0
22| 0…..0
22| 1…..0
-
-
2…..0 11| 3…..0 3| 4…..0 221220
-
11 110
-
Welcome to Nonogram Game =====0
Please enter your choice:0
Enter ‘p’ to print the current board.0 Enter ‘m’ to modify a cell.0
Enter ‘c’ to check your solution.0 Enter ‘s’ to invoke solver.0 Enter ‘q’ to quit.0
Your choice: s0 Generating solution:0
ABCDE0 22| 0XX.XX0 22| 1XX.XX0 | 2…..0 11| 3X…X0 3| 4.XXX.0 221220
11 11
End of Tasks
