Place Name Puzzle Solver, aka 'City Match'

Dr. Phillip M. Feldman

1. Introduction

Most of us, at one time or another, have played a game or worked on a puzzle that involved finding the name of a city or country that satisfies certain conditions. This online solver solves a wide range of such problems.

Here are a few examples of problems that this solver can answer:

The city database that I'm using currently contains 720 cities. This number is expected to slowly grow over time. The current rules for deciding whether a given city is included are as follows:

  1. Any city in North America, Europe, Australia, New Zealand, or Israel having a greater-metropolitan-area population of 300,000 or more is included.

  2. In other areas of the world, any city having a greater-metropolitan-area population of 1,000,000 or more is included.

  3. Certain cities that do not meet the above criteria, but that have some special historical, cultural, or political significance are also included. These are decided on a case-by-case basis.

For cities in the United States and Canada, the database contains the name of the city, the name of the U.S. state or Canadian province, and the name of the country. For cities in all other countries, the database stores only the names of the city and the country. The United States is always abbreviated as "U.S."; names of other countries and of U.S. states, Canadian provinces, and cities are never abbreviated.

The city database was constructed by hand. Errors are fixed as these come to my attention; undoubtedly that are many that have not yet been discovered. All specific error reports are welcome and will be promptly addressed.

2. Using City Match with Hangman-Style Templates

Inputs to the City Match program consist of two template fields and two checkboxes. When the Use Python Regular Expressions checkbox is unchecked, which is the default, the contents of the template fields are treated as hangman-style templates. This mode of operation is recommended for most users.

The first template specifies any restrictions on the name of the city. The second specifies any restrictions on the name of the county, U.S. state, or Canadian province.

Each template is a hangman-style string containing letters, spaces, and any of the following special characters:

Here are a few examples:

Some city names contain the word city; examples are Guatemala City and Mexico City. Depending on the rules of the game or puzzle, one may wish to ignore the word city for purposes of determining whether a given city name matches the specified template. If, for example, if one wishes to find city names that end with the letter y, one probably does not want Guatemala City and Mexico City to be returned as matches. A check box (see below) allows one to control whether the presence of the word city in the name of a city is counted as significant.

Note:

3. Using City Match with Python Regular Expressions

Python regular expressions, otherwise known as regexes, are much more powerful than the hangman-style templates described in the previous section, but are also more difficult to use. A full exposition on regexes is beyond the scope of this document, but many excellent references are available. I recommend starting with the link that appears at the beginning of this paragraph. Here are a couple of examples that illustrate the kinds of things that one can do with regular expressions:
  • To find cities whose names contain only the letters a-h, specify [a-h]*$ for the city regex, leave the country regex blank, and check the "Use Python regular expressions" checkbox. The expression [a-h] in the regex is an example of what is known as a character class; this defines a set of characters. (There is only one city in the database that matches this template).

  • Suppose that we wish to find cities whose names begin and end with the same letter, where this letter is not a. This can be done using a character class together with something known as a back reference. Specify ([b-z]).*\1$ for the city regex, leave the country regex blank, and check the "Use Python regular expressions" checkbox.

    4. Run City Match Solver Online

    To run city_match.py online:

    1. In each box, either enter a template or clear (remove) the template.

      • If a box is left empty, no filtering of results is done based on the corresponding database field. (If, for example, one enters 'Russia' into the second field and leaves the first field empty, the program will return a list containing all Russian cities in the database).

      • Upper- and lower-case can be used interchangeably.

      • One can move from the first box to the second by pressing the tab key.

    2. Make sure that the checkbox settings are as desired.

    3. Click on the green button.


      City:        Country, U.S. State, or Canadian Province: 

    Ignore the word 'City' in city name     Use Python regular expressions


    Last update: 19 July, 2015