Sample Modules

The following is a list of zipped Eclipse project files (more might be added during the quarter). Please feel free to download, unzip, run, and study these scripts (both their code and their run-time behavior). Programmers gain tremendous insight into all facets of programming by studying the code of other programmers (especially those with more experience; and I am happy to improve my code based on your observations -nothing is perfect). A good programmer typically makes elegant use of the required language features, resulting in smaller, more elegant code.

All downloadable projects are listed alphabetically; you can also search this page for keywords. All are zip files, so unzip them first. Most project files require the Download: standard course library which contains a variety of useful modules. If you followed the Eclipse installation instructions, you should have already created the courselib folder in your workspace and populated it with these modules.

Download: Backtracking Search
This project contains a general solver for all backtracking search problems: problems are solved by binding aspects to values, generating every possible possibilities and determining which are solutions; one function finds a/one solution, another finds all solutions. It also contains three files that define the Problem/Aspect classes needed by the solver and scripts to solve actual problems via backtracking search.

1. Solving the N Queens problem: Can N queens be placed on an NxN chessboard so no queen can attack (horizontally, vertically or on a diagonal) any other queen. Here is a sample solution of the 4 Queens problem.

      +---+---+---+---+
      |   | Q |   |   |
      +---+---+---+---+
      |   |   |   | Q |   
      +---+---+---+---+
      | Q |   |   |   |
      +---+---+---+---+
      |   |   | Q |   |
      +---+---+---+---+

2. Solving Sudoku puzzles: Can a 9x9 square (read from a file) have its empty entries filled so that every row and column contains the numbers all the numbers 1-9, and 3x3 squares comprising the 9x9 cube likewise each contain all the numbers 1-9. Here is a sample problem (on the left) and solution (on the right).

      9 6   | 1   4 |   5                      9 6 3 | 1 7 4 | 2 5 8
          8 | 3     | 6                        1 7 8 | 3 2 5 | 6 4 9
      2     |       |     1                    2 5 4 | 6 8 9 | 7 3 1
     -------+-------+------                   -------+-------+------
      8     | 4   7 |     6                    8 2 1 | 4 3 7 | 5 9 6
          6 |       | 3                        4 9 6 | 8 5 2 | 3 1 7  
      7     | 9   1 |     4                    7 3 5 | 9 6 1 | 8 2 4
     -------+-------+------                   -------+-------+------
      5     |       |     2                    5 8 9 | 7 1 3 | 4 6 2
          7 | 2   6 | 9                        3 1 7 | 2 4 6 | 9 8 5
        4   | 5   8 |   7                      6 4 2 | 5 9 8 | 1 7 3

3. Solving Anagrams: For any input of words, find all sequences of words (of a certain or arbitrary length, each rom some dictionary of legal words) that contain exactly those characters (including repetitions). For example, the word California has an anagram racial info.

Download: Collatz Conjecture
The Collatz conjecture states: starting with any positive number, repeat the process "If it is even, halve it; if it is odd, multiply it by three and add one" and eventually the remaining value reduces to one. No one has been able to prove this conjecture, but a short script allows us to investigate it (and others have examined billions of different values and found no counterexamples). It is interesting to observe the number of cycles required to reduce the starting number to 1, looking for a pattern. This script is highlighted in the debugger handout.

Download: Craps Statistics
This script prompts the user for the number of craps games to play (craps is a dice game whose rules are explained in the block comment at the top of this script). It then simulates that many games of craps, printing the number (and percentage) of wins, losses, dice throws (and average dice throws per game), elapsed time, and game playing speed. This script is used inthe problem set for the debugger handout.

Download: Regular Expression Tester
This script is a complicated driver for testing methods in the re (Regular Expression) module. There are boths simple and complex features dealing with entering patterns and testing for matches, searches, finds, substitutes (with replacements), and splits. Regular Expressions are tersely illustrated in a lecture.

Download: State-Space Search
This project contains a general solver for all state-space search problems: problems are solved by generating sequences of operators to transform the start state of a problem into its stop state; one function finds the optimal (minimum operators) solution by breadth-first searching, another tries to minizmize the number of states explored but cannot be guaranteed to find the optimal solution (unless its heuristic satisifes the A* property). It also contains a files that define the Problem/Operators/State classes and a script needed by the solver to the water-jugs problem.