INTRODUCTION TO AI: Assignment One - support files

modified_nqeens.py

from collections import deque
import heapq
import math

class NQueens:
    def __init__(self, N):
        self.N = N
        self.initial_state = tuple((0, col) for col in range(N))
        
    def actions(self, state):
        """Generate valid moves for each queen."""
        moves = []
        for i, (row, col) in enumerate(state):
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                new_row, new_col = row + dr, col + dc
                if 0 <= new_row < self.N and 0 <= new_col < self.N:
                    if not any((new_row, new_col) == (r, c) for r, c in state):
                        moves.append((i, (new_row, new_col)))
        return moves

    def result(self, state, action):
        """Execute a move and return the new state."""
        i, (new_row, new_col) = action
        new_state = list(state)
        new_state[i] = (new_row, new_col)
        return tuple(new_state)

    def is_goal(self, state):
        """Check if the state is a goal state."""
        rows = [row for row, col in state]
        cols = [col for row, col in state]
        """Check for conflicts in rows, columns, and diagonals"""
        if len(set(rows)) != self.N or len(set(cols)) != self.N:
            return False
        for i in range(self.N):
            for j in range(i + 1, self.N):
                if abs(rows[i] - rows[j]) == abs(cols[i] - cols[j]):
                    return False
        return True

    def heuristic(self, state):
        """Heuristic function: Count the total number of conflicts."""
        conflicts = 0
        for i in range(self.N):
            for j in range(i + 1, self.N):
                if state[i][0] == state[j][0] or state[i][1] == state[j][1] or abs(state[i][0] - state[j][0]) == abs(state[i][1] - state[j][1]):
                    conflicts += 1
        return conflicts

def bfs(problem):
    """Breadth-First Search."""
    frontier = deque([(problem.initial_state, [])])
    explored = set()
    nodes_expanded = 0

    while frontier:
        state, path = frontier.popleft()
        if problem.is_goal(state):
            return path, nodes_expanded, len(frontier)
        if state not in explored:
            explored.add(state)
            nodes_expanded += 1
            for action in problem.actions(state):
                new_state = problem.result(state, action)
                frontier.append((new_state, path + [action]))
    return None, nodes_expanded, len(frontier)

def ucs(problem):
    """Uniform Cost Search."""
    frontier = [(0, problem.initial_state, [])]
    explored = set()
    nodes_expanded = 0

    while frontier:
        cost, state, path = heapq.heappop(frontier)
        if problem.is_goal(state):
            return path, nodes_expanded, len(frontier)
        if state not in explored:
            explored.add(state)
            nodes_expanded += 1
            for action in problem.actions(state):
                new_state = problem.result(state, action)
                heapq.heappush(frontier, (cost + 1, new_state, path + [action]))
    return None, nodes_expanded, len(frontier)

def astar(problem):
    """A* Search."""
    frontier = [(problem.heuristic(problem.initial_state), 0, problem.initial_state, [])]
    explored = set()
    nodes_expanded = 0

    while frontier:
        est_cost, cost, state, path = heapq.heappop(frontier)
        if problem.is_goal(state):
            return path, nodes_expanded, len(frontier)
        if state not in explored:
            explored.add(state)
            nodes_expanded += 1
            for action in problem.actions(state):
                new_state = problem.result(state, action)
                new_cost = cost + 1
                heapq.heappush(frontier, (new_cost + problem.heuristic(new_state), new_cost, new_state, path + [action]))
    return None, nodes_expanded, len(frontier)

def solve_n_queens(N):
    """Solve the Modified N-Queens Problem using BFS, UCS, and A*."""
    problem = NQueens(N)
    print(f"Solving for N = {N}")

    print("\nRunning BFS...")
    bfs_solution, bfs_nodes, bfs_frontier = bfs(problem)
    print(f"BFS Solution: {bfs_solution}")
    print(f"Nodes Expanded: {bfs_nodes}, Frontier Size: {bfs_frontier}")

    print("\nRunning UCS...")
    ucs_solution, ucs_nodes, ucs_frontier = ucs(problem)
    print(f"UCS Solution: {ucs_solution}")
    print(f"Nodes Expanded: {ucs_nodes}, Frontier Size: {ucs_frontier}")

    print("\nRunning A*...")
    astar_solution, astar_nodes, astar_frontier = astar(problem)
    print(f"A* Solution: {astar_solution}")
    print(f"Nodes Expanded: {astar_nodes}, Frontier Size: {astar_frontier}")

if __name__ == "__main__":
    for N in [4, 5, 6, 7, 8]:
        solve_n_queens(N)

results.txt

Solving for N = 4

Running BFS...
BFS Solution: [(0, (1, 0)), (0, (2, 0)), (2, (1, 2)), (2, (2, 2)), (2, (3, 2)), (3, (1, 3))]
Nodes Expanded: 1024, Frontier Size: 6055

Running UCS...
UCS Solution: [(0, (1, 0)), (1, (1, 1)), (1, (2, 1)), (1, (3, 1)), (3, (1, 3)), (3, (2, 3))]
Nodes Expanded: 1436, Frontier Size: 7447

Running A*...
A* Solution: [(1, (1, 1)), (1, (2, 1)), (3, (1, 3)), (3, (2, 3)), (1, (3, 1)), (0, (1, 0))]
Nodes Expanded: 49, Frontier Size: 393
Solving for N = 5

Running BFS...
BFS Solution: [(0, (1, 0)), (0, (2, 0)), (0, (3, 0)), (0, (4, 0)), (1, (1, 1)), (1, (2, 1)), (3, (1, 3)), (3, (2, 3)), (3, (3, 3)), (4, (1, 4))]
Nodes Expanded: 67118, Frontier Size: 454803

Running UCS...
UCS Solution: [(1, (1, 1)), (1, (2, 1)), (2, (1, 2)), (2, (2, 2)), (2, (3, 2)), (2, (4, 2)), (3, (1, 3)), (4, (1, 4)), (4, (2, 4)), (4, (3, 4))]
Nodes Expanded: 74584, Frontier Size: 479484

Running A*...
A* Solution: [(1, (1, 1)), (1, (2, 1)), (3, (1, 3)), (2, (1, 2)), (3, (2, 3)), (3, (3, 3)), (3, (4, 3)), (1, (3, 1)), (4, (1, 4)), (4, (2, 4))]
Nodes Expanded: 1345, Frontier Size: 13867
Solving for N = 6

.
.
.