## Description

Lab 2: Greedy Search

The task in this lab is to use greedy hill-climbing search to find minima and solutions to the 10-

queens problem. This problem tries to find a position for all 10 queens on the board where they

cannot attack each other. Reminder, an attack is whenever a queen shares a row, column, or

diagonal with another queen. Here we will provide an initial configuration of the board for the 10-

queens problem, and you are to modify that board with the local minima reached from that starting

board. Here, a single step in the hill-climb is the movement of any one of the queens.

To simplify the problem every initial configuration will have exactly one queen in each column.

We will also require that any intermediate configuration used also has exactly one queen in each

column. This means any step in your hill-climb is the motion of one queen vertically up or down

within her column.

Each board will have the following layout of the x and y coordinates:

The board will be given as a 2D array board[y][x], where x and y are the positions of the board.

Queens are marked with a 1, empty positions are marked with a 0. You are to complete the code

for the function gradient_search(board) in the file student_code.py. This function will modify

“board” to be the local minima reached. In addition you will return True if the local minima is also

a solution to the problem, and return False otherwise.

To make sure everybody arrives to the same results (very important for the automated grader)

you must use the following tie breaker:

If motion of two or more different queens give the same best reduction in total attacks, choose to

move the queen with the lowest x value. If two or more positions for the same queen give the

same best reduction in total attacks, choose the position with the lowest y value.

Do not move to a new board state unless the total number of attacking queens in reduced (i.e.

don’t move on ties)

Don’t use any additional python modules or packages, and use Python3.

Considerations:

● We provided several maps to let you test your solution, but the grading will use a different

set. Feel free to create your own test cases.

● The running time of your algorithm cannot be longer than 10 seconds per board, otherwise

it will fail the grading test.