CECS 451
Assignment 3
Total: 60 Points
General Instruction
• Submit uncompressed file(s) in the Dropbox folder via BeachBoard (Not email).
• Use Python 3, any other programming language is not acceptable.
• You can import modules in the Python Standard Library (please check the full list
here). If you want to use any other library, please consult with the instructor or TA.
• Your submission may be evaluated automatically using a script file, so if you would
not follow the output format, you may receive zero point even though your program
outputs correct answers.
1. Implement 5-queens problem solvers using the hill-climbing algorithm and the genetic algorithm.
(a) (30 points) Implement a program that performs the hill-Climbing algorithm to
find a solution.
(b) (30 points) Implement a program that performs the genetic algorithm with 8
states including the three operations, i.e., selection, crossover, mutation to find
a solution.
Program specification.
i. You can use numpy library.
ii. Find the board.py, and please do not modify it.
iii. An initial state locates a queen per each row. Please use an appropriate and simple
local search strategy.
iv. The function get fitness in the board.py returns the number of attacking
pairs. It assumes a queen per each row, which means it checks only columns and
diagonals.
v. The hill-climbing algorithms can stuck in local minima. Please implement the
random restart procedure when they stuck.
vi. Please report running time and a solution.
Running time: 200ms
1 - - - -
- - - 1 -
- 1 - - -
- - - - 1
- - 1 - -
vii. Submit hill.py and genetic.py.
