HW 6:
n-Queens solver
Submission Details
Due: 4/12 - Submit via Gradescope:
4 files in total
buggy_recursion.py
n_queens_checker.py
n_queens_solver.py
A PDF that contains your self-assessment & reflection
Instructions
Part 1: debug the buggy_recursion.py program below
Part 2. create an n_queens_solver.py program to solve the n Queens problem
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.
Homeworks are an opportunity to engage with the material and practice your programming skills. To support you, solutions will be available on moodle. It is your responsibility to engage with them in a way that strategically moves your learning forward. You should:
Attempt the homework without looking at the solutions.
Review the solutions; if you were stuck, you may revise your homework. You may find yourself iteratively reviewing and revising to best support your learning.
When you submit your homework, you will be required to complete a self-assessment and reflection:
Give yourself an assessment mark on the initial attempt:
✘ if you did not complete it
✓- if you completed it, but were very far from the solution
✓ if you completed it and essentially had the solution
✓+ if you completed it correctly, including precise communication
? if you are unsure as to whether or not you completed it
Provide a short reflection as to why you earned that mark, such as:
I did not understand how to get started, and it was too close to the deadline to visit support hours.
I got stumped by a bug where my program entered an infinite loop.
If you used the solutions to revise your work, describe what you needed to change, as in:
I modified the style of my conditional when I saw a simpler approach in the solutions.
I was so stuck that the majority of my submission is based on the solutions.
Ask specific questions on portions that are still confusing, such as:
Why does it cause an error when I returned "1" instead of 1?
[Optional] Provide one hint for the homework (to your past self or future student).
Learning goals
practice with recursion
practice debugging skills
implement a recursive approach from pseudocode
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?
Part 1: buggy recursion
The program below has some bugs in it!
Copy it into a file named buggy_recursion.py
Work to debug the program, using the comments and test code to guide you.
buggy_recursion.py
def reverseString( word:str ) -> str:
""" Given a word, reverse it. For example,
"cat" -> "tac" and "bulb" -> "blub". """
# base case
if len(word) == 0:
return word
# recursive case
else:
# peel off the first letter and recurse
firstLetter:str = word[0]
restOfWord:str = word[1:]
return firstLetter + reverseString(restOfWord)
def isPalindrome( word:str ) -> bool:
""" A palindrome is a word that is the same as its own reversal.
For example, "wow" is a palindrome since it is the same forwards as backwards,
but "bulb" is not. This function should return True if the given word
is a palindrome. """
# base case
if len(word) == 1:
return True
# recursive case
else:
# peel off outer two
firstLetter:str = word[0]
lastLetter:str = word[len(word)-1]
interior:str = word[1:len(word)-1]
# check if the first and last match
if firstLetter == lastLetter:
# then recurse
return isPalindrome(interior)
# otherwise, we know it's not a palindrome
return False
def countDown( startValue:int ) -> str:
""" Given a number greater than or equal to 0
to start at, counts down until the value 1, then ends with "Go!".
Invalid inputs (with a negative number) should return the empty string "".
For example,
5 -> "5,4,3,2,1,Go!"
3 -> "3,2,1,Go!"
-4 -> ""
"""
# base case
if startValue == 0:
return "Go!"
# recursive case
else:
return countDown( startValue - 1 ) + str(startValue) + ","
def testReverseString() -> None:
testCases:list = ["bulb","cat",""]
expectedOutput:list = ["blub","tac",""]
for i in range(len(testCases)):
testOutput:str = f"Testing reverseString({testCases[i]})..."
testResult:str = reverseString( testCases[i] )
if testResult == expectedOutput[i]:
testOutput += "PASSED"
else:
testOutput += "FAILED"
print( f"{testOutput}\nExpected: {expectedOutput[i]}, Actual: {testResult}")
def testCountDown() -> None:
testCases:list = [5,3,0,-2]
expectedOutput:list = ["5,4,3,2,1,Go!","3,2,1,Go!","Go!",""]
for i in range(len(testCases)):
testOutput:str = f"Testing countDown({testCases[i]})..."
testResult:str = countDown( testCases[i] )
if testResult == expectedOutput[i]:
testOutput += "PASSED"
else:
testOutput += "FAILED"
print( f"{testOutput}\nExpected: {expectedOutput[i]}, Actual: {testResult}")
def testPalindrome() -> None:
testCases:list = ["bulb","wow","","cat"]
expectedOutput:list = [False,True,True,False]
for i in range(len(testCases)):
testOutput:str = f"Testing isPalindrome({testCases[i]})..."
testResult:str = isPalindrome( testCases[i] )
if testResult == expectedOutput[i]:
testOutput += "PASSED"
else:
testOutput += "FAILED"
print( f"{testOutput}\nExpected: {expectedOutput[i]}, Actual: {testResult}")
if __name__ == "__main__":
testReverseString()
testPalindrome()
testCountDown()
Part 2: n-Queens checker
This homework will continue the work on the n-Queens problem. Remember from HW 5: n-Queens Checker that the name is 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). This was 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:
Checking if a (partial) configuration of students was valid or invalid
Solving to find a valid configuration
In this homework, we'll focus on the first process of solving to find valid configurations. Remember that we decided to model this way:
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 value n, find every 2D list of boolean values (True/False) that represents a valid placement of n queens on an nxn board. To be valid, there must be no pair of queens that could attack each other; no pair can be in the same row, column or diagonal.
As we think about the solver, it is natural to question whether any solution exists for a given value of n; if so, is it unique? Are there many solutions?
We'll be able to investigate this through the code we write, but it may help to check out this interesting page.
Learning goals
practice with 2D lists
practice implementing a recursive approach for a problem
practice adapting sample code for file output
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?
Importing your checker from HW 5
You'll need to import your checker from HW 5 to be able to invoke the functions within.
Copy your working (or use solutions) n_queens_checker.py into the directory that you'll be using for HW 6
In the n_queens_solver.py file that you must create for this homework's solver program, add the following line of code which will allow you to use your n_queens_checker.py code as a "module" (much like the random module).
import n_queens_checkerThen, when you want to invoke the validQueensConfiguration function, you can do so with the dot notation (again, much like random.randint), as in:
n_queens_checker.validQueensConfiguration( board )
File Output (with sample code)
We'll want to save the solutions to a file so that they can be easily reviewed; printing to the console will be very cumbersome.
To write to a file, here is some sample code. Note that
The first part uses the "w" argument to specify "writing" to a file. This will overwrite the file if it already exists (erasing all contents) or create a new file if it does not exist.
The second part uses the "a" argument to specify "appending" to a file. This will add to the end of the file if it already exists (keeping the current contents and simply appending to the end) or create a new file if it does not exist.
You should test this code out and try modifying it to make sure you have a sense of how to adapt it.
# a list of fruits
fruits:list = ["apple", "banana", "orange"]
# open an output file for writing
with open( "fruits.txt", 'w') as writer:
# for each fruit in the list
for fruit in fruits:
# output it to the file
writer.write( fruit )
moreFruits:list = ["kiwi", "lemon"]
# open an output file for appending
with open( "fruits.txt", 'a') as writer:
# for each fruit in the list
for fruit in moreFruits:
# output it to the file with new lines following
writer.write( f"{fruit}\n" )
File format
To align with the autograder's testing code on Gradescope, your files must have the same format. Solutions for each value of n should be in a separate file named queens<n>.txt, as in queens1.txt for a 1x1, queens2.txt for a 2x2, ... It will be important to match this exactly (respecting the line breaks, the lack of spaces, and the number of # symbols.
The general template is:
line 1 is a header, with the appropriate substitution for <n>, as in 1, 2, 3...
<n> Queens Solutionseach solution should be preceded by n*2 # symbols
the solution itself should have a - for an empty square (False value) and a * for a queen (True value), separated by commas; it's easier to end the line with a comma as well
To make this concrete, this is what queens4.txt should hold:
4 Queens Solutions
########
-,*,-,-,
-,-,-,*,
*,-,-,-,
-,-,*,-,
########
-,-,*,-,
*,-,-,-,
-,-,-,*,
-,*,-,-,
Recursive pseudocode
We'll spend some time during Tuesday 4/5's class considering how to solve this problem. Ultimately, you'll use the recursive pseudocode outlined below.
You should write a high level solver function named nQueensSolver that:
Requires a single parameter n of type int
Has a return type of None
expected behavior: Finds all solutions to the n-Queens problem and saves them to a file named queens<n>.txt. For example, if n is 4, this should find the 2 solutions to placing 4 non-attacking queens on a 4x4 board and save them to the file queens4.txt.
How?
Write a single line to the file
Open the file for writing; you should pass "w" as the second argument to the open function to indicate you'd like to (over)write the contents of the file. The file name should have the pattern queens<n>.txt, where the <n> is a placeholder that should be substituted with the value of n, as in queens4.txt.
Write a single line, which should be "<n> Queens Solutions"; again, where <n> is a placeholder that should be substituted with the value of n, as in
4 Queens Solutions
You'll need to use the newline character \n to "end" the line.
Initialize an empty n x n board with all False values
Invoke the recursive function placeQueen to start the recursion at row 0
You should write the recursive function placeQueen that:
Requires two parameters
A value row of type int for the row to place a queen in
A value board of type list for the 2D list of True/False values with the current configuration
Has a return type of None
Expected behavior: Given a (square) board of True/False values, try to place a queen in the given row. If this is the last row, save any valid configurations to file.
How?
If row is an invalid input (< 0)
Print out a message to indicate that it's an invalid input
Base case: this is the final row
for each placement of the queen in this row
update the board to place the queen at that position
if the resulting board is a valid configuration
save it to the file
update the board to remove the queen (so that it's reset for the next iteration)
Recursive case: this is not the final row
for each placement of the queen in this row
update the board to place the queen at that position
if the resulting board is a valid configuration
recursively try to place the next queen (in the next row)
update the board to remove the queen (so that it's reset for the next iteration)
Helper functions
You'll need to design some helper functions to save valid configurations to a file.
Hints:
You'll want to pass the "a" argument to the open function to append each solution as you find it.
You may want to write a function that takes in a board and returns a string with the correct formatting; this will help for testing as you can print out boards along the way AND for saving to the file.
main function
Your main function should invoke the nQueensSolver function on the values 1,2,...,9. You'll find that, once n starts to get larger, the code can take a bit of time to run. Given this, you probably want to test on small values (1,2,3,4,5) of n before moving onto the larger ones.