#Assignment: Validate N-queens

The N-queens problem is a problem of placing N queens on an N*N chessboard such that no two queens can attack each other. A queen can move horizontally in a row, vertically in a column, or diagonally in either direction. It is out of the CS1 syllabus to solve the N-queens problem. But given a random placement of N queens on an N*N chessboard, you can check if the placement is a valid solution with the concepts that you have learned in CS1.

Representing the N*N chessboard and placement of N-queens

Representing a row:

A N*N chessboard is made up of N rows, and each row has N squares. The placement of queens in each row of N squares can be represented by a list of length N that contains boolean values True or False. To represent the row in a 6*6 chessboard shown in the picture below, we can use a list of length 6 that is equal to
[False, False, True, False, False, False]. The red dot indicates that a queen is placed in the third square from the left.

Representing the complete board:

To represent all rows of an N*N chessboard, we need N lists, where each list contains True or False and is of length N. These lists can be put together into a list of lists of length N, where each inner list represents a row in the chessboard. For example, the 5*5 chessboard given below can be represented by the list of lists

[[False, False, True, False, False], 
[True, False, False, False, False], 
[False, False, False, True, False], 
[False, True, False, False, False], 
[False, False, False, False, True]]

The order of inner lists corresponds to the order of rows from top to bottom on the chessboard.

Validating the placements of the queens

The placement of queens is a valid solution to a N-queen problem if no two queens can attack each other. If a queen is in row r1 and column c1, and another queen is in row r2 and column c2, then the two queens are in attacking position if any of the following conditions are true:

1. r1 == r2, this condition checks if the two queens are in the same row.
2. c1 == c2, this condition checks if the two queeens are in the same column.
3. r1 - c1 == r2 - c2, this condition checks if the two queens are in the same diagonal.
4. r1 + c1 == r2 + c2, this condition checks if the two queens are in the same diagonal.

What to do and how to do it

Your job is to define a function named check_board that takes a list of lists, board, as a parameter. The parameter represents an N*N chessboard, as described in the previous section. The list of lists is of length N, and each inner list is also of length N. The inner list contains boolean values True or False as elements. Your function should return True if the placements of queens is valid.

Here is a partially finished file (right click on the link and select “Save link as” or “Download link as” option to save the file) n_queens_sa.py. This code has some functions to help you. It has functions that allow you to use your mouse to click on a square to place a queen in that square. If you click on a square that has a queen it will remove the queen. Your check_board function is by the code at the framerate set in start_graphics. At any given point, if any two queens can attack each other, your check_board returns False, the program ends, and you will see ‘The End’ on the screen.

Special note:

Your code should work for any value of N >= 4.

You are only allowed to add code to body of check_board and define helper functions for check_board and change the value of N.

What to submit

Submit a zip file containing the following:

1. Your .py file.
2. Screenshot of the graphics window with a 4*4 chessboard with a valid placement for 4 queens.
3. Screenshot of the graphics window with a 4*4 chessboard with at least two queens placed in an attacking position and “The End” displayed on the screen.

Honor Code

The consequences of violating the Honor Code can be severe. Please always keep in mind the word and spirit of the Honor Code.