Next / Previous / Contents / Shipman's homepage

Abstract

Presents a method for solving crosspatch puzzles and a program embodying the method.

This publication is available in Web form and also as a PDF document. Please forward any comments to john@nmt.edu.

Table of Contents

1. Introduction to crosspatches
2. Installation
3. Operation of the script
3.1. Performance notes
4. Design of the script
4.1. Definitions of terms
4.2. Data structures
4.3. Overview of the solution algorithm
4.4. Initialization
4.5. Cyclic reduction
4.6. The recursive algorithm
4.7. The WordBank class
5. Code prologue
6. Imports
7. Manifest constants
7.1. UNK_CELL
7.2. COMMENT_CHAR
8. main(): The main program
9. usage(): Show command line argument usage
10. fatal(): Write a message and stop
11. showIsV(): Display “H” or “V
12. perpendicular(): Return the opposite orientation
13. class Puzzle: The top-level container
14. Puzzle.__init__(): Constructor
15. Puzzle.__input(): Read the puzzle file
16. Puzzle.__readFile(): Partition the input file
17. Puzzle.__digestGrid(): Parse the framework
18. Puzzle.__gridLine(): Parse one line of the framework
19. Puzzle.__findSlots(): Locate all the slots
20. Puzzle.__genSlots(): Detect slots in a row or column
21. Puzzle.__addSlot(): Add a new slot
22. Puzzle.__digestWords(): Parse the word list
23. Puzzle.__matchLengths(): Does the word list match the slot set?
24. Puzzle.__buildChoices(): Set up initial word choices
25. Puzzle.__buildSlotChoices(): Build the initial set of choices for one slot
26. Puzzle.__clueCheck(): Eliminate initial choices conflicting with clues
27. Puzzle.show(): Display the state of the puzzle
28. Puzzle.__showColHeads(): Column headings for .show()
29. Puzzle.__showRule(): Horizontal rule in .show() output
30. Puzzle.__showRow(): Show one row of the puzzle
31. Puzzle.showAllChoices()
32. Puzzle.whatCell(): Is there a cell at a given coordinate?
33. Puzzle.genCells(): Generate all the cells
34. Puzzle.whatSlots(): What slots intersect a given coordinate?
35. Puzzle.scan(): Traverse a row or column of the framework
36. Puzzle.nSlots(): How many slots are there?
37. Puzzle.genSolutions(): Generate all solutions
38. Puzzle.__cyclicReduction(): Eliminate choices at slot intersections
39. Puzzle.__reduceCycle(): Static elimination of word choices
40. Puzzle.__reduceCell(): Eliminate choices where two slots intersect
41. Puzzle.__reduceSlot(): Eliminate choices for one slot
42. Puzzle.__uniqueWordTest(): Require that a word be used only once in the puzzle
43. Puzzle.__uniqueSlotTest(): Find words that are choices for only one slot
44. Puzzle.__recurSolver(): Recursive solver
45. Puzzle.__choiceFits(): Does this slot choice fit the rest of the puzzle?
46. Puzzle.__crossingClash(): Does a perpendicular slot conflict?
47. Puzzle.__assumeChoice(): Try out an assumption
48. class Cell: One location for a character
49. Cell.__init__(): Constructor
50. Cell.addSlot(): Add an intersecting slot
51. Cell.genSlots(): Generate the slots intersecting this cell
52. class Slot: One place where a word goes
53. Slot.__init__(): Constructor
54. Slot.__str__()
55. Slot.__len__(): Return the slot length
56. Slot.__getitem__(): Slot position to puzzle position
57. Slot.__cmp__(): How to compare two slots
58. Slot.genCoords(): Generate all cell coordinates of a slot
59. Slot.findCoord(): Puzzle position to slot position
60. class WordBank: The word list and puzzle state
61. WordBank.__init__(): Constructor
62. WordBank.addWord(): Add a word to the word list
63. WordBank.__len__(): How many total words?
64. WordBank.wordsOfLen(): How many words have a given length?
65. WordBank.genAllWords(): Generate all the words
66. WordBank.genCandidates(): What words have a given length?
67. WordBank.mayBe(): Add one word choice to a slot
68. WordBank.isNot(): Remove one word from a slot's list of choices
69. WordBank.totalChoices(): How many total choices are in the current state?
70. WordBank.genSlotChoices(): What words are choices for a slot?
71. WordBank.slotCharChoices(): What letters are choices at a given position?
72. WordBank.cellChoices(): What characters are choices at a given coordinate?
73. WordBank.wordToSlots(): Which slots use a given word?
74. class Word
75. class Coord: One location in the grid
76. Epilogue