Are you familiar with Kakuro (Cross Sums)? See
http://www.kakuropuzzle.com/ for an example. In every such puzzle the
top row and left column are all "black". I exclude these from the
following "rules": A valid puzzle meets the following rules: 1 - black squares are symmetric around center. (thus ditto for white). 2 - every white square has at least one white square neighbor vertically and horizontally. 3 - there is a path from any white square to any other white square. 4 - the upper left square is black 5 - there are at most 9 contiguous white squares. 6 - a black square followed horizontally by contiguous white squares has a number in its upper right corner that is the sum of the digits to be placed in the contiguous white squares. 7 - ditto for vertically, the number going in the lower left. 8 - there must be at least one combination of unique digits that totals to the expected sum. 9 - there must be one and only one solution to the puzzle that meets all expected sums. This leads to an interesting series of programming assignments. You would start with some # of rows and columns. Each time the program would print the result. Aim for a simple character representation of the board. Example: 1 2 3 4 +-----+-----+-----+-----+-----+ |XXXXX|XXXXX|11\XX|10\XX|XXXXX| +-----+-----+-----+-----+-----| 1 |XXXXX| 3\4 | | | 7\X | +-----+-----+-----+-----+-----| 2 |XX\12| | | | | +-----+-----+-----+-----+-----| 3 |XX\10| | | | | +-----+-----+-----+-----+-----| 4 |XXXXX|XX\5 | | |XXXXX| +-----+-----+-----+-----+-----+ There are many ways to represent such a puzzle. I offer the following list of lists where - 0 = black with no numbers - 0.r = row sum - c.0 = column sum - c.r = row and column sums - -1 = blank white square - any integer between 1 and 9 = white square with number (potential solution) Given that the above puzzle would look like: [[0,0,11.0,10.0,0], [0.3.4,-1,-1,7.0], [0.12.-1,-1,-1,-1], [0.10.-1,-1,-1,-1], [0,0.5,-1,-1,0]] Assignment - Solve one or more of these puzzles, if you are not familiar with them. Assignment - Take the above list representation of the puzzle and print the human-readable form as shown above. Assignment - Program for human to enter the layout of a puzzle. Assignment - Look up the shelve module. This is an easy way to save and restore Python objects. This will be very useful to save puzzles that are in progress and restore them later. Write a simple program to save and restores some trivial object. Assignment - Apply the shelve technology to save & restore puzzles. Assignment - Program for human to enter value(s) for a square, using the row and column number to identify the square, and to print the result on demand. Assignment - Evaluate the solution to see if all the sums are correct. Report errors. Assignment - Design a structure that would be indexed by a potential sum and # of contiguous white squares to contain the potential solutions for that combination. Example for sum = 5 and # squares = 2 ((1,4),(2,3)). Assignment - Fill that table with the potential solutions. Assignment - Use that table to put values in rows and print a potential solution to a puzzle. Assignment - Think of ways to optimize automated solving of a puzzle rather than just brute force trial-and-error. I realize that this can go on and on. I hope this is in the ballpark of sufficient interest and somewhat easy steps. Let me knw. -- Bob Gailer 510-978-4454 |
_______________________________________________ Tutor maillist - [email protected] http://mail.python.org/mailman/listinfo/tutor
