Week 12 - Continue Twiddle / Consider another Uninformed Search

Last week we looked at the very introduction of "Intelligent Search" - that is, how to search for a solution to a problem. We looked at two search techniques - Breadth-First Search and Depth-First Search - and on two different problems - the Analysts/Hackers Canoe problem, and the Romanian Map prolbem.

At the Community of Practice (CoP) event on Saturday you spent time creating the children() function for an online game called Twiddle. If you have not done so yet, please explore that activity.

• Understanding Twiddle and coding the children() function.

Continuing Twiddle

[NOT graded - But strongly encouraged]

For this assignment you should write a program that will solve a Twiddle board using a Breadth First Search based on the generic search pseudocode. You can and should use the code from last week to guide you:

• canoe_BFS.py
• canoeNode.py
• romania_BFS.py
• cityNode.py
• queue_code.py

Step One

You will need to make a node class for this problem. This is actually trivial. The canoeNode is basically exactly what we want. In this problem, each node should know its value (the length 9 board string), it's parent value (ditto), and the move that got us from the parent to the child. This is exacty what we were storing for the canoe problem. So that node can be reused.

Step Two

Next, we need to do a minor update to the children() code from the CoP. To make this easier to process for you, I asked you to create a children() function that takes in a String and returns a list of 8 children Strings. This made it really easy to visually see it was working. But it doesn't align with what we were doing last week when we created expansion functions that took in a node and created children nodes. You will need to slightly modify the chidren() code so that it follows this pattern. This means

1. Taking in a node instead of a String
2. Using getValue() from this node to extract the board String [Trivial]
3. Doing the same manipulation to create a child String
4. But when adding this child to the list you need to make it a child NODE rather than a child STRING
   1. A node knows its value (what you just generated), it's parents value (the String you found in step #2), and it's move.
   2. Which children() function you use (I showed you three last week) will have an impact on how this is actually done

Since moving on to step #3 requires getting this part to work, I have provided my modification below if you get stuck.

Step Three

Finally, create the BFS() function based on our Breadth First Search code from last week.

• In a file called twiddle.py
• Create a function called BFS()
• THat takes in one length 9 String as input
  • You CAN ASSUME this this contains one each of the numbers 1-9.
  • There will be no spaces or punctuation.
  • For example, the board used above as an example would be entered as "957231846". 
• and prints the sequence of moves that will solve this puzzle (see below for the format)
• You should implement the Breadth First Search strategy for the generic search code as we have been discussing at the meetup and in the lecture videos:
  • searchPseudocode.pptx
• When a solution is found you need to print out the sequence of moves that will get you from the initial state to the goal state.
• 

Note: With the way we have been creating our explored set it takes a long time to check if a "new" node is truly new or one we have seen already. This means the runtime on this program is very poor at this point. You should be able to get a length 4 solution in a few seconds and a length 5 solution in a few minutes. After that, it will require major efficiency modifications to speed this up. I will talk about that later.

From experience

1. As you begin testing your solution make sure that it works on simple one move solutions.  If your code can't quickly solve a board that only needs one move than you CERTAINLY can't solve deeper solutions.  The following boards all are solvable with ONLY one move:
   • 413526789  (Solution: A')
   • 253146789  (Solution: A )
   • 152463789  (Solution: B' )
   • 136425789  (Solution: B )
   • 123746859  (Solution: C' )
   • 123586479  (Solution: C )
   • 123485796  (Solution: D' )
   • 123469758  (Solution: D )
2. Once you have those working move up to a few solutions of only two moves.  Again, if your code can't find a solution to these boards almost instantly (no more than 2 seconds) than you have a larger issue:
• 236154789    (Solution: B A )
• 142763859    (Solution: B'  C' )
• 413582796    (Solution: D' A' )
3. Once you master those then you can test the deeper boards.  Here are a few other boards of particular depths:

4 moves (2-10 seconds?)	5 moves (0.5 - 3 minutes depending)	6 moves (Longer than you want)
239654178 (Solution: B C D A )	359264178 (Solution: A B C D A)	675381429 (Solution: A C' B C' A B)
185372649 (Solution: C B' C B')	426539178 (Solution: A' C D B A )	361547289 (Solution: C B A B C' A ")
461293587 (Solution: B' D C A' )	518397246 (Solution: C A' B D' C)	486152739 (Solution: C' A C A' B A' )
234718956 (Solution: C' B D' A )	439165728 (Solution: C B C' D A')	436892751 (Solution: D' D' B D A' D')

 

My Solutions

When you have your own solution, or you just can't get it to work, you can view my solutions.

• Solution to step #1 [Absolutely the same as canoeNode.py from last week]
  • twiddleNode.py
• Solution to step #2 [My modification to children() to work with nodes]
  • revisedChildrenSolution.py
• Solution to step #3 [Can solve 5 move solutions but takes way too long after that]
  • twiddle_schafer.py
  • queue_code.py [The same as previous weeks]

Why so long?

If you played with the above solutions you will note that they take 2-3 minutes for the last two in the 5 moves category. Why?

• Watch : Understanding the time bottle neck in the previous solution [Video, 10 minutes]

• Consider a new way to manage the ExploredSet that use dictionaries rather than lists, and thus uses far fewer operations when looking if a "new" node is really new or not.
  • Code: explored_set.py

• Furthermore, we can speed it up a bit more (as well as help us out when we move to A* in two weeks) by Changing the twiddle code to contain an actual pointer to the parent node rather than a copy of it's board.
• To do this you, Step 1:
  • Change the constructor to go from:
    • 
  • to
    • 
  • Notice that we are putting an actual Node object in as the second parameter (node is a variable that knows the parent node) rather than a String object (board was the String value from the current node.)

• And step 2
  • This then means that building of the path when we find the solution is actually easier because we don't have to look up the parent node based on it's board, we actually KNOW the parent node because we have a pointer/reference to it. This means we can go from
    • 
  • to
  • 

   

• My final version of this BFS code is here:
  • Code: twiddle_schafer.py

With this modification, the length 5 solutions from above were only a few seconds, and the length 6 solutions about a minute or less. However, length 8 solutions are still more than 30 minutes (I don't know how much more. I stopped the program!)

CHALLENGE

• Do you want to test if you get it? [If you are looking to see if you understand this, and you want to challenge yourself, here is another assignment you could create as BFS search. Please note, this is ENTIRELY optional and "for fun"]
• Light's Out explanation video
• The websites I showed in the video
  • https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/flip.html
  • http://www.logicgamesonline.com/lightsout/
• Light's Out - My Solution [Don't look at this until you really truly have tried to solve it]