P3: N-Queens A & B
Instructions
NQueensA: Write a brief Python program to randomly generate a solution to the N-Queens problem (described on pages 71-72). Your program should: Prompt the user for a value for N (for an NxN board) Generate a randomized candidate NQ solution Count the number of conflicting pairs of queens Repeat the previous two steps until you get a solution Print the solution and the number of iterations the solution took Submit your file as NQueensA_yourInitials.py (e.g. NQueensA_BRP.py), and note in the Submission Comments in D2L the largest n-queens solution it was able to generate in reasonable time (start at n=4 and work up) and how many iterations it took. Pseudocode: # NQueensA_yourInitials.py import random # ask the user for an N value # generate a candidate NQ solution [random.randint(0,n-1) for x in range(n)] # define a function to count number of conflicts() # while number of conflicts in NQ > 0 # randomize (or improve) NQ # print NQ # print number of iterations NQueensB: Write a brief Python program to generate a more-informed random solution to the N-Queens problem (described on pages 71-72). Your program should: Prompt the user for a value for N (for an NxN board) Generate a smarter randomized candidate NQ solution (unique rows & columns) Count the number of conflicting pairs of queens Repeat the previous two steps until you get a solution Print the solution and the number of iterations the solution took Submit your file as NQueensB_yourInitials.py (e.g. NQueensB_BRP.py), and note in the Submission Comments in D2L one 8-queens solution it was able to generate and how many iterations it took. Finally, run both programs A and B and note the largest N each program can solve in reasonable time, along with the number of iterations taken. BONUS (10pts) - make your NQ app "pretty print" the nxn board of queens as follows (and include in your D2L submission): n=4, NQ = [1,3,0,2]: -Q-- ---Q Q--- --Q- Pseudocode: # NQueensB_yourInitials.py import random # ask the user for an N value # generate a candidate NQ solution list(range(n)) # define a function to count number of conflicts() # while number of conflicts in NQ > 0 # randomize (or improve) NQ shuffle! # print NQ # print number of iterations ======================================================================================================= pg71-72 The goal of the 8-queens problem is to place eight queens on a chessboard such that no queen attacks any other. (A queen attacks any piece in the same row, column or diagonal.) Figure 3.5 shows an attempted solution that fails: the queen in the rightmost column is attacked by the queen at the top left. 72 Chapter 3. Solving Problems by Searching Figure 3.5 Almost a solution to the 8-queens problem. (Solution is left as an exercise.) Although efficient special-purpose algorithms exist for this problem and for the whole n-queens family, it remains a useful test problem for search algorithms. There are two main kinds of formulation. An incremental INCREMENTAL formulation involves operators that augment the state FORMULATION description, starting with an empty state; for the 8-queens problem, this means that each COMPLETE-STATE action adds a queen to the state. A complete-state formulation starts with all 8 queens on FORMULATION the board and moves them around. In either case, the path cost is of no interest because only the final state counts. The first incremental formulation one might try is the following: States: Any arrangement of 0 to 8 queens on the board is a state. Initial state: No queens on the board. Actions: Add a queen to any empty square. Transition model: Returns the board with a queen added to the specified square. Goal test: 8 queens are on the board, none attacked. In this formulation, we have 64 63 57 1.81014 possible sequences to investigate. A better formulation would prohibit placing a queen in any square that is already attacked: States: All possible arrangements of n queens (0 n 8), one per column in the leftmost n columns, with no queen attacking another. Actions: Add a queen to any square in the leftmost empty column such that it is not attacked by any other queen. This formulation reduces the 8-queens state space from 1.81014 to just 2,057, and solutions are easy to find. On the other hand, for 100 queens the reduction is from roughly 10400 states to about 1052 states (Exercise 3.5)a big improvement, but not enough to make the problem tractable. Section 4.1 describes the complete-state formulation, and Chapter 6 gives a simple algorithm that solves even the million-queens problem with ease.