N-Queens-Hill-Climbing-Variants

Contributors

• Varad Deshpande
• Akshay Bheda
• Devashri Gadgil

Problem statement

Problem Statement: The N-Queens Problem consists of placing N queens on an NxN chessboard so that no two queens can capture each other. That is, no two queens are allowed to be placed on the same row, the same column or the same diagonal. The problem of finding all solutions to the 8-queens problem can be quite computationally expensive. In this project, you will experiment with the n-queens problem by using hill-climbing search and its variants. Your program should treat the number of queens as a variable and should allow the user to input the value of queens. Using a programming language of your choice, implement the followings:

1. Hill climbing search
2. Hill-climbing search with sideways move
3. Random-restart hill-climbing with and without sideways move

Instructions for code execution :

Prerequisites :

• Make sure you have python installed.
• Make sure you have numpy installed.
• When you import the code in an IDE make sure there are no errors on the imports (numpy and copy).

Next Steps

• Clone the code repository from GitHub and go to the src folder. Note: There are 4 programs:

1. NQueen_Hill_Climb - Normal Hill Climbing program
2. NQueen_Hill_Climb_Restart - Hill Climbing with random restarts
3. NQueen_Hill_Climb_Sideway - Hill Climbing with Sideway moves without restarts
4. NQueen_Hill_Climb_Sideway_Restart - Hill Climbing with Sideway moves and random restarts

• Open the terminal in the src folder and execute command to run program of your choice : ‘py <program_name>’. Example py NQueen_Hill_Climb