Assignment 7 (5%)

• Write a function(or set of functions) that unscrambles a simple puzzle
  • Input is a list of 9 elements, the numbers 1-8 in any order and the atom E
  • It is interpreted as a scrambled 3 x 3 matrix:

    (1 E 3 4 2 6 7 5 8) ==>  1 E 3 
                             4 2 6
                             7 5 8
                             
    
    

  • A legal move exchanges the E with one of it neighbours. We denote this by one of the atoms 'u, 'd, 'l, 'r, depending on wether the digit has to slide up, down, left, right to take the place of the E
• Your program should find and print a sequence of moves that transforms the scrambled puzzle to an unscrambled one:

  Start:   (1 E 3 4 2 6 7 5 8)      1 E 3 
                                    4 2 6
                                    7 5 8
  
  Up 'u:   (1 2 3 4 E 6 7 5 8)      1 2 3
                                    4 E 6  
                                    7 5 8
    
  Up 'u:   (1 2 3 4 5 6 7 E 8)      1 2 3
                                    4 5 6  
                                    7 E 8
  
  Left 'l: (1 2 3 4 5 6 7 E 8)      1 2 3
                                    4 5 6  
                                    7 8 E
  
  Output: (u u l)
  

• Hints:
  • Write a recursive function
  • Arguments are two lists of tuples, one for processed states, one for unprocessed states
    • Each tuple contains a configuration (list of 9 elements)
    • It also contains a sequence of moves to get there
  • Initially, the first list is (((init-config) ())) and the second one is empty
  • At each step:
    • Get the first element from unprocessed list
    • If it is ordered, you are done. Otherwise
    • Add it to the processed list
    • Generate the 2, 3, or 4 possible successors
    • For each successor: If the configuration is not yet on one of the lists, add it to unprocessed
    • Otherwise, ignore it
• Bonus: Write a function that accepts any size of square!