Homework Assignment #23

Show all work neatly.

How many solutions are there to the eight queens problem?

Just submitting the number will not suffice, since those are easy to find online. The insight you gain from implementing the state-space search is the most important part of the exercise. Write a short program to do the job. (Note that for this little exercise any programming language (e.g., Python) might do.) Write the explore() routine we examined in the lecture. Use the 8-tuple (and its permutations) as the representation of a state as we discussed in class. Design and implement the following sub-routines:

• criterion()
• partial_criterion()
• successors()
• init_state()

Submit your code as your work for this problem.

Extra credit: How many distinct solutions are there if we do not distinguish solutions that can be transformed into one another by rotations and reflections?

DP practice: Exercise 6.21 in the textbook.