[SOLVED] Cs540 p3: n-queens… with a boulder

Program Goals

• Deepen understanding of state space generation
• Practice implementation of search algorithms

Summary

We’ve introduced the 8-queens problem in class: place 8 queens on a chess board such that no queen is attacking any other queen.

A solution for an 8×8 board with state [2, 7, 3, 6, 0, 5, 1, 4]

Recall that in the game of chess, queens attack any piece they can “see” (i.e., there is nothing between the queen and the attacked piece) in the same row, column, or diagonal.

In this assignment, you will generalize this problem to a board of arbitrary (square) size and equivalent number of queens, and add a “boulder” to the board. This boulder has the following properties:

• It blocks the space — no queen may occupy the same space as the boulder
• It blocks queen attacks — two queens on opposite sides of the boulder are not considered to be attacking each other

Given the size of the board (N > 0) and location of the boulder (0 <= boulderX < N and 0 <= boulderY < N), you will implement a hill-climbing algorithm to attempt to solve the problem.

Program Specification

The code for this program must be written in Python, in a file called nqueens.py.

Your state representation must be a list of N integers, 0-indexed, representing the row the queen is occupying in each column. For simplicity of representation, we will retain our assumption of a single queen per column.

A Note About State Representation

A few students have pointed out that the state representation as a list of integers, one queen per column, only represents a subset of the possible valid states and solutions, since a boulder could block two queens in the same column from attacking each other and we could therefore have an empty column in a valid solution state. This is true!

The list-of-integers representation, however, simplifies the task of tie breaking unambiguously as it induces a natural ordering to the states that a list of (x,y) coordinates does not share. As the ordering and tie-breaking component are necessary only for efficiency of grading and are not the point of this assignment, we are choosing to simplify the space and have you explore only a subset of the possible states.

Should you want to additionally attempt a complete implementation with a list of n (x,y) coordinates that allows for multiple queens in the same column, Jerry and Hobbes would love to hear from you, but that is beyond the scope of the present assignment.

Goal State

There are multiple possible configurations for a goal state, defined only as a state in which no queen is attacking any other queen per the rules above. One of your tasks will be to define an evaluation function for the states such that the goal state has the highest value when the function is applied to it.

Functions

For this program you should write N (n) Python functions:

1. succ(state, boulderX, boulderY) — given a state of the board, return a list of all valid successor states
2. f(state, boulderX, boulderY) — given a state of the board, return an integer score such that the goal state scores 0
3. choose_next(curr, boulderX, boulderY) — given the current state, use succ() to generate the successors and return the selected next state
4. nqueens(initial_state, boulderX, boulderY) — run the hill-climbing algorithm from a given initial state, return the convergence state
5. nqueens_restart(n, k, boulderX, boulderY) — run the hill-climbing algorithm on an n*n board with random restarts

You may add other functions as you see fit, but these functions must be present and work as described.

Generate Successors

This function should return a list of lists, containing all valid successor states of the given initial state. For the purposes of this program, a successor of a current state is any valid state that differs from the initial state by ONE queen’s location.

• We WILL allow multiple queens to occupy the same row. They may be blocked from attacking each other by the boulder and you don’t need to figure that out here.
• We will NOT allow a queen to occupy the same space as the boulder.

For example, if the boulder is at (0,0) and n = 3, the valid successors of the state [1, 1, 2] are (formatted for readability here):

>>> succ([1,1,2],0,0)
=> [[2, 1, 2],
    [1, 0, 2],
    [1, 2, 2],
    [1, 1, 0],
    [1, 1, 1]]

Evaluate a State

As in class, we’ll define our f() to be the number of queens which are being attacked. Remember to account for the boulder in this calculation! Queens cannot attack through the boulder.

Given n=3 and a boulder at (1,1), here are some example f() values:

[1, 2, 2] - f=3
[2, 2, 2] - f=3
[0, 0, 2] - f=2  <-- (0,0) to (2,2) is blocked by the boulder
[0, 2, 0] - f=2
[0, 2, 1] - f=2

Select Next State

Given a current state and the location of the boulder, use the previous two functions to select the next state to evaluate per the following rules:

• If one of the possible states (including the current state) has a uniquely low score, select that state
• Otherwise, sort the states as in P2 (as though they were integers) and select the “lowest” state

If the state selected is the same as the current state, return None.

>>> choose_next([1,1,2],0,0)
=> [1, 0, 2]
>>> choose_next([0,0,2],1,1)
=> None

N-Queens

Run the hill climbing algorithm as specified in class on a given initial state until convergence: that is, until your algorithm finds a local minimum and gets stuck (or solves the problem).

Your printed output for this function should look like the black text below, followed by the returned minimum state in green:

>>> nqueens([0,1,2,3,5,5,6,7], 4, 4)
[0, 1, 2, 3, 5, 5, 6, 7] - f=8
[0, 1, 2, 3, 5, 0, 6, 7] - f=7
[0, 1, 2, 3, 5, 0, 4, 7] - f=5
[0, 1, 6, 3, 5, 0, 4, 7] - f=4
[0, 1, 6, 3, 5, 2, 4, 7] - f=3
[0, 4, 6, 3, 5, 2, 4, 7] - f=2
[0, 4, 1, 3, 5, 2, 4, 7] - f=2
=> [0, 4, 1, 3, 5, 2, 4, 7]

>>> nqueens([0,2,2,3,4,5,6,7], 1, 1)
[0, 2, 2, 3, 4, 5, 6, 7] - f=7
[0, 2, 2, 3, 1, 5, 6, 7] - f=6
[0, 2, 2, 3, 1, 4, 6, 7] - f=5
[0, 2, 5, 3, 1, 4, 6, 7] - f=3
[0, 2, 5, 3, 1, 4, 6, 3] - f=3
[0, 2, 5, 1, 1, 4, 6, 3] - f=2
=> [0, 2, 5, 1, 1, 4, 6, 3]

Each step of the hill-climbing function should print its current state along with that state’s f() value, and ultimately return the best state you find.

N-Queens with Random Restarts

Generate a random (valid!) initial state for your n*n board, and use your nqueens() function on that state. If the convergent state does not solve the problem, generate a new random (valid!) initial state and try again. Try again up to k times.

If you find a solution before you reach k, print the solution and terminate.

If you reach k before finding a solution, print the best solution(s) in sorted order.

Python’s random module will be helpful in generating random initial states. Each column’s coordinate should be uniformly distributed over the possible coordinates. To generate a single uniform integer between 0 (inclusive) and n (inclusive), the Python code is:

import random
n = random.randint(0,8)

Be sure to account for the location of the boulder! If you happen to randomly generate a state where a queen is occupying the same space as the boulder, abandon that state and generate a new one.