CPSC 415 - Artificial Intelligence - Fall 2023
Possible experience: +50XP
Due: Saturday, Sep. 30th Tuesday, Oct. 3rd, 6:30pm
I've entitled this assignment "Program #2⅓" because it is being offered to you in addition to the already-planned six up-to-50XP programs mentioned on the syllabus. Feel free to do this assignment instead of one of the other six, in addition to the other six, or not at all! The choice is yours.
Write a program that uses a local search algorithm to solve the n-queens problem for any given value of n. You can use plain-ol' hill climbing, the random restart version, the first-choice version, the stochastic version, simulated annealing, one of those weird hybrids concocted in class, or something else! The choice is yours.
Your program should be called yourumwid_nqueens.py, where yourumwid is your actual (lowercase) UMW Net ID. (Please do not name your file anything else. Please do not omit the suffix, or change the capitalization, or add/remove underscores, or do any other clever or creative things. Please call it exactly yourumwid_nqueens.py, with your actual (lowercase) UMW Net ID substituted for "yourumwid". Thanks.)
Your program should take one command-line argument, an integer n. (I will only call your program with n ≥ 4.) It should output one line of text for each board it considers as it searches. That line of text should be a space-separated list of integers in the range 0 through n-1 that indicates, for each column, which row number has the queen in that column. For consistency in grading, the lines should begin with a [ character and end with a ] character.
The last line of text, of course, should be the solution: a list of integers which represent the respective row numbers of n queens, none of which are attacking each other vertically, horizontally, or diagonally.
Optionally, you may dunk at the end of the program by printing out your solution in a more graphical fashion. This is not required for the assignment, but I'll chip in a bonus XP if you do it.
Here are some sample outputs from my program:
$ python3 stephen_nqueens.py 4 [ 3 0 0 0 ] [ 3 0 2 0 ] [ 3 0 2 1 ] [ 3 0 3 1 ] [ 2 0 3 1 ] Solution: +-------+ |. Q . .| |. . . Q| |Q . . .| |. . Q .| +-------+ [ 2 0 3 1 ]
$ python3 stephen_nqueens.py 10 [ 7 1 0 1 9 0 1 1 5 3 ] [ 7 1 0 1 9 0 8 1 5 3 ] [ 7 2 0 1 9 0 8 1 5 3 ] [ 7 2 0 6 9 0 8 1 5 3 ] [ 4 2 0 6 9 0 8 1 5 3 ] [ 4 2 0 6 9 0 8 1 7 3 ] [ 4 2 0 6 9 5 8 1 7 3 ] [ 4 2 0 6 9 5 8 0 7 3 ] [ 4 2 9 6 9 5 8 0 7 3 ] [ 4 2 9 6 1 5 8 0 7 3 ] Solution: +-------------------+ |. . . . . . . Q . .| |. . . . Q . . . . .| |. Q . . . . . . . .| |. . . . . . . . . Q| |Q . . . . . . . . .| |. . . . . Q . . . .| |. . . Q . . . . . .| |. . . . . . . . Q .| |. . . . . . Q . . .| |. . Q . . . . . . .| +-------------------+ [ 4 2 9 6 1 5 8 0 7 3 ]
$ python3 stephen_nqueens.py 25
[ 24 14 3 0 2 18 1 21 22 2 3 24 11 7 0 0 0 11 20 19 15 19 14 4 2 ]
[ 24 14 3 0 2 18 1 21 22 2 3 24 8 7 0 0 0 11 20 19 15 19 14 4 2 ]
...lots more lines here...
[ 4 9 18 2 11 6 20 5 17 24 21 16 1 19 7 3 0 12 10 22 14 3 8 13 15 ]
[ 4 9 18 2 11 6 20 5 17 24 21 16 1 19 7 3 0 12 10 22 14 23 8 13 15 ]
Solution:
+-------------------------------------------------+
|. . . . . . . . . . . . . . . . Q . . . . . . . .|
|. . . . . . . . . . . . Q . . . . . . . . . . . .|
|. . . Q . . . . . . . . . . . . . . . . . . . . .|
|. . . . . . . . . . . . . . . Q . . . . . . . . .|
|Q . . . . . . . . . . . . . . . . . . . . . . . .|
|. . . . . . . Q . . . . . . . . . . . . . . . . .|
|. . . . . Q . . . . . . . . . . . . . . . . . . .|
|. . . . . . . . . . . . . . Q . . . . . . . . . .|
|. . . . . . . . . . . . . . . . . . . . . . Q . .|
|. Q . . . . . . . . . . . . . . . . . . . . . . .|
|. . . . . . . . . . . . . . . . . . Q . . . . . .|
|. . . . Q . . . . . . . . . . . . . . . . . . . .|
|. . . . . . . . . . . . . . . . . Q . . . . . . .|
|. . . . . . . . . . . . . . . . . . . . . . . Q .|
|. . . . . . . . . . . . . . . . . . . . Q . . . .|
|. . . . . . . . . . . . . . . . . . . . . . . . Q|
|. . . . . . . . . . . Q . . . . . . . . . . . . .|
|. . . . . . . . Q . . . . . . . . . . . . . . . .|
|. . Q . . . . . . . . . . . . . . . . . . . . . .|
|. . . . . . . . . . . . . Q . . . . . . . . . . .|
|. . . . . . Q . . . . . . . . . . . . . . . . . .|
|. . . . . . . . . . Q . . . . . . . . . . . . . .|
|. . . . . . . . . . . . . . . . . . . Q . . . . .|
|. . . . . . . . . . . . . . . . . . . . . Q . . .|
|. . . . . . . . . Q . . . . . . . . . . . . . . .|
+-------------------------------------------------+
[ 4 9 18 2 11 6 20 5 17 24 21 16 1 19 7 3 0 12 10 22 14 23 8 13 15 ]
I will award you +nXP for this assignment, where n is the largest board dimension that your program can solve in two minutes or less on my laptop. I will try all values of n from 4 on up until your program takes more than 2 minutes to complete its search.
You will turn this assignment in by attaching your properly-named Python file to an email with subject line "CPSC 415 Program #2⅓ turnin". In the body of the email, tell me the highest value of n that your program successfully solved during your own testing. (This is just to give me an idea of what to expect. Your program will get more points than this if it solves a larger board in ≤ 2 minutes on my laptop...and fewer points than this if it can't solve that large a board in time for me.)
Come to office hours, or send me email with subject line "CPSC 415 Program #2⅓ help!!"