CSc 8710 Spring 2007
Homework 3:
Due Dates:
Problem 1: February 16, 2007 - Friday
Problem 2: February 26, 2007 - Monday

1. Write a Prolog program to "Solve" 9x9 Sudoku puzzles. In the remote case that you are not familiar with Sudoku, you are given a 9x9 matrix with some of the entries given and your task is to fill in the rest of the entries. In addition to dividing the matrix into nine rows and nine columns, the entries are also divided into nine 3x3 sub-matrices as shown in the sample puzzle shown below.

   

   Each entry must be a number between 1 and 9. The final solution must satisfy the constraints that each row, column, and sub-matrix must contain each of the numbers 1 to 9 exactly once.

   In Prolog, the Sudoku puzzle is represented as a list of "rows". For example, the following is a sample puzzle (initial configuration):

     [[_,6,_,1,_,4,_,5,_],
      [_,_,8,3,_,5,6,_,_],
      [2,_,_,_,_,_,_,_,1],
      [8,_,_,4,_,7,_,_,6],
      [_,_,6,_,_,_,3,_,_],
      [7,_,_,9,_,1,_,_,4],
      [5,_,_,_,_,_,_,_,2],
      [_,_,7,2,_,6,9,_,_],
      [_,4,_,5,_,8,_,7,_]]
   

   where the underscore entries are the unknowns and are represented by the anonymous variable. Write definitions of the predicates sudoku(L) and displaySolution(L) so that a puzzle may be solved using the following rule:

   solve :- 
     L = [
          [_,6,_,1,_,4,_,5,_],
          [_,_,8,3,_,5,6,_,_],
          [2,_,_,_,_,_,_,_,1],
          [8,_,_,4,_,7,_,_,6],
          [_,_,6,_,_,_,3,_,_],
          [7,_,_,9,_,1,_,_,4],
          [5,_,_,_,_,_,_,_,2],
          [_,_,7,2,_,6,9,_,_],
          [_,4,_,5,_,8,_,7,_]],
     sudoku(L),
     displaySolution(L).
   

2. Turing Machine Simulator

   Part 1: Basic Simulator

   Write a Turing Machine Simulator in Prolog. Assume a Turing Machine is described using two predicates:

     start_state(State).
     delta(FromState,ToState,ReadSymbol,WriteSymbol,MoveDirection).
   

   For example the following is a TM for accepting language with strings involving a's and b's and having equal number of a's and b's.

   start_state(1).
   delta(1,1,b,b,r).
   delta(1,1,x,x,r).
   delta(1,2,a,x,l).
   delta(1,5,#,#,l).
   delta(2,2,x,x,l).
   delta(2,2,b,b,l).
   delta(2,3,#,#,r).
   delta(3,3,a,a,r).
   delta(3,3,x,x,r).
   delta(3,4,b,x,l).
   delta(4,4,a,a,l).
   delta(4,4,x,x,l).
   delta(4,1,#,#,r).
   delta(5,5,x,x,l).
   delta(5,h,#,#,r).
   

   Note: States are numbered 1 thru n and h stands for the halt state; The # symbol is used to denote blank symbol on tape.

   The TM Simulator program will behave as follows under Prolog:

   [~/8710][4:27pm] pl
   Welcome to SWI-Prolog (Version 3.2.9)
   Copyright (c) 1993-1999 University of Amsterdam.  All rights reserved.
   
   For help, use ?- help(Topic). or ?- apropos(Word).
   
   ?- ['tm.pro'].
   tm.pro compiled, 0.00 sec, 3,196 bytes.
   
   Yes
   ?- ['equal.tm'].
   equal.tm compiled, 0.01 sec, 1,556 bytes.
   
   Yes
   ?- run_tm(abaaabbb).
   Final Tape Contents are:
   #xxxxxxxx#
   
   Yes
   ?- run_tm(abaaab).
   
   No
   ?- halt.
   [~/8710][4:28pm]
   

   Part 2: Step Mode

   Once you have developed the simulator program, improve the TM Simulator to enable step execution. A sample run in Prolog is for step execution is given below:

   [~/8710][4:28pm] pl
   Welcome to SWI-Prolog (Version 3.2.9)
   Copyright (c) 1993-1999 University of Amsterdam.  All rights reserved.
   
   For help, use ?- help(Topic). or ?- apropos(Word).
   
   ?- ['tmstep.pro'].
   tmstep.pro compiled, 0.00 sec, 4,040 bytes.
   
   Yes
   ?- ['equal.tm'].
   equal.tm compiled, 0.00 sec, 1,556 bytes.
   
   Yes
   ?- run_tm(abab).
   Tape: abab
         ^
   |: 
   Tape: #xbab
         ^
   |: 
   Tape: #xbab
          ^
   |: 
   Tape: #xbab
           ^
   |: 
   Tape: #xxab
          ^
   |: 
   Tape: #xxab
         ^
   |: 
   Tape: #xxab
          ^
   |: 
   Tape: #xxab
           ^
   |: 
   Tape: #xxab
            ^
   |: 
   Tape: #xxxb
           ^
   |: 
   Tape: #xxxb
          ^
   |: 
   Tape: #xxxb
         ^
   |: 
   Tape: #xxxb
          ^
   |: 
   Tape: #xxxb
           ^
   |: 
   Tape: #xxxb
            ^
   |: 
   Tape: #xxxb
             ^
   |: 
   Tape: #xxxx
            ^
   |: 
   Tape: #xxxx
           ^
   |: 
   Tape: #xxxx
          ^
   |: 
   Tape: #xxxx
         ^
   |: 
   Tape: #xxxx
          ^
   |: 
   Tape: #xxxx
           ^
   |: 
   Tape: #xxxx
            ^
   |: 
   Tape: #xxxx
             ^
   |: 
   Tape: #xxxx#
              ^
   |: 
   Tape: #xxxx#
             ^
   |: 
   Tape: #xxxx#
            ^
   |: 
   Tape: #xxxx#
           ^
   |: 
   Tape: #xxxx#
          ^
   |: 
   Tape: #xxxx#
         ^
   |: 
   Final Tape Contents are:
   #xxxx#
   Yes
   ?- run_tm(aba).
   Tape: aba
         ^
   |: 
   Tape: #xba
         ^
   |: 
   Tape: #xba
          ^
   |: 
   Tape: #xba
           ^
   |: 
   Tape: #xxa
          ^
   |: 
   Tape: #xxa
         ^
   |: 
   Tape: #xxa
          ^
   |: 
   Tape: #xxa
           ^
   |: 
   Tape: #xxa
            ^
   |: 
   Tape: #xxx
           ^
   |: 
   Tape: #xxx
          ^
   |: 
   Tape: #xxx
         ^
   |: 
   Tape: #xxx
          ^
   |: 
   Tape: #xxx
           ^
   |: 
   Tape: #xxx
            ^
   |: 
   
   No
   ?- halt.
   [~/8710]
   

   Part 3: Spy Mode

   Finally, modify the tmstep program so that we can do spying on a given state. Design a predicate, run_tm(Tape,P), which takes an additional parameter P: the state to spy on. The TM should execute in the same way as the original simulator (tm.pro, without step mode) but the TM should stop whenever the state P is reached and display tape contents. Upon hitting ENTER, the TM should continue executing and stop again at the given state, if it is reached. Call this file tmspy.pro