Artificial Intelligence: 1. n-puzzle using AI Search Algorithms

Code: GitRepo

Observations:

• Without any heuristics, I found that BFS is much better than DFS in this particular case, as DFS goes on solving to the depth on one particular side.
• There are at most 4 possibilities at every step, in DFS the time taken is highly dependent on taking the right step, for example, if there are 4 possible steps and DFS takes a step which doesn’t result in the output, DFs will now complete all possible combinations in that depth and then only return and check for another
• In plain BFS and DFS without any extended list, the queue size increases a lot, as it also checks for the sequence that is already checked. This can also be considered as brute force. Without extended list, the moves can be very unintelligent repeating the same moves again and again.
• Few times there’s a possibility that DFS will go into infinite loop, shifting left to right and right to left if there is no extended list.
• With the use of the extended list, there is no way for DFS to go into a infinite loop, it might take some time but will definitely give an output. But the cost keeps on increasing at first as it goes to one depth.
• And I also found that for [[0,3],[1,2]] the mentioned array and any possible outputs from that don’t have any solution
• When using A* the heuristics actually using f(n) = g(n) + h(n). I counted each previous path cost as 1, incrementing in each enqueuing process and calculating the Manhattan distance as the heuristic cost.
• IDA* is same as A* which has an iterative depth bound.
• IDA* allows having less number of items in the queue than that of A*

For the below input, calculations were done
[2, 0, 3, 4],
[1, 5, 6, 7],
[9, 11, 12, 8],
[13, 10, 14, 15]

• The above input is arranged in a way that BFS will give a better solution
• Extended size is nothing but the number of items that it checked at that point

Search Algorithms Used:

• BFS
• DFS
• BFS (With Extended List)
• DFS (With Extended List)
• A*
• IDA* (with 1 bound increment)

• We can see that A* found it many iterations before than even BFS with A*
• If we check the same using IDA* the queue size in IDA* will be much less than that of A*
• I didn’t write DFS results because it was taking so many hours.
• DFS is go into costs of more than 40,000+ (even DFS with extended list)
• BFS + Extended List gave the solution at a cost of 11, same as A* and IDA*
• Few times DFS and BFS will give different solutions, in which both might be correct, and I can bet on BFS to give a better least cost solution.