Homework Two

out 9/9, due 9/18

This homework will give you experience with solving problems using uninformed search techniques. Write code to solve the following two classic search problems using a programming language and search technique of your choice.

  • Knight's tour: A knight's tour is a sequence of moves that a knight can take on an NxN chess board such that the knight visits every square exactly once. Recall that a knight moves 2 space vertically followed by a 1 space move horizontally, or 2 space horizontally followed by 1 space move vertically. Your program must take a single command line argument, which is N, the size of the chess board, and then produce as output a sequence of board positions in a valid tour.
  • Cryptarithmetic: In cryptarithmetic you are given 3 words (w1, w2, w2) such there is an assignment of digits to letters in the words that satisfy the equation w1 + w2 = w3. No digit may be assigned to more than one letter. The classic example is SEND + MORE = MONEY, which is satisfied by O = 0, M = 1, Y = 2, E = 5, N = 6, D = 7, R = 8, and S = 9. Your program should accept as input 3 words (strings of letters only) and produce as output a satisfying assignment of digits to letters.
Note that there are many implementations of these problems online. Do not use them. Write your own code.

What to turn in: For the knight's tour, turn in a tour for an 8x8 chess board and the tour for the largest board you are able to solve (along with the value of N for that board). For the cryptarithmetic problem, turn in the output of your program for any 3 examples (you can find many of them online). The above should be handed in during class on the due date on paper.

Also, submit your code via blackboard along with a README on how to run it. Your code must run on a GL machine. In the README tell us what GL machine you tested it on. Make it easy to run your code because if we cannot get it to work we cannot grade it. Please submit your code as a single tar file. Do not use anything other than tar to bundle the files. You may compress the tar file as long as the file extension makes it clear what compression tool you used. To turn in your code via blackboard, click on the Assignments link and then click on Homework 2.