Home Logic Games Generating crossword puzzles using SAT solver

Generating crossword puzzles using SAT solver

by admin

There were several articles on Habra about crossword puzzle generation. In one of them. "The most difficult crossword puzzle generated by a computer." talked about a very difficult crossword puzzle made by a computer that "had to have a little help" by hand. In the second article. "An algorithm for forming crossword puzzles." talks about the algorithm the author created for crossword puzzles and notes that this "most difficult crossword puzzle" has remained unconquered and says that "maybe this unconquered peak will inspire someone to take a new assault!" Well, you can take up the challenge. What came out of it, see below the cat.
I begin with this most difficult crossword puzzle:
Generating crossword puzzles using SAT solver
The first thing to find – a list of words that are used in this crossword puzzle. As such a list were taken from two files from the above articles – one file with Russian words, one file with English words. Then it was necessary to decide the main question – which algorithm to use for this crossword puzzle. Actually "complex" this crossword puzzle is not the number of words, but the number of intersections. Clearly, the search "brute-force attack" is not suitable here, because trying all the options would take too much time. In the above-mentioned article many heuristics were considered to speed up the search process, however, this crossword puzzle was never completed neither in the Russian nor in the English version. You can keep coming up with other heuristics to speed up the solution, but most of them are already invented and implemented in SAT solvers. So, you can translate the problem into a form that SAT solvers can understand and use one of them.
What is a SAT solver and what kind of information it expects in the input I discussed in "Solving the paving problem with a SAT solver using the pentamino example" In the case of crossword puzzle generation, a slightly different approach is needed to formulate the problem in conjunctive-normal form, which I will now outline.
The first thing to do is to sort all the words from the list into groups. Each group will contain words of equal length. Obviously, for each word in the crossword grid you can choose some word from the group with the appropriate length. Let’s compare each word from the group, which can be written in a word from the grid 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 let’s make a formula describing our problem, that is, let’s actually impose constraints on our variables. Find all intersections of words vertically with words horizontally. For each intersection, determine which pairs of words combine with each other and which do not. However, there is a problem here, because the number of such pairs can exceed a million for a single intersection. Therefore, we will use another approach. Sort the words in the group that matches the word horizontally by the letter that stands at the intersection position of the two words. Let’s do the same for the word vertically. Obviously, matching words will have the same letter at the intersection. Introduce an additional variable for each letter that occurs in at least one word horizontally and vertically. Now the condition for two words to match each other will be that at least one such variable is true. Thus, for each intersection will be added one clause consisting of variables corresponding to the letters. It is now necessary to link variables corresponding to a particular letter with words containing this letter in the position of the intersection of words. This is done by a set of closes, which guarantees that two boolean variables have the same values. Finally, you need to ensure that there are no identical words in the crossword puzzle. To do this, for each word from the database add closes of the form (not x_i V not x_j), where x_i – the variable corresponding to its instance in a word from the crossword grid, and x_j – the variable corresponding to its instance in another word from the crossword grid.
Generating this "most complex crossword puzzle" using Russian words takes a few minutes on an Intel 2600K 3.5Ghz with 16GB of memory. Creating a crossword puzzle with English words took about twenty minutes.
After that, I tried other crossword puzzle grids. For example, I managed to make a crossword puzzle of English and Russian words in the form of a square 6 by 6, where all the words intersect.
Below I give the resulting crosswords. Those who want can solve them.
Variant with Russian words : 1 Horizontal Slow motion of an airplane with a bow up
6 Horizontal Japanese stringed plucked musical instrument
10 Horizontal In Norse mythology, a giant who emerged from the pre-modern chaos of the abyss
14 Horizontal Exile
15 Horizontal Mineral
16 Horizontal Czech poet (20th century)
17 Horizontal Island in the Gulf of Guinea (territory of Equatorial Guinea)
18 Horizontal Mouth, lips (obsolete)
19 Horizontal Indignation, rage
20 Horizontal Presence of only one political party
23 Horizontal Largest River in Ireland
24 Horizontal Clergyman’s Clothes
25 Horizontal River in Angola and Zaire, left tributary of the Kwango River
27 Horizontal Hungarian bus brand
32 Horizontal City and port in North Korea
35 Horizontal Mother-in-law or mother-in-law
37 Horizontal Plant of the nightshade family
38 Horizontal One who scratches wool
41 Horizontal A feminine name (Greek for good, kind)
42 Horizontal Canadian artificial satellite
43 Horizontal Character from Weber’s opera "The Free Arrow".
44 Horizontal A town in Slovakia
46 Horizontal Expenditure
48 Horizontal Farmed fish of the carp family
50 Horizontal In Japanese mythology, the deity of the abundance of rice ears.
54 Horizontal Inorganic crystalline phosphor
59 Horizontal Iranian prophet, founder of Manichaeism (3rd century).
60 Horizontal Peasant dwelling in the West Indies
61 Horizontal Shepherd dog (fox-like)
62 Horizontal Stubborn and stupid
63 Horizontal City in the Orenburg Region, on the river Ural
64 Horizontal In Greek mythology a giant hunter killed by Artemis
65 Horizontal Chilean singer and poet
66 Horizontal Indian folk theater character, depicted as a ruined waster of life, a freeloader with a rich patron
67 Horizontal Chechen and Ingush mother earth
1 Vertical The nickname of one of the leaders of the 1413 Paris uprising
2 Vertical An unsatisfied feeling
3 Vertical German paleontologist (1800-1862)
4 Vertical Recapture by the natives of the Iberian Peninsula of the territories captured by the Moors
5 Vertical Russian guitar master
6 Vertical Swedish and Russian military commander, general, associate of Peter the Great (1667-1717)
7 Vertical Musician who plays a musical instrument
8 Vertical Orator, an eloquent person
9 Vertical Ridge in Japan, on Honshu Island
10 Vertical Korean percussion musical instrument, an octagonal drum
11 Vertical Latvian conductor (1917-1967)
12 Vertical Warmth, affection
13 Vertical In Slavic mythology a spirit, the embodiment of death
21 Vertical A genre of animation that originated in Japan
22 Vertical Heating thread of a kotoda lamp
26 Vertical Lake in the Arkhangelsk Region
28 Vertical River in Spain
29 Vertical A small forest of deciduous trees
30 Vertical Rarest object
31 Vertical Belgian woodwind master, inventor of the saxophone
32 Vertical Small tub
33 Vertical A member of the black race
34 Vertical Old measure of apothecary weight = 62.21 mg
36 Vertical A province in Saudi Arabia
39 Vertical Anti-Friction Grease
40 Vertical Sculptural ornamentation of capitals, cornices, etc. in the form of stylized stems and leaves of such a plant
45 Vertical Russian writer, poet, screenwriter, author of scripts for films 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 powers
52 Vertical Goose scream
53 Vertical A feminine name (Greek name for the goddess of peaceful life; peace)
54 Vertical Grandmaster of Chess
55 Vertical A historically formed group of mankind united by a common origin
56 Vertical A crossbreed between a one-humped camel (dromedary) and a two-humped camel (bactrian), Nar
57 Vertical Mechanical quantity causing acceleration
58 Vertical Japanese writer (1909-1989, ”Notes of a Prisoner, ” ”Lights in the Field, ” ”The Battle of Leyte”)
Variant with English words : 1 Horizontal A place that attracts many visitors
6 Horizontal Any of a number of fishes of the family Carangidae
10 Horizontal A collection of facts from which conclusions 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 body tissues to injury or irritation
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 as an analgesic and also as an antipyretic
23 Horizontal A city in central Tanzania
24 Horizontal God of death
25 Horizontal Shaped and dried dough made from flour and water and sometimes egg
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 Horizontal A commercial document used to request someone to supply something in return for payment
38 Horizontal Biting midges
41 Horizontal An ancient city in northern Portugal
42 Horizontal An Eskimo hut
43 Horizontal Rotating mechanism in the form of a universally mounted spinning wheel that offers resistance to turns in any direction
44 Horizontal The capital of Bahrain
46 Horizontal The act of giving a light tint to the hair
48 Horizontal Type genus of the Majidae
50 Horizontal Any of several plants of the genus Camassia
54 Horizontal Flying gurnards
59 Horizontal Entire crop can be harvested at one time
60 Horizontal A law passed by US Congress to prevent employees from being injured or contracting diseases in the course of their employment
61 Horizontal A heavy block of iron or steel on which hot metals are shaped by hammering
62 Horizontal English statesman who opposed Henry VIII’s divorce from Catherine of Aragon and was imprisoned and beheaded
63 Horizontal A man who courts a woman
64 Horizontal United States baseball player
65 Horizontal A secret look
66 Horizontal Small slender gull having narrow wings and a forked tail
67 Horizontal Known for grapes and olives and olive oil
1 Vertical French revolutionary leader (born in Switzerland) who was a leader in overthrowing the Girondists and was stabbed to death in his bath by Charlotte 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 city in southern Turkey on the Seyhan River
9 Vertical An arid region with little or no vegetation
10 Vertical Surrealist Spanish painter (1904-1989)
11 Vertical Any of various water-soluble compounds having a sour taste and capable of turning litmus red and reacting with a base to form a salt
12 Vertical A native or inhabitant of Thailand
13 Vertical (in Gnosticism) a divine power or nature emanating from the Supreme Being and playing various roles in the operation of the universe
21 Vertical An active volcano in southeastern Colombia in the Andes
22 Vertical A lepton of very great mass
26 Vertical A member of the South American Indian people living in Brazil and Paraguay
28 Vertical The main sensory nerve of the face and motor nerve for the muscles of mastication
29 Vertical A miniature whirlpool or whirlwind resulting when the current of a fluid doubles back on itself
30 Vertical British artist and writer of nonsense verse (1812-1888)
31 Vertical Chocolate cookie with white cream filling
32 Vertical A ballistic missile that is capable of traveling from one continent to another
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) fabric of wool or wool and cotton used especially formerly for linings and garments and curtains
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 (the Promised Land) after the death of Moses
51 Vertical A nonsteroidal anti-inflammatory medicine (trade names Advil and Motrin and Nuprin) used to relieve the pain of arthritis and as an analgesic and antipyretic
52 Vertical Goat-like antelope of central Eurasia having a stubby nose like a 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 usually with fiber like hemp and spikes of showy flowers
56 Vertical Activity involved in maintaining something in good working order
57 Vertical (South African) a journey by ox wagon (especially an organized migration by a group of settlers)
58 Vertical A mountain lake (especially one formed by glaciers)
Crossword puzzle 6 by 6 in Russian : 1 Horizontal Soviet test pilot, Hero of the Soviet Union, one of the participants of Moscow-North Pole-Vancouver non-stop flight
2 Horizontal Ear
3 Horizontal Soothsayer
4 Horizontal City in Italy, on the island of Sicily
5 Horizontal Twisted textured filament obtained by corrugation in heated chambers.
6 Horizontal French film director and screenwriter ("Bad Blood, " "Boy Meets Girl")
7 Vertical Silver Coin of the Grand Duchy of Lithuania, 16th century.
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 A horizontal niche in the wall of a burial chamber, where the dead were laid and walled up or covered with a canopy
11 Vertical The thigh part of the carcass
12 Vertical A city in southeastern France
6 by 6 crossword puzzle in English : 1 Horizontal A member of the Indian people of northern California and southern Oregon
2 Horizontal A member of one of the four divisions of the 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 reddish wood used for furniture and bridges and wharves
7 Vertical A straight line that intersects a curve at two or more points
8 Vertical Any of several crested Old World birds with a slender down-curving bill
9 Vertical American novelist noted for children’s books (1832-1888)
10 Vertical North American bluebirds
11 Vertical A person whose occupation is making and altering garments
12 Vertical Type genus of the Annonaceae

Conclusion

Using SAT solver raises the frame of complexity of crossword puzzles that can be generated. As in the last article, I want to set the next unconquered peak – make a crossword puzzle of Russian or English words in the form of a square 7 by 7. Who will accept the challenge?

You may also like