Method of constructing crossword puzzles by computer

Claim 1

A method for constructing an unsolved crossword puzzle in an electronic computer having processor means, memory means for storing data, input means and output means, said method comprising: (a) establishing in said memory means a crossword puzzle grid structure representing a two-dimensional array of cells, each of said cells being variables that contain data representing either a blocked state or an unblocked state of said cell, and each of said cells, when representing said unblocked state, additionally representing an unassigned state or an assigned state of said cell, and each of said cells, when representing an assigned state, also representing a letter of the alphabet; (b) establishing in said crossword puzzle grid in said memory means a crossword puzzle pattern, said crossword puzzle pattern comprising a majority of unblocked cells, a minority of blocked cells, and a plurality of wordslots, each of said wordslots comprising an one-dimensional array of at least two mutually-adjacent unblocked cells, some of said wordslots oriented across and some of said wordslots oriented down in an intersecting network of wordslots, and wherein most to all unblocked cells are in intersecting wordslots; (c) providing in said memory means a lexicon of words; (d) said computer analyzing each wordslot that includes at least one unassigned cell in light of said assignments and said lexicon to determine, for each unassigned cell in said puzzle, a set of letters that are assignable to that unassigned cell, a letter being assignable to that unassigned cell if it does not rule out all the words in said lexicon from completing a wordslot that intersects at that unassigned cell; (e) said computer attempting to fill said wordslots with words from said lexicon by following the steps comprising: (1) said computer selecting an unassigned cell; (2) said computer selecting a letter from the set of letters that are assignable to the cell selected in step (1); (3) said computer assigning the letter selected in step (2) to the cell in step (1); (4) said computer analyzing each wordslot that was altered by any of the steps (3), (5) and (6), to update for each unassigned cell in said wordslot, the set of letters that are assignable to that unassigned cell, a letter being assignable to that unassigned cell if it, together with any existing assignments, does not rule out all the words in said lexicon from completing a wordslot that intersects at that unassigned cell; (5) whenever said computer updating a set of assignable letters results in an empty set of assignable letters, said computer reversing a sufficient number of assignments to restore the set of assignable letters to a non-empty condition; (6) whenever said computer updating a set of assignable letters results in a set of assignable letters that contains only one letter, said computer forcing the assignment of that one letter and repeating step (4); (7) said computer repeating steps (1), (2), (3), (4), (5) and (6) until all unassigned cells have become assigned cells or all selections have been attempted and the puzzle cannot be constructed.

Claim 2

A method for constructing an unsolved crossword puzzle in an electronic computer having processor means, memory means for storing data, input means and output means, said method comprising: (a) establishing in said memory means a crossword puzzle grid structure representing a two-dimensional array of cells, each of said cells being variables that contain data representing either a blocked state or an unblocked state of said cell, and each of said cells, when representing said unblocked state, additionally representing an unassigned state or an assigned state of said cell, and each of said cells, when representing an assigned state, also representing a letter of the alphabet; (b) establishing in said crossword puzzle grid in said memory means a crossword puzzle pattern, said crossword puzzle pattern comprising a majority of unblocked cells, a minority of blocked cells, and a plurality of wordslots, each of said wordslots comprising an one-dimensional array of at least two mutually-adjacent unblocked cells, some of said wordslots oriented across and some of said wordslots oriented down in an intersecting network of wordslots, and wherein most to all unblocked cells are in intersecting wordslots; (c) providing in said memory means a lexicon of words; (d) said computer analyzing each wordslot that includes at least one unassigned cell in light of said assignments and said lexicon to determine, for each unassigned cell in said puzzle, a set of letters that are assignable to that unassigned cell, a letter being assignable to that unassigned cell if it does not rule out all the words in said lexicon from completing a wordslot that intersects at that unassigned cell; (e) said computer attempting to fill said wordslots with words from said lexicon by following the steps comprising: (1) said computer selecting an unassigned cell; (2) said computer selecting a letter from the set of letters that are assignable to the cell selected in step (1); (3) said computer assigning the letter selected in step (2) to the cell in step (1); (4) said computer analyzing each wordslot that was altered by any of the steps (3), (5) and (6), to update for each unassigned cell in said wordslot, the set of letters that are assignable to that unassigned cell, a letter being assignable to that unassigned cell if it, together with any existing assignments, does not rule out all the words in said lexicon from completing a wordslot that intersects at that unassigned cell; (5) whenever said computer updating a set of assignable letters results in an empty set of assignable letters, said computer reversing a sufficient number of assignments to restore the set of assignable letters to a non-empty condition; (6) whenever said computer updating a set of assignable letters results in a set of assignable letters that contains only one letter, said computer forcing the assignment of that one letter and repeating step (4); (7) said computer repeating steps (1), (2), (3), (4), (5) and (6) until all unassigned cells have become assigned cells or all selections have been attempted and the puzzle cannot be constructed.