This repository demonstrates and describes the implementation of Search Algorithms and their application in different problems in Java.
- Java 17+
- Gradle
In the Jug Problem, you are given:
- Two jugs with known capacities:
- Jug A of capacity a liters.
- Jug B of capacity b liters.
- Unlimited water supply from a tap.
- No measuring marks on the jugs.
- The task is to measure exactly c liters of water using the two jugs.
- Fill: Fill the jug to its maximum capacity.
- Empty: Empty the jug until it is completely empty.
- Move: Pour water from one jug to the other until one is either full or empty.
This class defines a Jug object with the following instance variables:
- maxCapacity: The maximum capacity of the jug.
- currentCapacity: The current amount of water in the jug.
The Jug class provides methods to:
- fill the jug to its maximum capacity.
- empty the jug until it's completely empty.
- move water between jugs.
- Check whether the jug is filled or empty.
- copy the jug state.
This class inherits from the State class, which itself inherits from the Node class. It represents a specific state in the JugStateSpace.
It stores:
- A list of jugs and their current states.
- The edges of the state (i.e., possible transitions such as fill, empty, or move).
This class inherits from the StateSpace abstract class, which includes:
- An initial state and a goal state.
- A list of nodes representing the possible states in the search space.
Given an
- Each row must contain only one of each 1 to
$N$ without any repeats - Each column must contain only one of each 1 to
$N$ without any repeats - Each
$\sqrt{N} * \sqrt{N}$ subgrid must contain the digits of 1 to$N$ without repetition
Goal: To find the permutation of the
- State: The state is the grid with a selected cell that is modified.
-
Transitions: The transitions are the insertions from 1 to
$N$ - Cost: Assuming uniform cost
- Initial State: input matrix i.e:
- Goal State: There is not a static goal state that is defined the goal state is just whether the output matrix satisfies the constraints i.e:
- Guaranteed to find a solution.
- Admissible (in the case of uniform cost).
- Efficiency depends on the location of the solution.
- Uses a Queue
| ✅ When to Use | ❌ When Not to Use |
|---|---|
| Space is not a problem | Space is limited |
| Need to find a solution with the fewest steps | Solution is deep in the search tree |
| Very deep or infinite search trees | The branching factor is large |
Example Usage The Jug Problem
- Initialize a queue with the initial state and a hashmap for visited nodes (and their parent nodes to prevent cycles).
- While the queue is not empty:
- Dequeue the current state.
- Expand the current state by executing all available valid transitions (fill, empty, or move).
- If a generated state exists in the visited hashmap, ignore it.
- Check the generated state against the goal state:
- If it matches the goal state, backtrack through the visited hashmap to find the path.
- If not, continue the search.
- Enqueue valid states and mark them as visited.
- Mark the current state as visited if it doesn't have a parent node (mark parent as null).
Example Usage Sudoku
- Initialise a queue with the initial state and a hashmap for the visited nodes
- While the queue is not empty
- to get the currenState dequeue from the queue.
- expand the currentState by executing all available and valid transitions i.e the insertion of valid numbers in the cell from 1 to
$N$ - Check if the generated state meets the criteria of the goal state
- enqueue the valid states and mark the as visited
- If it matches the pre-conditions backtrack though the hashmap from the currentState and reverse the list.
- If not continue the search.
- Mark the current state as visited if it doesn't have a parent node (mark parent as null)
- Guaranteed to find a solution.
- Not admissible.
- Efficiency depends on the location of the solution.
- Uses Stack (Recursion)
| ✅ When to Use | ❌ When Not to Use |
|---|---|
| Space is restricted | Paths are infinite |
| Solutions are at similar depths | The search graph contains cycles |
| You have knowledge to allow ordering of nodes at each level | Some solutions are deep and others are shallow |
Example Usage The Jug Problem
- Adds the initial JugState to the visited hashmap, adds it to the result path.
- Checks if the current JugSTate is the goalState
- If it is returns the result path.
- else it continues
- Expand the states with the valid and available transitions
- For each expanded state checks whether the state has been visited.
- Recurse this by parsing the current expanded state into the search function. (steps 1-5)
- If the recursive search returns a non-empty path (indicating a valid solution), it is returned.
- if there are no more routes the branch is removed and the algorithm backtracks to previous state where it is removed from the result list. (returns a blank arraylist)
Example Usage Sudoku
- Compromise between BFS and DFS.
- Added extra variable of depth bound (d) which imposes backtracking when the frontier is at that depth.
- If the no solution is found at depth d increase d.
- Save nodes that are found at depth d to a pending list.
- If open is empty and the goal is not found move the pending list to the open list.
| ✅ When to Use | ❌ When Not to Use |
|---|---|
| Limited Space | Known shallow solution |
| Unknown Depth of the Solution: | Large branching factor |
| Can find the optimal solution | Non-Optimal Solutions |