HW 5:
n-Queens checker

Submission Details

Due before your lab session: 3/30 or 3/31 - Set up VSCode

Due: 4/1 - Submit via Gradescope:

2 files in total

• n_queens_checker.py

• A PDF that contains your self-assessment & reflection

Part 1: Install and set up VSCode

To prepare for lab, if you plan on using your own personal computer to develop code, be sure to have installed and set up VS Code.

Part 2: Develop a checker for the n-Queens problem

• You'll be creating a program in a file that must be named (EXACTLY, no spaces, respecting capitalization):

• • n_queens_checker.py

• Review the solutions to perform a self-assessment and write your reflection.

  • You may write up your self-assessment and reflection in whatever format is most comfortable for you (written on paper, typed in a Word or Google Doc, etc.), but you must convert it to a PDF before submitting. Please ask if you need help with this!

  • Submit the PDF to Gradescope and name it SelfAssessmentReflection.pdf.

While Coding Rooms has been a nice IDE, it has a few limitations. In particular, it lacks a "debugger" which allows you to pause execution of your program and inspect memory (similar to how Python Tutor supports visualization). For the remainder of the semester, we'll shift to using a more standard IDE and, for consistency, choose the freely available and widely-used IDE VSCode.

If you plan on developing your projects on your personal machines, in advance of your lab next week (Wednesday 3/30 or Thursday 3/31), please make sure to download and install VSCode to support Python programming. You can use these two videos that Charlie created to help you:

• on Windows

• on Mac

This homework will give you a chance to practice with 2D lists. In an earlier module led by your mentors in lab, you worked on the "Paranoid Prof" challenge. This problem is known as the n-Queens problem, based on how a Queen piece can attack on a chessboard (a Queen can attack another piece in the same row or in the same column or in the same diagonal). To refresh your memory, here is the setup you saw in the module:

You show up to a final for one of your classes. For some reason your professor is super paranoid about the possibility of cheating. You and your classmates decide to try to reassure your professor by sitting as far apart as possible. There are 8 students in your class (including you), and there are 8 rows and columns of desks. You and your classmates decide to make sure no two students occupy the same row, or the same column. But your professor is still paranoid! So you also decide to make sure no two students are sitting in the same diagonal. Task: Place all 8 students at a desk in a way that reduces the number of students in the same row, column or diagonal.

When you worked on this, you probably had two different processes that you were balancing:

1. Checking if a (partial) configuration of students was valid or invalid

2. Solving to find a valid configuration

In this homework, we'll focus on the first process of checking for valid/invalid configurations. We'll need to specify this a little more to be able to write a program. Often, we have a modeling phase, where we decide how to model the problem in code. Here is a how we can model the n-Queens problem:

• We can use a 2D grid of boolean values to model an nxn chess board

• Each cell of the 2D grid models a square of the chess board

• A True value in a cell models that a Queen is placed in that square

• A False value in a cell models that the square is empty

Based on this model, we can then specify the problem for this homework:

Given a 2D list of boolean values of True and False values, determine if any row, column or diagonal contains more than one True value. If so, return True; otherwise, return False.

• practice with 2D lists

• practice designing a solution to a problem and implement your solution

• continue practicing type-hinting and using mypy to make sure types are consistent

Be strategic!

• Start early!

• Ask questions!

• Leave time for questions by... starting early :)

• When you're stuck, pause and evaluate what could be going on. Remember the self-regulated learning cycle!

  • Do you have a plan?

  • Are you evaluating your plan? How will you test your code as you go?

  • How will you revise? What will you do when you're confused? Stuck?

Before you attempt to write any Python code, you should start with a plan and move towards pseudocode. Here are some prompts to help you think about your plan:

• How will you break the problem into smaller subproblems (perhaps you could check by row, then by column, then by diagonal)?

• For each subproblem, consider:

  • What function do you need to write?

  • What are the expected interactions with that function (remember, this helps you identify its parameters and return value)?

  • What is its expected behavior?

  • How will you implement the behavior? Write your approach in pseudocode; you have many examples from prior homeworks and projects. Strive to have pseudocode where you feel confident you can implement each line with a couple lines of Python code.

Requirements

• You must support checking whether two (or more) queens are in the same row or column.

• It is a bonus to check if two (or more) queens are in the same diagonal.

• When working with indices of a 2D grid, it's incredibly helpful to have pen/pencil and paper. Draw out a sample grid (e.g., a 4x4 board) and label the rows and columns (the way you did in Lab 8). Then write down the row and column indices for a particular example before looking for a pattern that you can generalize with variables.

Implement your design and pseudocode, remembering that it's best to have stubs and test as you go.

Requirements

To make sure that the autograder can run, you will need to have your highest-level function have this signature:

def validQueensConfiguration( grid:list ) -> bool:

""" Given a 2D grid of boolean values, determine if

any row, column or diagonal contains more than 1 True value.

If so, return False; otherwise (when it is a valid n-Queens

configuration), return True. """

Diagonal checking

It is a bonus (great experience, but not required!) to check if there are two or more queens in a diagonal. It is a little tricky to figure out the indices, so you can use the code below to solve this part of the problem.

To help you with testing, here is some starting code for your main function. You should add a few more test grids, though we will work more on how to test effectively during Lab 9.

• Some bugs are "easy" to detect in that Python will actually print out an error.

  • Use the error message to identify where the bug is.

    • The line number is a great starting point!

• Some bugs are "logical" bugs, which are a bit harder to identify and fix. For the buggy code given to you, identify them by looking at the

  • • Focus on examples where the expected output does not match the actual output to help isolate the bug(s)

    • Draw memory and trace the program to understand how Python is interpreting the code

    • Use print statements to gain insight into memory and narrow down the source(s) of the bug(s)

    • Use the comments to help you understand the high-level approach; there is a logical bug whenever the Python code does not implement the high-level approach