[Optional Extension] Assignment 3 - Drawing Shapes

Due: Thursday, May 23, 2024, at 10pm

This assignment is completely optional. If you receive at least 80% of the points, you will gain one extra token. If you receive at least 50% of the points (but not quite 80%), you will gain half of an extra token.

You may work alone or with a partner, but you must type up the code yourself. You may also discuss the assignment at a high level with other students. You should list any student with whom you discussed each part, and the manner of discussion (high-level, partner, etc.) in a comment at the top of each file. You should only have one partner for an entire assignment.

If you worked with a partner for the base version of this assignment, you may not work with another partner for the extension unless neither of you plans to resubmit the base version.

You should submit your assignment as an a3_opt.zip file on Moodle.

Parts of this assignment:

Comments and collaboration

As with all assignments in this course, for each file in this assignment, you are expected to provide top-level comments (lines that start with # at the top of the file) with your name and a collaboration statement. For this assignment, you have multiple programs; each needs a similar prelude.

You need a collaboration statement, even if just to say that you worked alone.

Note on style:

The following style guidelines are expected:

  • Variable names should be clear and easy to understand, should not start with a capital letter, and should only be a single letter when appropriate (usually for i, j, and k as indices, potentially for x and y as coordinates, and maybe p as a point, c for a circle, r for a rectangle, etc.).
  • It’s good to use empty lines to break code into logical chunks.
  • Comments should be used for anything complex, and typically for chunks of 3-5 lines of code, but not every line.
  • Don’t leave extra print statements in the code, even if you left them commented out.
  • Make sure not to have code that computes the right answer by doing extra work (e.g., leaving a computation in a for loop when it could have occurred after the for loop, only once).

Note: The example triangle-drawing program on page 108 of the textbook demonstrates a great use of empty lines and comments, and has very clear variable names. It is a good model to follow for style.

Getting started

For Part 1, you’ll copy your randomPieces.py program from Assignment 3 to a new file named nRooks.py.

For Parts 2 and 3, this assignment comes with starter code. You can copy-paste it into a new file in VS Code – just save it as verifyNQueens.py.

You will implement two functions in this file; the rest of the code is there to help test your implementations. Try running it to see what tests it will perform:

Performing positive N-Rooks tests.
Passed 0 out of 100 tests (n=0).
Passed 0 out of 100 tests (n=1).
Passed 0 out of 100 tests (n=2).
Passed 0 out of 100 tests (n=3).
Passed 0 out of 100 tests (n=4).
Passed 0 out of 100 tests (n=5).
Passed 0 out of 100 tests (n=6).
...

Part 1: Placing Rooks

In this part, you should extend your randomPieces.py program from Assignment 3 to make sure that no two pieces are in the same column. The rest should be the same. Save your program in a file called nRooks.py.

Hint: Think carefully about how you can store the location of each piece – you need one piece per row. Perhaps there is a good data structure that would hold a bunch of information, say maybe for each row, the column of the piece. You could then randomly generate that information in such a way that the columns are assigned randomly…

Here is a possible output:

<image: placing checkers pieces as rooks>

Part 2: N-Rooks

In this part, you will implement a function that checks if a given board state satisfies the “N-Rooks Problem”. That is, it checks whether no two pieces are in the same row or column (and thus whether they’d threaten each other if they were rooks in a game of chess).

The board state is represented as a list of lists (another nested list). The function doesSatisfyNRooks takes a parameter boardState that contains one list per row. Each inner list contains one value per cell within that row. The value is 0 if no piece is placed there, and 1 if there is a piece placed there.

def doesSatisfyNRooks(boardState):
    """
    Checks whether the given state of the board satisfies N-Rooks.
    If no two pieces are in the same row or column, returns True.
    Otherwise, returns False.

    boardState: a nested lists containing 0s (no piece) and 1s (a piece)
    
    returns: True or False
    """
    # TODO: Part 2
    return False # replace with your code

This assignment comes with some tests that will help you verify whether your code works. Although you don’t have to fully understand how the tests work, they can be helpful for getting a feel for the expected results.

Once you have implemented doesSatisfyNRooks, the first two tests should pass. The positive tests will all pass, but the negative tests will pass more frequently with increasing n. This is because the negative tests randomly generate a board setup, and it might satisfy N-Rooks, but this becomes less likely as the board becomes larger.

Performing positive N-Rooks tests.
Passed 100 out of 100 tests (n=0).
Passed 100 out of 100 tests (n=1).
Passed 100 out of 100 tests (n=2).
Passed 100 out of 100 tests (n=3).
Passed 100 out of 100 tests (n=4).
Passed 100 out of 100 tests (n=5).
Passed 100 out of 100 tests (n=6).
Passed 100 out of 100 tests (n=7).
Passed 100 out of 100 tests (n=8).
Passed 100 out of 100 tests (n=9).
Passed 100 out of 100 tests (n=10).

Performing negative N-Rooks tests.
(Note that not all will pass, but the number should go up as n increases.)
Passed 0 out of 100 tests (n=0).
Passed 0 out of 100 tests (n=1).
Passed 39 out of 100 tests (n=2).
Passed 75 out of 100 tests (n=3).
Passed 91 out of 100 tests (n=4).
Passed 98 out of 100 tests (n=5).
Passed 99 out of 100 tests (n=6).
Passed 100 out of 100 tests (n=7).
Passed 100 out of 100 tests (n=8).
Passed 100 out of 100 tests (n=9).
Passed 100 out of 100 tests (n=10).

Part 3: N-Queens

For this part, you will implement the function doesSatisfyNQueens. The logic for the “N-Queens Problem” is a bit more complex. The function should only return True if no two pieces are placed in the same row, column, or diagonal.

For example, the board state on the left below would satisfy N-Queens, as the bottom two pieces are in the same diagonal. However, the board state on the right would satisfy N-Queens.

<image: N-Queens>

def doesSatisfyNQueens(boardState):
    """
    Checks whether the given state of the board satisfies N-Queens.
    If no two pieces are in the same row, column, or diagonal,
    returns True.  Otherwise, returns False.

    boardState: a nested lists containing 0s (no piece) and 1s (a piece)
    
    returns: True or False
    """
    # TODO: Part 3
    return False # replace with your code

Again, there are test functions available to help you verify your code works. As with N-Rooks, the positive tests for N-Queens should all pass. The negative tests all generate random board configurations, and assume it is unlikely that they will pass N-Queens. Therefore, more will pass as n increases.

Performing positive N-Queens tests.
Passed 1 out of 1 test (n=0).
Passed 1 out of 1 test (n=1).
Passed 1 out of 1 test (n=2).
Passed 1 out of 1 test (n=3).
Passed 1 out of 1 test (n=4).
Passed 1 out of 1 test (n=5).
Passed 1 out of 1 test (n=6).
Passed 1 out of 1 test (n=7).
Passed 1 out of 1 test (n=8).
Passed 1 out of 1 test (n=9).
Passed 1 out of 1 test (n=10).

Performing negative N-Queens tests (assuming N-Rooks passes).
(Note that not all will pass, but the number should go up as n increases.)
Passed 0 out of 100 tests (n=0).
Passed 0 out of 100 tests (n=1).
Passed 51 out of 100 tests (n=2).
Passed 53 out of 100 tests (n=3).
Passed 83 out of 100 tests (n=4).
Passed 80 out of 100 tests (n=5).
Passed 85 out of 100 tests (n=6).
Passed 98 out of 100 tests (n=7).
Passed 97 out of 100 tests (n=8).
Passed 97 out of 100 tests (n=9).
Passed 100 out of 100 tests (n=10).

Performing negative N-Queens tests (likely fails N-Rooks).
(Note that not all will pass, but the number should go up as n increases.)
Passed 0 out of 100 tests (n=0).
Passed 0 out of 100 tests (n=1).
Passed 58 out of 100 tests (n=2).
Passed 83 out of 100 tests (n=3).
Passed 100 out of 100 tests (n=4).
Passed 100 out of 100 tests (n=5).
Passed 100 out of 100 tests (n=6).
Passed 100 out of 100 tests (n=7).
Passed 100 out of 100 tests (n=8).
Passed 100 out of 100 tests (n=9).
Passed 100 out of 100 tests (n=10).

Reflection

Did you learn anything additional that you find interesting? Were there any particular issues or challenges you dealt with in completing this assignment? How long did you spend on this assignment? Write a brief discussion (a sentence or two is fine) in your readme.txt file.

Grading

This assignment will be graded out of 100 points, as follows:

  • 5 points - submit a valid a3_opt.zip file with all files correctly named

  • 5 points - all code files contain top-level comments with file name, purpose, and author names

  • 5 points - each code files’ top-level comments contain collaboration statement

  • 10 points - code style enables readable programs

  • 20 points - nRooks.py program draws pieces on the board satisfying the N-Rooks Problem

  • 40 points - verifyNRooks.py tests whether a board configuration satisfies the N-Rooks Problem

  • 10 points - verifyNQueens.py tests whether a board configuration satisfies the N-Queens Problem

  • 5 points - readme.txt file contains reflection

What you should submit

You should submit a single a3_opt.zip file on Moodle. It should contain the following files:

  • readme.txt (reflection)
  • nRooks.py (Part 1)
  • verifyNQueens.py (Parts 2 and 3)