Hill Climbing Algorithm - 8 Queens Problem

This project demonstrates the implementation of the Hill Climbing algorithm with random restarts to solve the classic 8 Queens problem, developed as part of my ITCS 3153 (Introduction to Artificial Intelligence) coursework at UNC Charlotte. The assignment successfully places 8 queens on an 8x8 chessboard such that no queen can attack another in a single move. I initially implemented this solution in Python before the assignment requirements specified Java or C#. Both versions use the same Hill Climbing logic and can be found in the repository as Assignment1.java and Assignment1.py.

View Source Code on GitHub

Project Overview

The 8 Queens puzzle is a classic constraint satisfaction challenge where the goal is to place eight chess queens on an 8×8 chessboard so that no two queens threaten each other. This means no two queens can share the same row, column, or diagonal.

This implementation uses the Hill Climbing algorithm, a local search optimization technique that iteratively moves toward better solutions by evaluating neighboring states. To handle local minima, the solution incorporates random restarts - automatically resetting the board configuration when no better moves are available.

The program tracks and displays:

• State Changes: The number of times a queen was moved to a better position
• Restarts: The number of times the algorithm had to restart from a random configuration

Technologies Used: Java, Local Search Algorithms, Heuristic Optimization

How to Run the Project

Prerequisites

To run this project, ensure you have the following installed on your machine:

• python 3.6 or higher if running the python version. You can download it from here.
• Java Development Kit (JDK) 8 or higher if running the java version. You can download it from here.
• Git, you can download it from here.

Installation/Execution Steps

1. Clone the repository:

   bash
   git clone https://github.com/jcmecham/Intro_To_AI_ITCS_3153.git
   

2. Navigate to the project directory:

   cd Intro_To_AI_ITCS_3153
   

3. For Java Version:

   • Compile the Java program:

   javac Assignment1.java
   

   • Execute the compiled Java program:

   java Assignment1
   

4. For Python Version:

   • Run the Python script:

   python Assignment1.py
   

How Hill Climbing Works

Hill Climbing is a local search algorithm that continuously moves in the direction of increasing value (or decreasing cost) to find the peak of a mountain (or the optimal solution). In the context of the 8 Queens problem, the algorithm works as follows:

1. Initial State: Randomly place one queen in each column of the board
2. Evaluation: Calculate a heuristic value representing the number of queen conflicts (pairs of queens attacking each other)
3. Generate Neighbors: For each column, consider all possible positions where the queen could be moved
4. Selection: Move to the neighboring state with the lowest heuristic (fewest conflicts)
5. Repeat: Continue until no neighboring states improve the current state

The Heuristic Function

The heuristic function counts the total number of attacking pairs of queens. For each queen, the algorithm checks if any other queens share the same row or diagonal (both \ and / diagonals). The goal is to minimize this heuristic to zero.