Artificial Intelligence: 2. Rule based Colouring nxn board using AI search algorithms

Code: GitRepo

Observations:

Swap method (swapping with adjacent elements)

· If the swap algorithm is used, the same above observations apply.

· The greedy best first search algorithm gives the output in a lot less time than compared to BFS and DFS.

· Greedy sorts the queue using a heuristics of the least number of collisions tending to closer to the goal.

· Now using this the output matrix has the same frequency of colors as the input matrix.

· The output is not guaranteed if the input matrix has input colors in a way that there will be no possible permutation to arrange with no two same colors adjacent to each other.

· The input matrix is generated randomly.

· DFS and BFS works in reasonable time if the input matrix size <5

· To compute for the below 10x10 matrix using swap method, the “greedy best first search algorithm” took the following statistics Queue: 119569 Extended: 1744 Cost: 203

· DFS without extended list gives redundant and non optimal solutions, and many of them are found when enqueuing the items to the queue.

· If only the first collision is considered to swap, then the following wont have a solution, which actually has a solution. For the best deep searching, we have to consider possibilities of all the collisions, which might be a optimal method as for every collision there will be at least 2 possibilities.

[1, 1, 1]

[1, 2, 2]

[2, 2, 2]

Exchange method (replacing with a possible value)

· I found that plain DFS is much better in this scenario, as DFS will solve a collision and then will try to solve that only again.

· BFS also gives a solution but might take a little time.

· The best is if we add a little heuristic to it, I took the sorting order of the number of collisions (greedy best first search), and this gives the correct possibility in blazingly fast.

· The BFS and DFS is not restricted to 5 size for a reasonable timed output.

· The solutions are guaranteed.