dpigeon / heuristic-indonesian-puzzle Goto Github PK

As a user, I want to create an A* algorithm so that it find the optimal solution path.

As a user, I want to build an A* algorithm from inputs given to give us the proper searched nodes and solution path. The algorithm must follow f(n) = g(n) + h(n) where

• f(n): estimate of total cost along path through n
• g(n): actual cost of path from start to node n
• h(n): estimate of cost to reach goal from n (heuristic #32)

In summary, it will have to keep track of the depth (g) and the estimate (h). The smaller f(n) will be chosen each iteration. The heuristic h will have to be ran on all nodes to evaluate their estimate.

This is dependent of:
#32
#34

Criteria of Acceptance:

• Is the algorithm optimal
• Can we get the node searched in a text output
• Can we get the optimal path
• Is it fast and not too complex

As a user,

I want to be able to use nodes that will be used to store the state of a board.

Acceptance Criteria:

• Define the class
• Have private members such as values, etc
• Have a reference to their childrens

A node should have:

As a user,

I want to be able to see the last move step when the solution path reaches the goal state.

Acceptance Criteria:

• Show the last step on when node is goal state

As a user, I want to create a Best First Search algorithm so that it find the solution path.

As a user, I want to build a Best First Search algorithm from inputs given to give us the proper searched nodes and solution path. The algorithm must follow f(n) = h(n) where g(n) is 0.

• f(n): estimate of total cost along path through n
• h(n): estimate of cost to reach goal from n (heuristic #32)

In summary, it will have to keep of the estimate (h) only. The smaller f(n) will be chosen each iteration. The heuristic h will have to be ran on all nodes to evaluate their estimate.

This is dependent of:
#33
#32

Criteria of Acceptance:

• Can we get the node searched in a text output
• Can we get the optimal path
• Is it fast and not too complex

As a user,

I want to be able to see the board flip the 0 --> 1 and 1 --> of the surrounding of the tiled touches (up and down, not diagonally).

Acceptance Criteria:

• Flip from 0 to 1
• Flip like shown on figure below
• Generate each new state board in a list to get ready to prioritize them here #3.

As a user,

I want to optimize the DFS algorithm so that it is faster than it is right now.

As a user,

I want the algorithm A* and BFS to backtrack our heapQueue by looking at parents of the nodes so that we can put them perfectly in our closed list.

Acceptance of Criteria:

• Can a node look at its parent
• Can we track all parents
• Can we put them in the closed list in the end
• Do we get a good solution path

As a user,

I want to be able to read the whole file and create a list of board

Acceptance Criteria:

• Read whole file
• Output a list of board on command line
• The size of the list of matches size of the file

As a user,

I want to design a heuristic so that I can search and find the fastest possible path within the board. We should at least have 3 heuristics so that we can test them.

Acceptance Criteria:

• First Heuristic: count the number of 1's -->
• Second heuristic: Try each index and see if they produce 1's. sum up the heuristic (would need to be quick so we need an algorithm of generate possible moves in 1D
• A third heuristic: heuristic 1 + heuristic 2

As a user,

I want to have a base code that all the developers can work and begin with.

Acceptance Criteria:

• Structure of files
• Main file (Puzzle.py)
• Read input file and display the board with it

As a user,

I want to be able to virtually create a tree of boards (nodes) to store the actions and nodes. Also, an open and closed list must be generated with a goal state function.

Acceptance Criteria:

• Has to have a list of state boards (nodes)
• Must be able to add edges, nodes
• Check the goal state function

As a user,

I want to prioritize the boards that has its first white token(s) at an earlier position based on a left-to-right, then top-down order.

Acceptance Criteria:

• Compare all the board nodes
• Use it for the next action step

As a user,

I want to be able to create and write the search output of a board for DFS.

Display the search path (list of nodes that have been searched).

• One line for each node
• Each line format: f(n) g(n) h(n) 111101100
• If value of f(n), g(n) or h(n) are irrelevant, display them as 0.

Acceptance Criteria:

• Create and write to files
• Output each individual board with #_dfs_search.txt
• Write like the format

As a user, I want to be able to transform the values of the token touched to the actual board token coordinates.

As a developer, I want obtained what token was pressed in order to see the solution path better in the output here #5.

Acceptance Criteria:

• Define the board's dimension according to the coordinates (min is A to C for 3x3 and max is A to J).
• Pass in the values and get a touched token in string

As a user,

I want to generate a BFS tree that will be based of A* so that it derives of it.
If a solution is found after searching <= max l nodes, your program will display the solution
using the same format as indicated above.

f(n) = 0 + h(n)

where g(n) = 0

Acceptance of Criteria:

• g(n) = 0
• Derive from A* so that f(n) = 0 + h(n)

As a user,

I want to generate an A* algorithm so that it traverses the whole program.
If a solution is found after searching <= max l nodes, your program will display the solution
using the same format as indicated above.

f(n) = g(n) + h(n)

Using a priority queue as an open list, we can either use the queue.PriorityQueue with best case O(n) and worst case O(n^2) compexity or the heapq which tends to be better and faster.

Acceptance of Criteria:

• f(n) = g(n) + h(n)
• Did we use a fast data structure such as heapq

As a user,

I want to run the DFS algorithm.

Acceptance Criteria:

• #3
• #8
• #9
• #10
• #26
• #28

As a user,

I am unable to input any board I want. Indeed, 0's cannot be put in front of the value column in the input file. For example:

If n = 3 with values = 001010101 would not work since our parser would only see 1010101 and disregard the two first 0's.

Acceptance Criteria:

• Change the integers to strings
• Accept any type of integers

As a user,

I want to be able to see the time taken to go through the DFS algorithm so that I have a better understanding of it.

As a developer, I want to see how well some inputs can perform with time better than the others. This will be very useful for examples in the report.

Acceptance Criteria:

• Define a start and stop time
• Use the time Python library

As a user, I want to optimize the last algorithms we have implemented so that we are sure that they deliver the real optimal solution.

As a user, I want to compare each estimate in the heap queue and see if there is a smaller estimate in the open or closed list. If there is, we must update the list by getting the node, removing it and adding the new low estimate node in the heap queue. Don't forget that heapify must be used each time we delete a node in the list so that we keep the order of the heap.

Acceptance of Criteria:

• Are nodes with smaller estimate f(n) update with the old one
• Do we get a fast solution
• Do we get a good optimal solution

As a user,

I want to write a report of 4-5 pages with the information written in the requirements.
Project 1: Final Report

As a user,

I want to be able to create and write the solution output of a board for DFS.

If found within max_d levels, I want the program to display the initial configuration preceded by 0 and then show each move solutions with A1 0 1 1 1 1 1 after.

If no solution after searching > max_l nodes, then no solution.

Acceptance Criteria:

• Create and write to files
• Output each individual board with #_dfs_solution.txt
• Write initial configuration & each moves afterwards until we reach the goal state