p3-0hh1

EECS 183 Project 3: 0hh1

Project Due Friday, October 23, 2020, 11:59 pm Eastern

game-pic

In this project, you will develop a command-line application to read, check, solve, and play basic instances of 0h h1, a Sudoku-like puzzle game.

By completing this project, you will learn to:

You will apply the following skills you learned in lecture:

Getting Started

Overview Video

Here is a project overview video that summarizes how to get started with the project:

Starter Files

Begin by heading over to 0hh1.com and playing the game to gain familiarity with the rules.

After downloading the distribution code at this link, you’ll find these files:

FileRoleWhat you will do
ohhi.cppContains the functions you will implement for this project. Implement stubs, submit to autograder
test.cppContains the test cases for your project. Implement test cases, submit to autograder
ohhi.hContains the RMEs and declarations for the functions you will implement in ohhi.cpp. Do not modify or submit
utility.h, utility.cppContains helper functions you may call in your code. Do not modify or submit
driver.h, driver.cpp, main.cpp, color.h, color.cpp, main.cpp Code that calls your functions to play the 0hh1 game. Do not modify or submit
start.cpp Code that includes the main function. Use this to choose between playing 0hh1 or running your tests. Do not modify or submit

We recommend you write one function at a time. Similar to P2, the best strategy is to write test cases in test.cpp for a function, then write the function in ohhi.cpp.

Submission and Grading

Submit your code to the autograder here. You receive 10 submits each day and your best overall submission counts as your score. You will submit two files, which must be called ohhi.cpp and test.cpp.

The deadline is Friday, October 23, 2020 at 11:59PM Eastern. If your last submission is on Wednesday, October 21 by 11:59PM, you will receive a 5% bonus. If your last submission is on Thursday, October 22 by 11:59PM, you will receive a 2.5% bonus.

Here is a grade breakdown:

Working with a Partner

Multiple Files

Suggested Timeline

You will be approximately on track for this project if you follow this timeline:

Collaboration Policy

We want students to learn from and with each other, and we encourage you to collaborate. We also want to encourage you to reach out and get help when you need it. You are encouraged to:

To clarify the last item, you are permitted to look at another student’s code to help them understand what is going on with their code. You are not allowed to tell them what to write for their code, and you are not allowed to copy their work to use in your own solution. If you are at all unsure whether your collaboration is allowed, please contact the course staff via the admin form before you do anything. We will help you determine if what you’re thinking of doing is in the spirit of collaboration for EECS 183.

The following are considered Honor Code violations:

The full collaboration policy can be found in the syllabus.

Solution Overview

Problem Statement

Like Sudoku, 0h h1 is a popular puzzle game in which the goal is to find a valid coloring of the game board without violating a particular set of constraints. Instead of filling in the numbers 1 through 9, in 0h h1 we simply use squares of either RED or BLUE, as shown above.

In 0h h1, there are three rules that define a valid board:

  1. Equal representation. Each row and column must have the same number of red and blue squares.
  2. Runs of three or more are not allowed. There may not be more than two consecutive squares of the same color either horizontally or vertically.
  3. No duplicates. No two rows can be the same, nor two columns.

Note that rules 1 and 3 only apply to a completed board. For instance, it is possible for a partially completed, valid board to have two duplicate rows with unknown squares, since they could be filled in such a way that the final board has no duplicates. Similarly, a partially filled row does not have to have the same number of RED squares as BLUE squares.

The first sections of your program will check partially-completed 0h h1 boards to ensure that they adhere to these rules. You will then develop algorithms to solve 0h h1 puzzles. Finally, you will implement functions that allow a user to play 0h h1.

For this project, you will write a checker, a solver, and gameplay functions for 0h h1.

You do not need to write a driver for 0h h1. Since we want you to concentrate on the more interesting parts of the program, we have implemented the driver for you in start.cpp and main.cpp; see Running with start.cpp below for the details. We strongly recommend that you hold off on using the driver to run 0h h1 until you have completed and thoroughly tested each function you have to write. Instead, write tests in test.cpp to test each function and use the driver to run those tests first.

Counter

The first function you write, count_unknown_squares(), will traverse and count the number of UNKNOWN squares in an 0h h1 board, stored in a 2-dimensional array of proportions MAX_SIZE x MAX_SIZE. This function will serve as a stepping stone to the more involved array functionality of the next two sections.

NOTE: In utility.h, we have defined several global constants (UNKNOWN, RED, and BLUE) which represent the color of a square–please use them when checking or manipulating the contents of a board.

NOTE: The size of the board is passed in as the size argument in every function you will write. The board is assumed to be square, so size is the size in both dimensions. size may be less than or equal, but no more than, MAX_SIZE.

Checker

In this section of the project, you will design algorithms to verify 2 of the 3 rules of 0h h1. (The first rule has already been written for you as an example: board_is_balanced() in driver.cpp.)

Solver

So that you are able to focus on the most interesting portions of this section, we have implemented some of the “structural” pieces of the solver for you. The main portion of our pre-written code is contained in the solve() function, found in driver.cpp. This function reads in an 0h h1 puzzle and attempts to solve it by calling several key functions, which we have generously left blank for you to implement at your leisure. These functions are as follows:

solve_three_in_a_row() and solve_three_in_a_column() will identify certain instances of squares which cannot be assigned one of the colors and therefore must be assigned the opposite; for instance, a square with BLUE squares on either side cannot be assigned BLUE without violating the rule of no consecutive threes in a row or column, and therefore must be designated as RED.

solve_balance_row() and solve_balance_column() will look at the given row or column to determine if exactly half the squares are RED or exactly half the squares are BLUE. Since by the rules of 0h h1 a row or column must have equal parts RED and BLUE squares, these functions will complete such a row or column using the underrepresented color.

All solver functions take in an announce argument, which controls whether or not mark_square_as() prints a message when a square is changed. (The solver is used both in solving a board and in generating one, and the announce parameter allows the former to announce each move without requiring the latter to print out lots of extraneous output giving away the solution.) Make sure to pass on announce when you call mark_square_as().

IMPORTANT: When marking a square a particular color, you must use the mark_square_as() function, which will also print out the steps as your program goes along if the announce argument is true. In order for your project to pass the Autograder’s tests, your functions must check columns from check from top to bottom within a column, and left to right within a row.

Gameplay

The final three functions you will write enable a user to play 0h h1 interactively. We have already written the gameplay driver for you in play_board(), found in main.cpp, and make_move(), found in driver.cpp, which read in user input for you. The three functions you are responsible for check the validity of user input, whether or not a move is legal, and whether the board is solved:

NOTE: You may find it useful to make a copy of the board in order to check whether or not a move is valid.

NOTE: check_valid_move() relies on your validity checks to be properly implemented, so we recommend writing it last.

Hints

Play the game here a couple times to make sure you understand the rules. If you get stuck, you can click on the eye at the bottom of the screen to get hints. We suggest playing several games on the 6×6 board, so you see a variety of positions and how the rules apply.

Most functions do not require nested loops, and none require more than two levels of nesting, which means you should think more carefully about what the function is doing if you find yourself writing a lot of nested loops. Examples of correct function outputs are in the RMEs, but here are some additional hints along with our suggested order for implementing the functions:

  1. count_unknown_squares()
  2. row_has_no_threes_of_color(), col_has_no_threes_of_color()
  3. board_has_no_threes()
  4. solve_balance_row(), solve_balance_column()
  5. rows_are_different(), cols_are_different() - Two rows/columns can only be the same if neither of them have UNKNOWN squares.
  6. board_has_no_duplicates()
  7. solve_three_in_a_row(), solve_three_in_a_column() - Be sure to not only check the case where there are two consecutive squares, but also the case where two squares are separated by a blank one! Also watch out for having two consecutive squares on the edge of the board. In order to satisfy the autograder, these two functions must only iterate over the given row or column once, from left to right or top to bottom. When considering a square, you must check all cases that may apply in these functions.
  8. board_is_solved()
  9. check_valid_input()
  10. check_valid_move()

To help you understand this project, and to give you an idea of the code you’ll be writing, driver.cpp implements the functions row_is_balanced, col_is_balanced, and board_is_balanced. Feel free to look at them for inspiration on how to write the remaining functions.

Additionally, these utility functions are written for you to use:

They are declared in utility.h and defined in utility.cpp.

Function Table

You will need to implement and test the following functions in ohhi.cpp. You do not need to implement or change any functions in files other than ohhi.cpp and test.cpp.

FunctionOther functions it should call
count_unknown_squaresDoes not utilize any other functions
row_has_no_threes_of_colorDoes not utilize any other functions
col_has_no_threes_of_colorDoes not utilize any other functions
board_has_no_threesrow_has_no_threes_of_color,col_has_no_threes_of_color
rows_are_differentDoes not utilize any other functions
cols_are_differentDoes not utilize any other functions
board_has_no_duplicatesrows_are_different,cols_are_different
solve_three_in_a_rowmark_square_as,opposite_color
solve_three_in_a_columnmark_square_as,opposite_color
solve_balance_rowmark_square_as,opposite_color
solve_balance_columnmark_square_as,opposite_color
board_is_solvedcount_unknown_squares,board_is_valid
check_valid_inputtoupper
check_valid_movecopy_board,board_is_valid

Testing

NOTE: A very good practice is to write tests before even implementing functions.

NOTE: We will run your test suite against buggy code to determine whether or not your tests are effective at identifying bugs.

void test_count_unknown_squares() {
    int board[MAX_SIZE][MAX_SIZE];

    // test case 1
    string test_board_1[] = {"O-OX",
                             "OO--",
                             "X---",
                             "-O--"};
    int size_1 = 4;
    read_board_from_string(board, test_board_1, size_1);
    cout << count_unknown_squares(board, size_1) << endl;

    // add more tests here
}

As the example illustrates, you can create a testing board by using the read_board_from_string() utility function.

IMPORTANT: Do not read from cin in your test code. The autograder will not provide any input to standard input, so you will fail the autograder if you attempt to read from cin.

IMPORTANT: Only write test cases in test.cpp for functions declared in ohhi.h. If you have helper functions you want to test, write test cases for those in a separate file (e.g. test2.cpp) with its own main(). We will be linking your test.cpp with our own ohhi.cpp, so it should only rely on functions declared in the distribution code or included in the standard C++ library.

WARNING: If you submit a test case that violates the Requires clause, we will stop grading that submission and you will receive a very low score.

Bugs To Expose

There are a total of 11 unique bugs to find in our implementations. Your tests will need to expose 7 of the bugs to receive full points for test.cpp. The autograder will tell you the names of the bugs that you have exposed, from the following set:

Running with start.cpp

Once you have completed test.cpp, you can use the included start.cpp to run your tests. Once you have completed ohhi.cpp, you can use the included start.cpp to play or solve a game.

IMPORTANT: Do NOT start by using start.cpp to play or solve a game by executing the ohhi() function in main.cpp. You will have to test your code to make sure it works, and you will need to eventually submit test.cpp. We strongly recommend that you write tests and test your code thoroughly by first using start.cpp to run your tests using the startTests() function in test.cpp before trying to run the game using the ohhi() function defined in main.cpp.

Here is an overview of the behavior of start.cpp, assuming a correct implementation of ohhi.cpp.

The initial menu allows you to choose between running ohhi() or running startTests(). Here is the initial menu:

-------------------------------
EECS 183 Project 3 Menu Options
-------------------------------
1) Execute testing functions in test.cpp
2) Execute ohhi() function in main.cpp
Choice -->

ohhi Menu

Inputting 2 executes ohhi(), which displays the game menu. The game menu allows you to solve a custom game, play a random game, or play a custom game. Here is the game menu:

Menu Options
------------
1) Play a random game
2) Play a custom game
3) Solve a custom game
4) Play a random game with colors
5) Play a custom game with colors

Input

board-example

When solving or a playing a custom game, the program requires you to input the board. The distribution file contains code that reads in a board, with the following notation:

Accordingly, the text notation below translates to the 0h h1 board above.

X-----
X----X
--O--X
--O---
X-----
---X--

Output

Given a board, the program will attempt to print out:

When solving a game, it will also attempt to print:

When playing a game, the board will continue to print out the state of the board, ask for a move, check if the move is valid and legal, and update the board if it is. This continues until the board is solved.

Printing the board

In this example, the user runs the program, chooses to solve a custom game, and then enters the following via standard input (cin), pressing Enter after each line:

X-----
X----X
--O--X
--O---
X-----
---X--

The program will repeat the board it was given, properly formatted for readability.

Your board is:
   A B C D E F
  =============
1| X - - - - - |1
2| X - - - - X |2
3| - - O - - X |3
4| - - O - - - |4
5| X - - - - - |5
6| - - - X - - |6
  =============
   A B C D E F

Assessing validity

The program then calls each of your Checker functions in turn to decide whether this board is valid and can be solved. If the board is valid and your functions work correctly, the program will state the following:

This board is balanced.
This board does not contain threes-in-a-row/column.
This board does not contain duplicate rows/columns.

Solving the puzzle

It will then begin attempting to solve the 0h h1 puzzle by using your algorithms:

This board is valid; solving...
looking for threes-in-a-row/column...
marking (3, A) as O
marking (2, C) as X
marking (5, C) as X
marking (1, F) as O
marking (4, F) as O
marking (2, B) as O
marking (3, B) as X
marking (5, B) as O
looking for rows/columns with half X/O...
marking (2, D) as O
marking (2, E) as O
marking (4, A) as O
marking (6, A) as O
looking for threes-in-a-row/column...
....(continued)

Printing the result

If everything goes well, your functions will eventually generate a complete solution, which will be presented as output. The program will use your count_unknown_squares() to determine when the solution is complete.

Solved!
   A B C D E F
  =============
1| X X O O X O |1
2| X O X O O X |2
3| O X O X O X |3
4| O X O X X O |4
5| X O X O X O |5
6| O O X X O X |6
  =============
   A B C D E F

Playing the game

Sample Runs

Here are some sample runs of the game with start.cpp, assuming a correct implementation of ohhi.cpp. User’s input is shown in red. You will want to use a diffchecker tool to compare your program with the sample outputs.

Sample Run #1

-------------------------------
EECS 183 Project 3 Menu Options
-------------------------------
1) Execute testing functions in test.cpp
2) Execute ohhi() function in main.cpp
Choice --> 2 
Menu Options
------------
1) Play a random game
2) Play a custom game
3) Solve a custom game
4) Play a random game with colors
5) Play a custom game with colors

Choice --> 3
What board do you want to solve?
X-----
X----X
--O--X
--O---
X-----
---X--

Your board is:
   A B C D E F
  =============
1| X - - - - - |1
2| X - - - - X |2
3| - - O - - X |3
4| - - O - - - |4
5| X - - - - - |5
6| - - - X - - |6
  =============
   A B C D E F

This board is balanced.
This board does not contain threes-in-a-row/column.
This board does not contain duplicate rows/columns.

This board is valid; solving...
looking for threes-in-a-row/column...
marking (3, A) as O
marking (2, C) as X
marking (5, C) as X
marking (1, F) as O
marking (4, F) as O
marking (2, B) as O
marking (3, B) as X
marking (5, B) as O
looking for rows/columns with half X/O...
marking (2, D) as O
marking (2, E) as O
marking (4, A) as O
marking (6, A) as O
looking for threes-in-a-row/column...
marking (4, B) as X
looking for rows/columns with half X/O...
marking (4, D) as X
marking (4, E) as X
looking for threes-in-a-row/column...
marking (5, D) as O
looking for rows/columns with half X/O...
looking for potential duplicate rows/columns...
marking (5, E) as X
marking (5, F) as O
marking (1, C) as O
marking (6, C) as X
looking for threes-in-a-row/column...
marking (6, B) as O
marking (6, E) as O
marking (3, E) as O
marking (6, F) as X
marking (3, D) as X
marking (1, E) as X
looking for rows/columns with half X/O...
marking (1, B) as X
marking (1, D) as O

Solved!
   A B C D E F
  =============
1| X X O O X O |1
2| X O X O O X |2
3| O X O X O X |3
4| O X O X X O |4
5| X O X O X O |5
6| O O X X O X |6
  =============
   A B C D E F

Sample Run #2

-------------------------------
EECS 183 Project 3 Menu Options
-------------------------------
1) Execute testing functions in test.cpp
2) Execute ohhi() function in main.cpp
Choice --> 2 
Menu Options
------------
1) Play a random game
2) Play a custom game
3) Solve a custom game
4) Play a random game with colors
5) Play a custom game with colors

Choice --> 3
What board do you want to solve?
O-XO-X-O
X---OO--
O-O--X-O
XOX---OX
--O--X--
XO---O--
XXOOX--O
O--O-X--

Your board is:
   A B C D E F G H
  =================
1| O - X O - X - O |1
2| X - - - O O - - |2
3| O - O - - X - O |3
4| X O X - - - O X |4
5| - - O - - X - - |5
6| X O - - - O - - |6
7| X X O O X - - O |7
8| O - - O - X - - |8
  =================
   A B C D E F G H

This board is balanced.
This board does not contain threes-in-a-row/column.
This board does not contain duplicate rows/columns.

This board is valid; solving...
looking for threes-in-a-row/column...
marking (2, D) as X
marking (2, G) as X
marking (3, B) as X
marking (5, A) as O
marking (5, B) as X
marking (6, C) as X
marking (6, D) as X
marking (4, F) as O
marking (2, H) as X
marking (4, E) as X
marking (6, E) as O
marking (6, G) as X
marking (4, D) as O
looking for rows/columns with half X/O...
marking (2, B) as O
marking (2, C) as O
marking (6, H) as O
marking (8, C) as X
marking (3, D) as X
marking (5, D) as X
marking (7, F) as O
marking (5, H) as X
marking (8, H) as X
looking for threes-in-a-row/column...
marking (3, E) as O
marking (5, E) as O
marking (5, G) as O
marking (7, G) as X
marking (8, G) as O
marking (1, E) as X
marking (3, G) as X
marking (1, G) as O
looking for rows/columns with half X/O...
marking (1, B) as X
marking (8, B) as O
marking (8, E) as X

Solved!
   A B C D E F G H
  =================
1| O X X O X X O O |1
2| X O O X O O X X |2
3| O X O X O X X O |3
4| X O X O X O O X |4
5| O X O X O X O X |5
6| X O X X O O X O |6
7| X X O O X O X O |7
8| O O X O X X O X |8
  =================
   A B C D E F G H

Sample Run #3

-------------------------------
EECS 183 Project 3 Menu Options
-------------------------------
1) Execute testing functions in test.cpp
2) Execute ohhi() function in main.cpp
Choice --> 2 
Menu Options
------------
1) Play a random game
2) Play a custom game
3) Solve a custom game
4) Play a random game with colors
5) Play a custom game with colors

Choice --> 2
What board do you want to solve?
X-
--

Your board is:
   A B
  =====
1| X - |1
2| - - |2
  =====
   A B

This board is balanced.
This board does not contain threes-in-a-row/column.
This board does not contain duplicate rows/columns.

This board is valid; solving...
   A B
  =====
1| X - |1
2| - - |2
  =====
   A B

Please enter your move (ROW COLUMN COLOR): 0 0 x
Read: 0 0 x
Sorry, that's not a valid input.

Please enter your move (ROW COLUMN COLOR): 1 A o
Read: 1 A o
Sorry, original squares cannot be changed.

Please enter your move (ROW COLUMN COLOR): 1 B o
Read: 1 B o

   A B
  =====
1| X O |1
2| - - |2
  =====
   A B

Please enter your move (ROW COLUMN COLOR): 2 a o
Read: 2 a o

   A B
  =====
1| X O |1
2| O - |2
  =====
   A B

Please enter your move (ROW COLUMN COLOR): 2 b x
Read: 2 b x

   A B
  =====
1| X O |1
2| O X |2
  =====
   A B

Congratulations, you've won!

Sample Run #4

-------------------------------
EECS 183 Project 3 Menu Options
-------------------------------
1) Execute testing functions in test.cpp
2) Execute ohhi() function in main.cpp
Choice --> 2 
Menu Options
------------
1) Play a random game
2) Play a custom game
3) Solve a custom game
4) Play a random game with colors
5) Play a custom game with colors

Choice --> 2
What board do you want to solve?
-X--
OOXX
XXOO
-O-X

Your board is:
   A B C D
  =========
1| - X - - |1
2| O O X X |2
3| X X O O |3
4| - O - X |4
  =========
   A B C D

This board is balanced.
This board does not contain threes-in-a-row/column.
This board does not contain duplicate rows/columns.

This board is valid; solving...
   A B C D
  =========
1| - X - - |1
2| O O X X |2
3| X X O O |3
4| - O - X |4
  =========
   A B C D

Please enter your move (ROW COLUMN COLOR): 4 a o
Read: 4 a o

   A B C D
  =========
1| - X - - |1
2| O O X X |2
3| X X O O |3
4| O O - X |4
  =========
   A B C D

Please enter your move (ROW COLUMN COLOR): 4 c x
Read: 4 c x
Sorry, that move violates a rule.

Please enter your move (ROW COLUMN COLOR): 4 c o
Read: 4 c o
Sorry, that move violates a rule.

Please enter your move (ROW COLUMN COLOR): 4 a -
Read: 4 a -

   A B C D
  =========
1| - X - - |1
2| O O X X |2
3| X X O O |3
4| - O - X |4
  =========
   A B C D

Please enter your move (ROW COLUMN COLOR): 4 a x
Read: 4 a x

   A B C D
  =========
1| - X - - |1
2| O O X X |2
3| X X O O |3
4| X O - X |4
  =========
   A B C D

Please enter your move (ROW COLUMN COLOR): 4 c o
Read: 4 c o

   A B C D
  =========
1| - X - - |1
2| O O X X |2
3| X X O O |3
4| X O O X |4
  =========
   A B C D

Please enter your move (ROW COLUMN COLOR): 1 a o
Read: 1 a o

   A B C D
  =========
1| O X - - |1
2| O O X X |2
3| X X O O |3
4| X O O X |4
  =========
   A B C D

Please enter your move (ROW COLUMN COLOR): 1 c x
Read: 1 c x

   A B C D
  =========
1| O X X - |1
2| O O X X |2
3| X X O O |3
4| X O O X |4
  =========
   A B C D

Please enter your move (ROW COLUMN COLOR): 1 d o
Read: 1 d o

   A B C D
  =========
1| O X X O |1
2| O O X X |2
3| X X O O |3
4| X O O X |4
  =========
   A B C D

Congratulations, you've won!

Style

Your code must follow the EECS 183 style guide.

Style Rubric

Top Comment

Must have name, uniqname, program name, and project description at the top of the file.

If all or part of the top comment is missing, take 1 point off.

Readability violations

-1 for each of the following:

Indentations

Spacing

Bracing

Variables

Line limit

Statements

Comments

RMEs

Coding quality

-2 for each of the following:

Global variables

Magic numbers

Egregious code

Function misuse

bools