<file_sep># Crossword-Solver
<p align="center">
<img src="https://github.com/pncnmnp/Crossword-Solver/blob/master/screenshots/newspaper.jpg">
</p>

This solver guesses the probable solutions based on the clues provided and uses a SMT solver to predict the result

## How does it work ?
[I have written a blogpost explaining the working of this crossword-solver.](https://pncnmnp.github.io/blogs/crossword-1.html)

## Structure
The project has 4 main files:
*  `words.py`: Uses Moby's thesaurus, gensim's glove-wiki-gigaword-100 and nltk's Wordnet to guess the solutions
* `words_offline.py`: Uses all-clues.bz2 to guess the solutions
* `solve.py`: Solves the crossword based on the solution stored in `clues.json` using a SMT solver (Z3)
* `schema.py`: This is where a user needs to enter the layout of the crossword

## How to run
To run `words_offline.py`, I highly recommend using [pypy](https://pypy.org/). 
There is a considerable difference in performance between PyPy and native python's implementation (`./corpus/all-clues.bz2` is a large file when uncompressed).
I have observed certain libraries like `nltk` work flawlessly with PyPy whereas `z3` has some issues.
Native python (default) works reasonably well with `words.py` and `solve.py`.

**Important**: Decompress the `./corpus/all-clues.bz2` file before running `words_offline.py`

## Working
**Here is the format entered in `schema.py`**

<pre>
CROSSWORD_GRID = {
	"__ of bad news": {"start":(0, 1), "direction":"D", "length": 6},
	"Posture problem": {"start":(0, 3), "direction":"D", "length": 5},
	"Loads": {"start":(0, 4), "direction":"D", "length": 6},
	"Laundry appliance": {"start":(0, 5), "direction":"D", "length": 5},
	"Lectured": {"start":(1, 0), "direction":"D", "length": 5},
	"One who weeps": {"start":(1, 2), "direction":"D", "length": 5},
	"Grassy clump": {"start":(0, 3), "direction":"A", "length": 3},
	"Pie chart portion": {"start":(1, 0), "direction":"A", "length": 6},
	"\"Scary Movie,\" e.g.": {"start":(2, 0), "direction":"A", "length": 6},
	"Maryland's state bird": {"start":(3, 0), "direction":"A", "length": 6},
	"Something worth saving": {"start":(4, 0), "direction":"A", "length": 6},
	"\"To __ is human\"": {"start":(5, 0), "direction":"A", "length": 3}
}
</pre>

**Output (using `words_offline.py`)**

![Crossword Output](https://github.com/pncnmnp/Crossword-Solver/blob/master/screenshots/output-crossword.png)

### I am getting error running `solve.py`
If the error being faced is: `z3.z3types.Z3Exception: model is not available`, it is because a solution with the clues in `clues.json` does not exist!

This is usually seen when trying fetching solutions for clues from `words.py`. I recommend running with `words_offline.py` in such cases.

## Attribution
* For corpus attribution, see [`./corpus/README`](https://github.com/pncnmnp/Crossword-Solver/blob/master/corpus/README.txt)
* [Wikipedia's MediaWiki API](https://www.mediawiki.org/wiki/API:Main_page): [Donate to Wikipedia](https://wikimediafoundation.org/support/)
* https://nlp.stanford.edu/projects/glove/
* The crossword image is by <a href="https://pixabay.com/users/stevepb-282134/?utm_source=link-attribution&amp;utm_medium=referral&amp;utm_campaign=image&amp;utm_content=412452"><NAME></a> from <a href="https://pixabay.com/?utm_source=link-attribution&amp;utm_medium=referral&amp;utm_campaign=image&amp;utm_content=412452">Pixabay</a>
<file_sep># Pattern is (initial_X, initial_Y), direction(D or A), length
# THE WORDS INSERTED SHOULD HAVE THEIR STARTING LETTER CAPITALIZED (For clue names)
# "": {"start":(), "direction":"", "length": },
CROSSWORD_GRID = {
	"__ of bad news": {"start":(0, 1), "direction":"D", "length": 6},
	"Posture problem": {"start":(0, 3), "direction":"D", "length": 5},
	"Loads": {"start":(0, 4), "direction":"D", "length": 6},
	"Laundry appliance": {"start":(0, 5), "direction":"D", "length": 5},
	"Lectured": {"start":(1, 0), "direction":"D", "length": 5},
	"One who weeps": {"start":(1, 2), "direction":"D", "length": 5},
	"Grassy clump": {"start":(0, 3), "direction":"A", "length": 3},
	"Pie chart portion": {"start":(1, 0), "direction":"A", "length": 6},
	"\"Scary Movie,\" e.g.": {"start":(2, 0), "direction":"A", "length": 6},
	"Maryland's state bird": {"start":(3, 0), "direction":"A", "length": 6},
	"Something worth saving": {"start":(4, 0), "direction":"A", "length": 6},
	"\"To __ is human\"": {"start":(5, 0), "direction":"A", "length": 3}
}
<file_sep>MOBY_PATH = "./corpus/moby_words.txt"
ALL_WORD_VECTOR_PATH = "./corpus/all_word_vectors.pickle"
CLUES_PATH = "./clues.json"
ALL_CLUES = "./corpus/all-clues"<file_sep>from nltk.corpus import wordnet as wn
from nltk.tokenize import word_tokenize
from nltk.corpus import stopwords
from ast import literal_eval
import gensim.downloader as api
from file_path import *
from schema import CROSSWORD_GRID
import pickle
import string
import requests
import inflect # Library used to check whether a sentence is singular or plural
import json

"""
TODO: >> Plural detection and conversion [done]
      >> Variable cutoff value
"""

class Words():
	def __init__(self):
		self.word_vectors = self.retrieve_all_word_vectors()
		if self.word_vectors == None:
			self.store_all_word_vectors()
			self.word_vectors = self.retrieve_all_word_vectors()

	def fetch_all_word_vectors(self):
		return api.load("glove-wiki-gigaword-100")

	def store_all_word_vectors(self):
		all_word_vectors = self.fetch_all_word_vectors()
		with open(ALL_WORD_VECTOR_PATH, "wb") as fp:
			pickle.dump(all_word_vectors, fp)

	def retrieve_all_word_vectors(self):
		try:
			with open(ALL_WORD_VECTOR_PATH, "rb") as fp:
				all_word_vectors = pickle.load(fp)
			return all_word_vectors
		except:
			return None		

	def wikipedia_solution(self, wikipedia_clues, clues):
		WIKIPEDIA_API = "https://en.wikipedia.org/w/api.php?action=query&utf8=&format=json&list=search&srlimit=50&srsearch="
		stop = stopwords.words('english') + list(string.punctuation)
		clue_mapping = dict()

		print(">>> STARTING WIKI FETCH.....")
		for sentence in wikipedia_clues:
			req = requests.get(WIKIPEDIA_API + sentence)
			wiki_json = literal_eval(req.text)

			# The following code finds all titles from the JSON response,
			# The title is stripped of stop_words and punctuations
			# The title is split by space
			# Duplicates are removed and words are converted to a 1-D list
			solutions = list(set([word for word in [[word for word in word_tokenize(info["title"].lower()) if word not in stop] for info in wiki_json["query"]["search"]] for word in word]))

			for soln in solutions:
				if len(soln) != clues[sentence]:
					continue
				try:
					clue_mapping[sentence] += [soln]
				except:
					clue_mapping[sentence] = [soln]

		return clue_mapping

	def reduce_search_bound(self, all_words_wordnet, sentence_clues, clues):
		"""Reduces the search space by finding most similar words from self.word_vectors
		   using the method 'most_similar'.
		   Common words found between self.word_vectors.most_similar() and all_words_wordnet
		   are returned.
		   Param: all_words_wordnet : has to be wn.words()
		                              where wn is wordnet from nltk.corpus
		"""
		words = list(all_words_wordnet)
		possible_words = list()
		stop = stopwords.words('english') + list(string.punctuation)
		topn = 4000

		for sentence in sentence_clues:
			pos = [word for word in word_tokenize(sentence.lower()) if word not in stop]
			try:
				search_words = [word[0] for word in self.word_vectors.most_similar(positive=pos, topn=topn) if len(word[0])==clues[sentence]]
			except:
				pass
			possible_words += list(set(words).intersection(set(search_words)))

		return sorted(list(set(possible_words)))

	def sentence_solution(self, sentence_clues, clues):
		all_words_wordnet = self.reduce_search_bound(wn.words(), sentence_clues, clues)

		word_vectors = self.word_vectors

		stop = stopwords.words('english') + list(string.punctuation)
		clues_tokenized = dict()
		clue_mapping = dict()
		
		clue_plural = dict()
		infl = inflect.engine()

		# Tokenize all the clues, removing stopwords and punctuations
		for clue in sentence_clues:
			tokenized = [word for word in word_tokenize(clue.lower()) if word not in stop]
			clues_tokenized[clue] = tokenized

			# check if the clue is singular or plural
			if infl.singular_noun(clue) == False:
				clue_plural[clue] = "singular"
			else:
				clue_plural[clue] = "plural"

		print(">>> STARTING SENTENCE LOCAL FETCH.....")
		for word_wordnet in all_words_wordnet:
			iter_val = len(wn.synsets(word_wordnet))

			for syn_no in range(iter_val):
				synset_tokenized = [word for word in word_tokenize(wn.synsets(word_wordnet)[syn_no].definition().lower()) if word not in stop]

				for clue in sentence_clues:
					# To prevent any modifications on original variable
					# Can be caused if the clue is in plural form, and word_wordnet gets converted to plural form
					# This happens if length of the plural form of word matches with clue's required length
					# Example: "<NAME>" (PLURAL) (length - 7) -> filly -> fillies
					temp_word_wordnet = word_wordnet

					if len(temp_word_wordnet) != clues[clue]:
						# Check if the plural form of the word is of same length as required by the crossword
						if clue_plural[clue] == "plural" and len(infl.plural(temp_word_wordnet)) == clues[clue]:
							temp_word_wordnet = infl.plural(temp_word_wordnet)
						else:
							continue

					try:
						similarity = word_vectors.n_similarity(clues_tokenized[clue], synset_tokenized)
					except KeyError as e:
						try:
							# This error is caused by word_vectors.n_similarity()
							# The keyerror is printed as "word 'XXX' not in vocabulary"
							# We are giving the prediction another chance by removing the KeyError word
							try_removing_a_word = e.args[0].replace("word ", "").replace("not in vocabulary", "").replace("'", "").strip()
							synset_tokenized.remove(try_removing_a_word)
							similarity = word_vectors.n_similarity(clues_tokenized[clue], synset_tokenized)
						except:
							continue
					except:
						continue

					if similarity > 0.65:
						try:
							clue_mapping[clue] += [(temp_word_wordnet, similarity)]
						except:
							clue_mapping[clue] = [(temp_word_wordnet, similarity)]
						clue_mapping[clue] = sorted(set(clue_mapping[clue]), key=lambda x: x[1], reverse=True)

		return clue_mapping

	def one_word_solution(self, one_word_clues, clues):
		fp = open(MOBY_PATH)
		moby_lines = fp.readlines()
		clue_mapping = dict()

		# Copy the contents of the 'clues' dict in a temp variable
		# To prevent any modification changes appearing globally
		temp_clues = dict()
		for word in list(clues.keys()):
			temp_clues[word] = clues[word]

		print(">>> STARTING ONE-WORD LOCAL FETCH (V.1).....")
		# splits and re-indexes clues such as 'extra-large' as 'large'
		# this is done to maintain consistency with 'one_word_clues'
		for word in list(temp_clues.keys()):
			temp_clues[word.replace("-", " ").split()[-1].lower()] = temp_clues.pop(word)

		for line in moby_lines:
			guess_words = line.replace("\n", "").split(",")

			# removing spaces between the same word: at first -> atfirst
			guess_words = list(map(lambda word: word.replace(" ", ""), guess_words))
			common = list(set(guess_words).intersection(set(one_word_clues)))

			if len(common) == 0:
				continue
			else:
				for word in common:
					guess_words = [guess for guess in guess_words if len(guess)==temp_clues[word]]
					try:
						clue_mapping[word] += guess_words
					except:
						clue_mapping[word] = guess_words

					clue_mapping[word] = sorted(list(set(clue_mapping[word])))

		return clue_mapping

	def one_word_solution_alternate(self, one_word_clues, clues):
		clue_mapping = dict()
		stop = stopwords.words('english') + list(string.punctuation)

		# For common words, optimal is around 100, for proper nouns optimal is 1000-2000
		topn = 100

		# Copy the contents of the 'clues' dict in a temp variable
		# To prevent any modification changes appearing globally
		temp_clues = dict()
		for word in list(clues.keys()):
			temp_clues[word] = clues[word]

		print(">>> STARTING ONE-WORD LOCAL FETCH (V.2).....")
		# splits and re-indexes clues such as 'extra-large' as 'large'
		# this is done to maintain consistency with 'one_word_clues'
		for word in list(temp_clues.keys()):
			temp_clues[word.replace("-", " ").split()[-1].lower()] = temp_clues.pop(word)

		for clue in one_word_clues:
			pos = [word for word in word_tokenize(clue.lower()) if word not in stop]
			try:
				clue_mapping[clue] = [word[0] for word in self.word_vectors.most_similar(positive=pos, topn=topn) if len(word[0]) == temp_clues[clue]]
			except:
				pass

		return clue_mapping

	def store_words(self, one_word_solved, one_word_clues, sentence_solved, wikipedia_solved):
		clues = dict()

		for key in list(one_word_solved.keys()):
			actual_key = [val[1] for val in one_word_clues if val[0]==key][0]
			try:
				clues[actual_key] += one_word_solved[key]
			except:
				clues[actual_key] = list()
				clues[actual_key] += one_word_solved[key]

		for key in list(sentence_solved.keys()):
			try:
				clues[key] += [word[0] for word in sentence_solved[key]]
			except:
				clues[key] = list()
				clues[key] += [word[0] for word in sentence_solved[key]]

		for key in list(wikipedia_solved.keys()):
			try:
				clues[key] += wikipedia_solved[key]
			except:
				clues[key] = list()
				clues[key] += wikipedia_solved[key]

		print(">>> STORED CLUES.....")
		with open(CLUES_PATH, "w") as fp:
			json.dump(str(clues), fp)

	def fetch_words(self, clues):
		"""	1. The tense of the clues have to be guessed
		    2. We segregate the "one word" clues with "sentence" clues
		    3. Possible solutions of the "one word" clues (in the tenses required)
		       are searched in Moby's Thesaurus
		    4. "Sentence" clues are searched in Wordnet (NLTK's version)
		    5. If a "sentence" clue has less confidence level than expected,
		       Wikipedia's MediaWiki API is used.
		    6. All the possible solutions are searched with the criteria:
		           Word length is same as required ||in the correct tense||

		    Param: clues - dict
		           {clue_1: word_len_1, clue_2: word_len_2}
		"""
		all_clues = list(clues.keys())
		one_word_clues = [(clue.lower(),clue) for clue in all_clues if len(clue.split(" ")) == 1]

		# converting words such as extra-large into large
		one_word_clues += [(clue.split("-")[-1].lower(),clue) for clue in all_clues 
								if ("-" in clue) and (len(clue.split("-"))) == 2]
		one_word_solved = self.one_word_solution_alternate([clue[0] for clue in one_word_clues], clues)

		sentence_clues = list(set(all_clues).difference(set(one_word_clues)))
		sentence_solved = self.sentence_solution(sentence_clues, clues)

		wikipedia_clues = list()
		# Print top N results
		N = 40
		for clue in sentence_solved:
			sentence_solved[clue] = sentence_solved[clue][:N]

		wikipedia_solved = self.wikipedia_solution(sentence_clues, clues)

		self.store_words(one_word_solved, one_word_clues, sentence_solved, wikipedia_solved)

if __name__ == '__main__':
	grid = CROSSWORD_GRID
	clues = dict()
	for clue in CROSSWORD_GRID:
		clues[clue] = CROSSWORD_GRID[clue]["length"]

	Words().fetch_words(clues)
<file_sep>from nltk.corpus import stopwords
from collections import Counter
from schema import CROSSWORD_GRID
from file_path import *
import string
import math
import re
import json

class Words_Offline():
	def __init__(self):
		pass

	def all_solution(self, clues):
		stop = stopwords.words('english') + [""]

		with open(ALL_CLUES, encoding="latin-1") as fp:
			dict_guesses = fp.readlines()

		clue_mapping = dict()
		all_lengths = []
		for clue in clues:
			clue_mapping[clue] = list()
			if clues[clue] not in all_lengths:
				all_lengths.append(clues[clue])

		clue_statements = list(clues.keys())
		clue_vecs = dict()
		for clue in clue_statements:
			clue_vecs[clue] = [word for word in [word.strip(string.punctuation) for word in clue.lower().split()] if word not in stop]

		print(">>> STARTING ALL CLUES FETCH (V.1).....")
		for guess in dict_guesses:
			if len(guess.split()[0]) not in all_lengths:
				continue

			guess_statement = " ".join(guess.split()[4:])
			guess_vec = Counter([word for word in [word.strip(string.punctuation) for word in guess_statement.lower().split()] if word not in stop])

			for clue in clue_statements:
				if len(guess.split()[0]) == clues[clue]:
					clue_vec = Counter(clue_vecs[clue])

					# https://stackoverflow.com/questions/15173225/calculate-cosine-similarity-given-2-sentence-strings
					intersection = set(guess_vec.keys()) & set(clue_vec.keys())
					numerator = sum([guess_vec[x] * clue_vec[x] for x in intersection])

					sum1 = sum([guess_vec[x]**2 for x in guess_vec.keys()])
					sum2 = sum([clue_vec[x]**2 for x in clue_vec.keys()])
					denominator = math.sqrt(sum1) * math.sqrt(sum2)

					if not denominator:
						sim =  0.0
					else:
						sim = float(numerator) / denominator

					if sim > 0.65:
						clue_mapping[clue] += [guess.split()[0].lower()]

		for clue in clues:
			clue_mapping[clue] = list(set(clue_mapping[clue]))				

		return clue_mapping

	def fetch_words(self, clues):
		all_solved = self.all_solution(clues)
		print(">>> STORED CLUES.....")
		with open(CLUES_PATH, "w") as fp:
			json.dump(str(all_solved), fp)

if __name__ == '__main__':
	grid = CROSSWORD_GRID
	clues = dict()
	for clue in CROSSWORD_GRID:
		clues[clue] = CROSSWORD_GRID[clue]["length"]

	Words_Offline().fetch_words(clues)
<file_sep>from ast import literal_eval
from tabulate import tabulate
from file_path import *
import json
import z3
from schema import CROSSWORD_GRID

"""
NOTE: No length-verification is required in Solve(),
      as all clues retrieved from CLUES_PATH are of required length
"""

# Pattern is (initial_X, initial_Y), direction(D or A), length
# "": {"start":(), "direction":"", "length": },
GRID = CROSSWORD_GRID

class Solve():
	def __init__(self):
		pass

	def fetch_clues(self):
		"""Fetches the clues present in "clues.json"
		"""
		clues = dict()
		with open(CLUES_PATH) as fp:
			clues = literal_eval(json.load(fp))
		return clues

	def get_matrix(self):
		clues = self.fetch_clues()
		start_positions = dict()

		# finding the square matrix size
		max_val = 0
		for clue in GRID:
			start_positions[GRID[clue]["start"]] = clue

			if GRID[clue]["start"][0] > max_val:
				max_val = GRID[clue]["start"][0]
			elif GRID[clue]["start"][1] > max_val:
				max_val = GRID[clue]["start"][1]

		# As the GRID starts from 0, we have to add 1 to get actual max_val
		max_val += 1

		matrix = [[None for index in range(max_val)] for index in range(max_val)]

		# The following code encodes the matrix declared with z3.Int(VALUE)
		# If at a position value is: (z3.Int(VALUE)_1, z3.Int(VALUE)_2), it signifies intersection is taking place there
		# NOTE: _1 -> signifies the COLUMN index AND _2 -> signifies the ROW index
		for x_index in range(max_val):
			for y_index in range(max_val):

				if (x_index, y_index) in list(start_positions.keys()):
					pos_info = GRID[start_positions[(x_index, y_index)]]
					for i in range(pos_info["length"]):

						if pos_info["direction"] == "A":
							if isinstance(matrix[x_index][y_index + i], z3.z3.ArithRef):
								matrix[x_index][y_index + i] = (z3.Int("alpha_" + str(x_index) + "_" + str(y_index + i) + "_1"), z3.Int("alpha_" + str(x_index) + "_" + str(y_index + i) + "_2"))
							else:
								matrix[x_index][y_index + i] = z3.Int("alpha_" + str(x_index) + "_" + str(y_index + i))

						elif pos_info["direction"] == "D":
							if isinstance(matrix[x_index + i][y_index], z3.z3.ArithRef):
								matrix[x_index + i][y_index] = (z3.Int("alpha_" + str(x_index + i) + "_" + str(y_index) + "_1"), z3.Int("alpha_" + str(x_index + i) + "_" + str(y_index) + "_2"))
							else:
								matrix[x_index + i][y_index] = z3.Int("alpha_" + str(x_index + i) + "_" + str(y_index))

		return matrix, start_positions, max_val

	def convert_clues_code(self):
		"""converts all the clues (in string format) to a list of their ascii characters value
		   example: "mumbai" -> [109, 117, 109, 98, 97, 105]
		"""
		clues = self.fetch_clues()
		clues_ord = dict()

		for clue in clues:
			for guess in clues[clue]:
				try:
					clues_ord[clue].append([ord(ch) for ch in guess.lower()])
				except:
					clues_ord[clue] = [[ord(ch) for ch in guess.lower()]]

		return clues_ord

	def make_guess_constraint(self):
		clues = self.convert_clues_code()
		matrix, start_positions, max_val = self.get_matrix()

		clue_constraint = list()

		for x_index in range(max_val):
			for y_index in range(max_val):
				if (x_index, y_index) in list(start_positions.keys()):
					pos_info = GRID[start_positions[(x_index, y_index)]]
					clue = start_positions[(x_index, y_index)]

					guesses_ord = clues[clue]
					all_guesses_constraint = list()

					for guess_ord in guesses_ord:
						guess_constraint = list()
						x_i = x_index
						y_i = y_index

						for ch in guess_ord:
							if isinstance(matrix[x_i][y_i], tuple):
								# NOTE: _1 -> signifies the COLUMN index AND _2 -> signifies the ROW index
								if pos_info["direction"] == "D":
									matrix_val = matrix[x_i][y_i][0]
								elif pos_info["direction"] == "A":
									matrix_val = matrix[x_i][y_i][1]
							else:
								matrix_val = matrix[x_i][y_i]

							guess_constraint.append(z3.And(matrix_val == ch))

							if pos_info["direction"] == "D":
								x_i += 1
							elif pos_info["direction"] == "A":
								y_i += 1

						all_guesses_constraint.append(z3.And(guess_constraint))

					clue_constraint.append(z3.Or(all_guesses_constraint))

		clues_constraint = z3.And(clue_constraint)

		return clues_constraint

	def common_position_constraint(self):
		clues = self.convert_clues_code()
		matrix, start_positions, max_val = self.get_matrix()

		equality_constraint = list()

		for x_index in range(max_val):
			for y_index in range(max_val):
				if isinstance(matrix[x_index][y_index], tuple):
					first = matrix[x_index][y_index][0]
					second = matrix[x_index][y_index][1]

					equality_constraint.append(z3.And(first == second))

		common_position_constraint = z3.And(equality_constraint)

		return common_position_constraint

	def apply_constraints(self):
		solver = z3.Solver()
		solver.add(self.make_guess_constraint())
		solver.add(self.common_position_constraint())
		solver.check()
		
		return solver.model()

	def solution(self):
		solved = self.apply_constraints()
		solved_keys = [index.name() for index in solved]
		matrix, start_positions, max_val = self.get_matrix()

		for x_index in range(max_val):
			for y_index in range(max_val):
				if isinstance(matrix[x_index][y_index], tuple):
					matrix_val = matrix[x_index][y_index][0]
				elif matrix[x_index][y_index] != None:
					matrix_val = matrix[x_index][y_index]
				else:
					continue

				no = solved[matrix_val]
				ch = chr(no.as_long())
				matrix[x_index][y_index] = ch

		return matrix

if __name__ == '__main__':
	solve = Solve()
	print(tabulate(solve.solution()))
<file_sep>gensim==3.8.1
tabulate==0.8.6
nltk==3.4.5
z3_solver==4.8.7.0
inflect==3.0.2
requests>=2.20.0
z3==0.2.0
