Sovereign 8s.is mirror of standardgalactic/foundation_artificial_intelligence
Find a file
Repository files (latest commit first)
Filename Latest commit message Latest commit date
Asfand Yar 1d15b4a928
Revise README for better clarity and organization
Updated README to enhance clarity and structure, including improved section headings and descriptions for implemented problems.
2026-03-19 22:47:14 +01:00
__pycache__ Initial commit - AI state space problems 2026-02-27 01:35:29 +01:00
4_queen_base.py Implemented to force first move A->B so it will automatically in 13 steps 2026-03-14 19:14:02 +01:00
cup3_base.py Implemented Hanoi actions and result functions 2026-03-05 23:55:33 +01:00
hanoi_base.py Implemented to force first move A->B so it will automatically in 13 steps 2026-03-06 00:34:37 +01:00
LICENSE Initial commit 2026-02-26 23:37:17 +01:00
README.md Revise README for better clarity and organization 2026-03-19 22:47:14 +01:00
search.py Initial commit - AI state space problems 2026-02-27 01:35:29 +01:00
utils.py Initial commit - AI state space problems 2026-02-27 01:35:29 +01:00

🤖 Foundation of Artificial Intelligence

Classical AI search algorithms and constraint satisfaction — implemented in Python

Python License Status Framework

Built as part of a university-level Foundations of AI course, using the Russell & Norvig AIMA framework.


📋 Table of Contents


🧠 Overview

This repository contains Python implementations of foundational AI problem-solving techniques, with a focus on state space search, uninformed and informed search strategies, and constraint satisfaction problems (CSPs).

Each problem is modelled as a subclass of the Problem base class from search.py, making all problems immediately compatible with every search algorithm in the framework.


📁 Repository Structure

foundation_artificial_intelligence/
│
├── search.py           # Core search algorithms (BFS, DFS, A*, UCS, Greedy)
├── utils.py            # Utility functions, queues, data structures
│
├── hanoi_base.py       # Tower of Hanoi — state space formulation
├── cup3_base.py        # Water Jug / Cup pouring problem
└── 4_queen_base.py     # 4-Queens constraint satisfaction problem

🧩 Problems Implemented

🗼 Tower of Hanoi

File: hanoi_base.py

Move all disks from peg A to peg B without placing a larger disk on a smaller one.

Initial state       Step 4              Goal state
    A  B  C             A  B  C             A  B  C
   [1]                     [1]                 [1]
   [2]              [3]    [2]                 [2]
   [3]                                         [3]
Property Detail
State Tuple of disk lists on pegs A, B, C
Actions Move top disk from any peg to any other
Goal All disks on peg B
Optimisation Forced first move A→B — solves in ~13 steps automatically

💧 Water Jug Problem

File: cup3_base.py

Reach a target volume using jugs of fixed capacities by filling, emptying, or pouring between them.

Jugs: A=3L  B=4L  C=2L      Target: 2L in any jug

State 0:  (3, 0, 0)   → start
State 1:  (1, 0, 2)   → pour A into C
State 2:  (1, 2, 0)   → pour C into B
State 3:  (0, 2, 1)   → pour A into B
State n:  ...         → BFS finds optimal path
Property Detail
State Tuple (vol_A, vol_B, vol_C)
Actions Fill, empty, or pour between any two jugs
Goal Target volume in at least one jug
Algorithm BFS over full reachable state graph

👑 4-Queens Problem

File: 4_queen_base.py

Place 4 queens on a 4×4 board so that no two queens attack each other.

Solution 1          Solution 2
. Q . .             . . Q .
. . . Q             Q . . .
Q . . .             . . . Q
. . Q .             . Q . .
Property Detail
State Partial column assignment of queens
Constraints No shared row, column, or diagonal
Solutions 2 valid solutions exist
Strategy Backtracking with forced first-move optimisation

⚙️ Search Algorithms

Implemented in search.py — all algorithms share the same Problem interface.

Algorithm Type Strategy Complete Optimal
BFS Uninformed Breadth-first (FIFO queue) ✅ ✅ (unit cost)
DFS Uninformed Depth-first (LIFO stack) ❌ ❌
UCS Uninformed Uniform cost (priority queue) ✅ ✅
A* Informed Heuristic + path cost f = g + h ✅ ✅ (admissible h)
Greedy Informed Heuristic only f = h ❌ ❌

The Problem Interface

Every problem implements these four methods:

class Problem:
    def actions(self, state):
        """Return list of valid actions from this state."""
        raise NotImplementedError

    def result(self, state, action):
        """Return the state that results from applying action."""
        raise NotImplementedError

    def goal_test(self, state):
        """Return True if this state is a goal state."""
        return state == self.goal

    def path_cost(self, c, state1, action, state2):
        """Return cost of path — used by UCS and A*."""
        return c + 1

🚀 Getting Started

Prerequisites

  • Python 3.8 or higher
  • No external dependencies — standard library only

Installation

git clone https://github.com/asfandyar-prog/foundation_artificial_intelligence.git
cd foundation_artificial_intelligence

Running the Problems

# Tower of Hanoi
python hanoi_base.py

# Water Jug Problem
python cup3_base.py

# 4-Queens Problem
python 4_queen_base.py

Each script prints the full solution path from initial state to goal state.


📚 Key Concepts

Concept Description
State space Graph of all configurations reachable from the initial state
Uninformed search No domain knowledge — explores blindly (BFS, DFS, UCS)
Informed search Uses a heuristic function to guide exploration (A*, Greedy)
Admissible heuristic Never overestimates true cost — guarantees A* optimality
CSP Constraint Satisfaction Problem — assign values subject to constraints
Backtracking Systematically explore assignments, pruning invalid branches early

📖 References


MIT License · Made by asfandyar-prog