This program asks the user to input unique numbers from 0-8 in a 3x3 grid, that will serve as the input for the 8- puzzle. The program will then utilize IDS and A* search to find the solution, solution path, solution cost, number of nodes expanded, and the running time.
| ↑ | ||
| ← | _ |
→ |
| ↓ |
An 8 puzzle is a simple game consisting of a 3 x 3 grid (containing 9 squares). One of the squares is empty. The blank tile can only be moved to the adjacent cells. The objective is to move the empty square around into different positions and reaching the state of the numbers as displayed in the "goal state".
| Default Goal State | [1] Easy mode | [2] Medium mode | [3] Hard mode | [4] Worst mode | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
|
|
Aside from the pre-set starting configuration of the puzzle, the user can also give their desired starting config.
Similarly, the user can also provide their own desired goal state to try to reach.
The program will promptly give a warning if the goal state is impossible to reach, from the starting position.
-
- The user shall input the desired Initial state. The program will alert the user if ever the default goal state is impossible to reach when starting from the chosen initial state.u
- The user shall input the desired Initial state. The program will alert the user if ever the default goal state is impossible to reach when starting from the chosen initial state.u
-
- The user may choose and enter their own desired Initial state, as well as the targe Goal state. The program will alert the user if ever the chosen goal state is impossible to reach when starting from the chosen initial state.
- The user may choose and enter their own desired Initial state, as well as the targe Goal state. The program will alert the user if ever the chosen goal state is impossible to reach when starting from the chosen initial state.
-
- Additional information about how the algorithm is solving the problem is printed. This helps make sure the program is behaving as intended, especially during development.
- Additional information about how the algorithm is solving the problem is printed. This helps make sure the program is behaving as intended, especially during development.
- Iterative Deepening Search(IDS)
IDS (or IDDFS) is a state space/graph search strategy in which a depth-limited version of depth-first search is run repeatedly with increasing depth limits until the goal is found. It isa a graph traversal and path search algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. One major practical drawback is its O(b^d) space complexity, as it stores all generated nodes in memory.
- A * Search Algorithm
A* search algorithm is an informed search algorithm using heuristics (in this case, manhattan distance) to estimate the cost to reach the goal, and making informed decisions based on that cost. It keeps track of the nodes based on their estimated cost (f-value), where f(n) = g(n) + h(n), g(n) is the cost of the path from the start node to node n, and h(n) is the heuristic estimate of the cost from node n to the goal.
Using IDS on problems that require more than 16 steps is will take an unreasonable long time because there is no optimization to prune repeated states in the search tree. The algorithms in this program could be further optimized to remember, then ignore repeated states (pruning).
| Algorithm | Completeness | Time Complexity | Space Complexity | Optimality |
|---|---|---|---|---|
| IDS | YES (no infinite paths) | O (b^d) | O (bd) | Yes *if step cost is constant |
| A* | Yes | O (b^d) | O (b^d) | Yes |
*where b is the average branching factor of the search tree and d is the depth of the goal node.
-
IDS is a variation of depth-first search (DFS) that addresses the limitations of DFS, such as potentially getting stuck in deep branches and not being able to find a solution within a reasonable time or memory constraint. needs to search until the end of the tree branch. Repeated generation of already explored states makes the time complexity expensive.
-
Although A* search is optimal, the space complexity is a drawback because it needs to store all the explored states. In the worst case, where the A* algorithm explores the entire search space, the time complexity of A* search with the Manhattan distance heuristic is exponential. However, in practice, A* search is often much more efficient than the worst-case scenario because of the heuristic function. The Manhattan distance heuristic is admissible, meaning it never overestimates the cost of reaching the goal state. With an admissible heuristic, A* search is guaranteed to find the optimal solution. Additionally, the heuristic helps guide the search towards the goal state, reducing the number of unnecessary states explored.
- BALANA, Renmar
- BORRERO, Jan Lance
- SABAS, Jessa Lorenza
BSCS 3-C (2021-2022)