Week 13b - A* for Twiddle

Create the heuristic function (Target date: Sunday, November 20)

Last week I asked you to write a heuristic for Twiddle.

This is my solution:

• My solution

Update the Node class (Target date: Friday, November 25) [Yes, I know this is the week of Thanksgiving. Do what you can]

How much work this step takes will depend a little bit on where you are at with your Node class.  You should have had a solved BFS search for Twiddle. My sample solution looked like the following:

• originalTwiddleSolution.py

Then I had asked you to consider a revised Node class that used magic methods to allow them to be comparable to each other based on the length of the path.  It might have looked like this:

• RevisedNode.py

To get this Node to work with the A* search we need to do several small, related steps:

• incoporate the heurstic() function above in to the Node class
  • Note, this will mean changing the function so it doesn't take in a parameter for the board but uses the Node's board itself.
  • A sample call might look like this:
  • 
• create a fValue() function which returns the sum of the currentValue plus the heurstic() value
  • A sample call might look like this:
  • 
  • Notice that if we make the Node that results from turning A clockwise that all of this data is correct:
• modify the six magic methods so they are comparing based on the fValue() result rather then the currentValue() result
  • A sample call might look like this:
  • 

I will post my solution to this portion on this page after the target date listed above.

Modify the search (Target date: Monday, November 28)

If you get this far, the rest is EASY.

Using your previous Twiddle solution (or mine if you prefer) modify the BFS search to be an A* search.  This requires:

• Replacing the Queue with a PriorityQueue
• Replacing the Node with the new Node created above
• eliminating the exploredSet

Seriously. That's it. Now you should be able to run a search on a larger board in MUCH faster time.

As an example this is what I got when I compared a length 6 board using my previous solution with my A* solution

I tried to do a comparison with a length 8 board. I got the following answer for A* but had to manually kill the program after 30 minutes without an answer when doing DFS. [No exaggeration]