Generating crosswords with SAT Solver
On Habré there were several articles about the generation of crosswords. In one of them, “The most difficult crossword made by a computer” was told about a very difficult crossword made by a computer, which “had to help a little” manually. The second article, “Crossword Formation Algorithm,” tells about the algorithm created by the author for creating crossword puzzles, and notes that this “most difficult crossword puzzle” remained unconquered and says that “this unconquered peak might inspire someone to a new assault!”. Well, you can take the challenge. What came out of it, look under the cut.
In the beginning I will give this most difficult crossword puzzle:
The first thing to find is a list of words that are used in the construction of this crossword. Two files from the above articles were taken as such a list - one file with Russian words, one file with English. Then it was necessary to solve the main question - what algorithm to use to compile this crossword. Actually “difficult” this crossword does not the number of words, but the number of their intersections. It is clear that the brute-force attack is not suitable here, since the enumeration of all the options would take too much time. In the aforementioned article, many heuristics were considered to speed up the brute force process; however, this crossword was never written in Russian or in English. You can continue to come up with other heuristics to speed up the solution, but most of them have already been invented and implemented in the SAT solvers. Therefore, it is possible to translate the task into a form understandable by the SAT solvers and use one of them.
What is a SAT solver and what information it expects at the entrance I considered in the article “Solving the Tile Problem with the SAT Solver Using the Example of Pentamino” . In the case of generating a crossword puzzle, a slightly different approach is needed to formulate the problem in conjunctive-normal form, which I will now state.
The first thing to do is to sort all the words from the list into groups. Each group will contain words of the same length. Obviously, for each word in the crossword grid, you can select a word from the group with the corresponding length. Let's compare each word from the group which can be written in one word from the grid to a boolean variable. This variable will be true if the given word from the group will be written in this word from the grid and false otherwise.
Now we will make a formula describing our task, that is, we will actually impose restrictions on our variables. Find all vertical word crossings with words horizontally. For each intersection, we determine which pairs of words are combined with each other and which are not. However, a problem arises here, since the number of such pairs may exceed one million for one intersection. Therefore, we use a different approach. Sort the words in the group that corresponds to the word horizontally by the letter that stands in the position of the intersection of these two words. Do the same for the word vertically. Obviously, the appropriate words will have the same letter at the intersection. We introduce an additional variable for each letter that occurs at least in one word horizontally and vertically. Now the condition that the two words are combined with each other will be that at least one such variable will be true. Thus, for each intersection, one clause consisting of variables corresponding to letters will be added. Now it is necessary to associate variables corresponding to a specific letter with words containing this letter in the position of the intersection of words. This is done by a set of clauses that ensure that two boolean variables have the same values. And finally, it is necessary to ensure that there are no identical words in the crossword. To do this, for each word from the database we add clauses of the form (not x_i V not x_j), where x_i is the variable corresponding to its instance in one word from the crossword puzzle grid, and x_j is the variable corresponding to its instance in another word from the crossword puzzle grid.
Generating this “most difficult crossword puzzle” using Russian words takes a few minutes on an Intel 2600K 3.5 GHz with 16 gigabytes of memory. Creating a crossword puzzle using English words took about twenty minutes.
After that, I tried other crossword grids. For example, I managed to make a crossword of English and Russian words in the form of a square 6 by 6, where all the words intersect.
Next, I bring the resulting crossword puzzles. Those interested can solve them.
The use of SAT Solver raises the complexity of crossword puzzles that can be generated. As in the previous article, I want to set the next unconquered peak - to make a crossword puzzle of Russian or English words in the form of a square 7 by 7. Who will take the challenge?
In the beginning I will give this most difficult crossword puzzle:
The first thing to find is a list of words that are used in the construction of this crossword. Two files from the above articles were taken as such a list - one file with Russian words, one file with English. Then it was necessary to solve the main question - what algorithm to use to compile this crossword. Actually “difficult” this crossword does not the number of words, but the number of their intersections. It is clear that the brute-force attack is not suitable here, since the enumeration of all the options would take too much time. In the aforementioned article, many heuristics were considered to speed up the brute force process; however, this crossword was never written in Russian or in English. You can continue to come up with other heuristics to speed up the solution, but most of them have already been invented and implemented in the SAT solvers. Therefore, it is possible to translate the task into a form understandable by the SAT solvers and use one of them.
What is a SAT solver and what information it expects at the entrance I considered in the article “Solving the Tile Problem with the SAT Solver Using the Example of Pentamino” . In the case of generating a crossword puzzle, a slightly different approach is needed to formulate the problem in conjunctive-normal form, which I will now state.
The first thing to do is to sort all the words from the list into groups. Each group will contain words of the same length. Obviously, for each word in the crossword grid, you can select a word from the group with the corresponding length. Let's compare each word from the group which can be written in one word from the grid to a boolean variable. This variable will be true if the given word from the group will be written in this word from the grid and false otherwise.
Now we will make a formula describing our task, that is, we will actually impose restrictions on our variables. Find all vertical word crossings with words horizontally. For each intersection, we determine which pairs of words are combined with each other and which are not. However, a problem arises here, since the number of such pairs may exceed one million for one intersection. Therefore, we use a different approach. Sort the words in the group that corresponds to the word horizontally by the letter that stands in the position of the intersection of these two words. Do the same for the word vertically. Obviously, the appropriate words will have the same letter at the intersection. We introduce an additional variable for each letter that occurs at least in one word horizontally and vertically. Now the condition that the two words are combined with each other will be that at least one such variable will be true. Thus, for each intersection, one clause consisting of variables corresponding to letters will be added. Now it is necessary to associate variables corresponding to a specific letter with words containing this letter in the position of the intersection of words. This is done by a set of clauses that ensure that two boolean variables have the same values. And finally, it is necessary to ensure that there are no identical words in the crossword. To do this, for each word from the database we add clauses of the form (not x_i V not x_j), where x_i is the variable corresponding to its instance in one word from the crossword puzzle grid, and x_j is the variable corresponding to its instance in another word from the crossword puzzle grid.
Generating this “most difficult crossword puzzle” using Russian words takes a few minutes on an Intel 2600K 3.5 GHz with 16 gigabytes of memory. Creating a crossword puzzle using English words took about twenty minutes.
After that, I tried other crossword grids. For example, I managed to make a crossword of English and Russian words in the form of a square 6 by 6, where all the words intersect.
Next, I bring the resulting crossword puzzles. Those interested can solve them.
Variant with Russian words:
1 Horizontal Slow Motion with Nicked Plane
6 Horizontal Japanese stringed musical instrument
10 Horizontal In Scandinavian mythology, a giant that emerged from the pre-temporal chaos of the global abyss.
14 Horizontal Exile from the clan
15 Horizontal Mineral
16 Horizontal Czech Poet (20 in.)
17 Horizontal Island in the Gulf of Guinea (Equatorial Guinea Territory)
18 Horizontal Mouth, Lips (outdated)
19 Horizontal Resentment, Rage
20 Horizontal The presence of only one political party
23 Horizontal Ireland's largest river
24 Horizontal Cleric Clothes
25 Horizontal River in Angola and Zaire, left tributary of the Kwango River
27th Horizontal Mark of the Hungarian Bus
32 Horizontal City and Port in the DPRK
35 Horizontal Mother-in-law or mother-in-law
37 Horizontal Plant of the Solanaceae Family
38 Horizontal One who is engaged in carding wool
41 Horizontal Female name (Greek. Good, kind)
42 Horizontal Canadian Artificial Satellite
43 Horizontal Character of Weber's opera '' Free Shooter ''
44 Horizontal City in Slovakia
46 Horizontal Spending
48 Horizontal Fish bred carp family
50 Horizontal In Japanese mythology, the deity of plenty of rice ears
54 Horizontal Inorganic Crystalline Phosphor
59 Horizontal Iranian prophet, founder of Manichaeism (3 v.)
60 Horizontal Peasant Housing on the Islands of the West Indies
61 Horizontal Shepherd Dog Breed (similar to fox)
62 Horizontal (rel.) Stupid, stubborn, stupid
63 Horizontal City in the Orenburg region. on the Ural River
64 Horizontal In Greek mythology, the giant-hunter killed by Artemis.
65 Horizontal Chilean singer and poet
66 Horizontal Character of the Indian folk theater, the image of a ruined playboy, a parasite with a rich patron
67 Horizontal Chechens and Ingushes Mother Earth
1 Vertical Nickname of one of the leaders of the popular uprising in 1413 in Paris
2 Vertical Unsatisfied Sense
3 Vertical German paleontologist (1800-1862)
4 Vertical Conquest of the territories captured by the Moors by the indigenous population of the Iberian Peninsula
5 Vertical Russian guitar master
6 Vertical Swedish and Russian military leader, general, associate of Peter I (1667-1717)
7 Vertical Musician Playing a Musical Instrument
8 Vertical Speaker, eloquent man
9 Vertical Ridge in Japan, on the island of Honshu
10 Vertical Korean Percussion Musical Instrument, Octagonal Drum
11 Vertical Latvian Conductor (1917-1967)
12 Vertical Hospitality, Weasel
13 Vertical In Slavic mythology, the spirit, the embodiment of death
21 Vertical Animation genre originated in Japan
22 Vertical Warming up thread
26 Vertical Lake in the Arkhangelsk Region
28 Vertical River in Spain
29 Vertical Small forest of deciduous trees
30 Vertical Exceptional Item
31 Vertical Belgian wind instrument inventor saxophone
32 Vertical Small Tub
33 Vertical Representative of the Black Race
34 Vertical Old apothecary weight measure = 62.21 mg
36 Vertical Province in Saudi Arabia
39 Vertical Antifriction Grease
40 Vertical Sculptural decoration of capitals, cornices, etc. in the form of stylized stems and leaves of such a plant.
45 Vertical Russian writer, poet, screenwriter, author of film scripts by A. Sokurov (“Moloch”, ““ Taurus ”)
47 Vertical Polysulfide rubber, a type of synthetic rubber
49 Vertical English Pathologist (Nobel Prize 1945)
51 Vertical In Muslim mythology, a genie with special power
52 Vertical Goose Creek
53 Vertical female name (Greek: the name of the goddess of peaceful life; peace)
54 Vertical Chess Grandmaster
55 Vertical The historical group of mankind united by common origin
56 Vertical Hybrid from crossing a single-humped camel (dromedara) with a double-humped (Bactrian), drug
57 Vertical Mechanical quantity causing acceleration
58 Vertical Japanese writer (1909-1989, '' Notes of the prisoner '', '' Lights in the field '', '' Battle on Leyte '')
6 Horizontal Japanese stringed musical instrument
10 Horizontal In Scandinavian mythology, a giant that emerged from the pre-temporal chaos of the global abyss.
14 Horizontal Exile from the clan
15 Horizontal Mineral
16 Horizontal Czech Poet (20 in.)
17 Horizontal Island in the Gulf of Guinea (Equatorial Guinea Territory)
18 Horizontal Mouth, Lips (outdated)
19 Horizontal Resentment, Rage
20 Horizontal The presence of only one political party
23 Horizontal Ireland's largest river
24 Horizontal Cleric Clothes
25 Horizontal River in Angola and Zaire, left tributary of the Kwango River
27th Horizontal Mark of the Hungarian Bus
32 Horizontal City and Port in the DPRK
35 Horizontal Mother-in-law or mother-in-law
37 Horizontal Plant of the Solanaceae Family
38 Horizontal One who is engaged in carding wool
41 Horizontal Female name (Greek. Good, kind)
42 Horizontal Canadian Artificial Satellite
43 Horizontal Character of Weber's opera '' Free Shooter ''
44 Horizontal City in Slovakia
46 Horizontal Spending
48 Horizontal Fish bred carp family
50 Horizontal In Japanese mythology, the deity of plenty of rice ears
54 Horizontal Inorganic Crystalline Phosphor
59 Horizontal Iranian prophet, founder of Manichaeism (3 v.)
60 Horizontal Peasant Housing on the Islands of the West Indies
61 Horizontal Shepherd Dog Breed (similar to fox)
62 Horizontal (rel.) Stupid, stubborn, stupid
63 Horizontal City in the Orenburg region. on the Ural River
64 Horizontal In Greek mythology, the giant-hunter killed by Artemis.
65 Horizontal Chilean singer and poet
66 Horizontal Character of the Indian folk theater, the image of a ruined playboy, a parasite with a rich patron
67 Horizontal Chechens and Ingushes Mother Earth
1 Vertical Nickname of one of the leaders of the popular uprising in 1413 in Paris
2 Vertical Unsatisfied Sense
3 Vertical German paleontologist (1800-1862)
4 Vertical Conquest of the territories captured by the Moors by the indigenous population of the Iberian Peninsula
5 Vertical Russian guitar master
6 Vertical Swedish and Russian military leader, general, associate of Peter I (1667-1717)
7 Vertical Musician Playing a Musical Instrument
8 Vertical Speaker, eloquent man
9 Vertical Ridge in Japan, on the island of Honshu
10 Vertical Korean Percussion Musical Instrument, Octagonal Drum
11 Vertical Latvian Conductor (1917-1967)
12 Vertical Hospitality, Weasel
13 Vertical In Slavic mythology, the spirit, the embodiment of death
21 Vertical Animation genre originated in Japan
22 Vertical Warming up thread
26 Vertical Lake in the Arkhangelsk Region
28 Vertical River in Spain
29 Vertical Small forest of deciduous trees
30 Vertical Exceptional Item
31 Vertical Belgian wind instrument inventor saxophone
32 Vertical Small Tub
33 Vertical Representative of the Black Race
34 Vertical Old apothecary weight measure = 62.21 mg
36 Vertical Province in Saudi Arabia
39 Vertical Antifriction Grease
40 Vertical Sculptural decoration of capitals, cornices, etc. in the form of stylized stems and leaves of such a plant.
45 Vertical Russian writer, poet, screenwriter, author of film scripts by A. Sokurov (“Moloch”, ““ Taurus ”)
47 Vertical Polysulfide rubber, a type of synthetic rubber
49 Vertical English Pathologist (Nobel Prize 1945)
51 Vertical In Muslim mythology, a genie with special power
52 Vertical Goose Creek
53 Vertical female name (Greek: the name of the goddess of peaceful life; peace)
54 Vertical Chess Grandmaster
55 Vertical The historical group of mankind united by common origin
56 Vertical Hybrid from crossing a single-humped camel (dromedara) with a double-humped (Bactrian), drug
57 Vertical Mechanical quantity causing acceleration
58 Vertical Japanese writer (1909-1989, '' Notes of the prisoner '', '' Lights in the field '', '' Battle on Leyte '')
Option with English words:
1 Horizontal A place that attracts many visitors
6 Carangidae
10 Horizontal A collection of facts from which may may be drawn
14 Horizontal Nintu)
15 Horizontal Body covering of a living animal
16 Horizontal A dull persistent (usually moderately intense) pain
17 Horizontal A response of the body
18 Horizontal Type genus of the Anatidae freshwater ducks
19 Horizontal The dynasty that ruled much of Manchuria and northeastern China from 947 to 1125
20 Horizontal A white crystalline compound used
23 Horizontal A city in central Tanzania
24 Horizontal God of death
25 Horizontal Shaped and dried eggs
27 Horizontal A member of the Siouan people of Virginia and North Carolina
32 Horizontal A strong restless desire
35 Horizontal South African prelate and leader of the antiapartheid struggle (born in 1931)
37
38 Horizontal Biting midges
41 Horizontal Portugal
42 Horizontal An Eskimo hut
There is no resistance to any direction.
44 Horizontal The capital of Bahrain
46 tint to the hair
48 Horizontal Type genus of the Majidae
50 Horizontal Camassia
54 Horizontal Flying gurnards
59 Horizontal Entire crop can be harvested at one time
60 Horizontal A law passed to US law meeting
61 Horizontal Alabaster
62 Horizontal English statesman who opposes Henry VIII's divorce from Aragon and was imprisoned
63 Horizontal A man who courts a woman
64 Horizontal United States baseball player
65 Horizontal A secret look
66 Horizontal Small slender gull
67 Horizontal Known for oil and olives
1 Vertical French Revolutionary Leader (Charityte Corday (1743-1793))
2 Vertical Annual to perennial herbs of the Mediterranean region
3 Vertical Tropical southeast Asian shrubby vine bearing spicy berrylike fruits
4 Vertical Ani
5 Vertical The first light of day
6 Vertical Title for the former hereditary monarch of Iran
7 Vertical A photographer who operates a movie camera
8 Vertical A Seyhan River
9 Vertical An arid region with little or no vegetation
10 Vertical Surrealist Spanish painter (1904-1989)
11 Vertical Any Bottles of Water
12 Vertical A native or inhabitant of Thailand
13 Vertical (in Gnosticism)
21 Vertical An active by volcano in southeastern Colombia in the Andes
22 Vertical A lepton of very great mass
26 South American Indian people living in Brazil and Paraguay
28 Vertical Them for the muscles of mastication
29 Vertical A miniature whirlpool or whirlwind resulting in double fluid back on itself
30 Vertical British artist and writer of nonsense verse (1812-1888)
31 Vertical Chocolate Cookies with white cream filling
32 Vertical A ballistic missile
33 Vertical A three-tone Chadic language
34 Vertical A capacity unit used for measuring fresh herring
36 Vertical Large sweet juicy hybrid between tangerine and grapefruit having a thick wrinkled skin
39 Vertical Plain-woven (often glazed) used especially for linings and garments
40 Vertical A unit of apothecary weight equal to 480 grains or one twelfth of a pound
45 Vertical A Town in central Belgium
47 Vertical A long brightly colored shawl
49 Vertical A book in the Old Testament describing how Joshua led the Israelites into Canaan after the death of Moses
51 Vertical A nonsteroidal anti-inflammatory medicine (trade names Advil and Motrin and Nuprin) used for anti-inflammatory and antipyretic
52 Vertical Goat-like antelope of proboscis
53 Vertical United States tennis player (born in Yugoslavia in 1973)
54 Vertical A slight wetness
55 Vertical Succulent plants having rosettes of leaves
56 Vertical Activity involved in maintaining working order
57 Vertical (South African) a group of settlers (especially by organized migration)
58 Vertical A mountain lake (especially one formed by glaciers)
6 Carangidae
10 Horizontal A collection of facts from which may may be drawn
14 Horizontal Nintu)
15 Horizontal Body covering of a living animal
16 Horizontal A dull persistent (usually moderately intense) pain
17 Horizontal A response of the body
18 Horizontal Type genus of the Anatidae freshwater ducks
19 Horizontal The dynasty that ruled much of Manchuria and northeastern China from 947 to 1125
20 Horizontal A white crystalline compound used
23 Horizontal A city in central Tanzania
24 Horizontal God of death
25 Horizontal Shaped and dried eggs
27 Horizontal A member of the Siouan people of Virginia and North Carolina
32 Horizontal A strong restless desire
35 Horizontal South African prelate and leader of the antiapartheid struggle (born in 1931)
37
38 Horizontal Biting midges
41 Horizontal Portugal
42 Horizontal An Eskimo hut
There is no resistance to any direction.
44 Horizontal The capital of Bahrain
46 tint to the hair
48 Horizontal Type genus of the Majidae
50 Horizontal Camassia
54 Horizontal Flying gurnards
59 Horizontal Entire crop can be harvested at one time
60 Horizontal A law passed to US law meeting
61 Horizontal Alabaster
62 Horizontal English statesman who opposes Henry VIII's divorce from Aragon and was imprisoned
63 Horizontal A man who courts a woman
64 Horizontal United States baseball player
65 Horizontal A secret look
66 Horizontal Small slender gull
67 Horizontal Known for oil and olives
1 Vertical French Revolutionary Leader (Charityte Corday (1743-1793))
2 Vertical Annual to perennial herbs of the Mediterranean region
3 Vertical Tropical southeast Asian shrubby vine bearing spicy berrylike fruits
4 Vertical Ani
5 Vertical The first light of day
6 Vertical Title for the former hereditary monarch of Iran
7 Vertical A photographer who operates a movie camera
8 Vertical A Seyhan River
9 Vertical An arid region with little or no vegetation
10 Vertical Surrealist Spanish painter (1904-1989)
11 Vertical Any Bottles of Water
12 Vertical A native or inhabitant of Thailand
13 Vertical (in Gnosticism)
21 Vertical An active by volcano in southeastern Colombia in the Andes
22 Vertical A lepton of very great mass
26 South American Indian people living in Brazil and Paraguay
28 Vertical Them for the muscles of mastication
29 Vertical A miniature whirlpool or whirlwind resulting in double fluid back on itself
30 Vertical British artist and writer of nonsense verse (1812-1888)
31 Vertical Chocolate Cookies with white cream filling
32 Vertical A ballistic missile
33 Vertical A three-tone Chadic language
34 Vertical A capacity unit used for measuring fresh herring
36 Vertical Large sweet juicy hybrid between tangerine and grapefruit having a thick wrinkled skin
39 Vertical Plain-woven (often glazed) used especially for linings and garments
40 Vertical A unit of apothecary weight equal to 480 grains or one twelfth of a pound
45 Vertical A Town in central Belgium
47 Vertical A long brightly colored shawl
49 Vertical A book in the Old Testament describing how Joshua led the Israelites into Canaan after the death of Moses
51 Vertical A nonsteroidal anti-inflammatory medicine (trade names Advil and Motrin and Nuprin) used for anti-inflammatory and antipyretic
52 Vertical Goat-like antelope of proboscis
53 Vertical United States tennis player (born in Yugoslavia in 1973)
54 Vertical A slight wetness
55 Vertical Succulent plants having rosettes of leaves
56 Vertical Activity involved in maintaining working order
57 Vertical (South African) a group of settlers (especially by organized migration)
58 Vertical A mountain lake (especially one formed by glaciers)
Crossword 6 for 6 in Russian:
1 Horizontal Soviet test pilot, Hero of the Soviet Union, one of the participants of the non-stop flight Moscow - North Pole - Vancouver
2 Horizontal Ear
3 Horizontal Soothsayer
4 Horizontal City in Italy, on the island of Sicily
5 Horizontal Twisted, textured yarn obtained by shirring in heated chambers.
6 Horizontal French film director, screenwriter ('' Bad blood '', '' A guy meets a girl '')
7 Vertical Silver coin of the Grand Duchy of Lithuania 16th c.
8 Vertical American biochemist, first synthesized tRNA gene (Nobel Prize 1968)
9 Vertical City in the Russian Federation, North Ossetia, on the Ardon River, on the Military Ossetian Road
10 Vertical Horizontal niche in the wall of the burial chamber, where the deceased was laid and bricked up or curtained with a canopy
11 Vertical Femoral Mascara
12 Vertical City in southeastern France
2 Horizontal Ear
3 Horizontal Soothsayer
4 Horizontal City in Italy, on the island of Sicily
5 Horizontal Twisted, textured yarn obtained by shirring in heated chambers.
6 Horizontal French film director, screenwriter ('' Bad blood '', '' A guy meets a girl '')
7 Vertical Silver coin of the Grand Duchy of Lithuania 16th c.
8 Vertical American biochemist, first synthesized tRNA gene (Nobel Prize 1968)
9 Vertical City in the Russian Federation, North Ossetia, on the Ardon River, on the Military Ossetian Road
10 Vertical Horizontal niche in the wall of the burial chamber, where the deceased was laid and bricked up or curtained with a canopy
11 Vertical Femoral Mascara
12 Vertical City in southeastern France
Crossword 6 to 6 in English:
1 Calvary California and southern Oregon
2 Prehistoric Greeks
3 Horizontal Can become addictive
4 Horizontal Greek god of light
5 Horizontal Small personal or clothing or sewing items
6 Horizontal Valuable timber tree of New Zealand yielding hard wood wood bridges and wharves
7 Vertical A straight line
8 Vertical Any Downed Curving Bill
9 Vertical American novelist noted for children's books (1832-1888)
10 Vertical North American bluebirds
11 Vertical A person
12 Vertical Type genus of the Annonaceae
2 Prehistoric Greeks
3 Horizontal Can become addictive
4 Horizontal Greek god of light
5 Horizontal Small personal or clothing or sewing items
6 Horizontal Valuable timber tree of New Zealand yielding hard wood wood bridges and wharves
7 Vertical A straight line
8 Vertical Any Downed Curving Bill
9 Vertical American novelist noted for children's books (1832-1888)
10 Vertical North American bluebirds
11 Vertical A person
12 Vertical Type genus of the Annonaceae
Conclusion
The use of SAT Solver raises the complexity of crossword puzzles that can be generated. As in the previous article, I want to set the next unconquered peak - to make a crossword puzzle of Russian or English words in the form of a square 7 by 7. Who will take the challenge?
All Articles