How the N-Queens program works: Pidgin Python

A while ago, I wrote about a system that invites users to watch as it solves the N-Queens problem. I promised to write another post explaining, for non-programmers, how the solver works. I put “for non-programmers” in italics because I intend to take it seriously. I hope that after reading this post, someone without programming experience will understand how the solver works.

The solver is a computer program. Its operation is best understood as an algorithm, a finite sequence of clearly defined steps. You can look at the solver program itself on its Colab¹ page. It is written in the programming language Python². Most non-programmers will find it unapproachable. Yet to describe the solver with any precision requires something like a programming language. The typical compromise is to use what is often called pseudo-code³. Since the language we use in this post draws from both Python and English, we refer to it as Pidgin Python.

The explanation is organized into three parts, which I’ll cover in three separate posts.

• What is a programming language function?

• What is a recursive programming language function?

• How does the solver’s recursive function work?

The following will describe Pidgin Python as if it were an actual programming language, with a fixed syntax and rules of use. I’m describing Pidgin Python in this way to be as clear as possible. But since this is Pidgin Python, you needn’t take the syntax and rules too seriously. They are intended to give you a sense of the elements of the language rather than to specify formal constraints.

On the other hand, writing software is fairly demanding; to do it successfully requires a variety of tools for expressing one’s thoughts. I’m going to be as explicit as I can about what those tools of expression include.

The elements of Pidgin Python

Algorithms, functions, names, conditionals, and assignment of values

An algorithm⁴ is a finite sequence of well-defined steps. Each step is typically expressed as a single line of code.

A function is an algorithm in which:

• The steps are packaged into a unit.

• The unit is typically given a name.

• When the unit is run, it accepts (or may accept) input and produces (or may produce) output.

Here is a simple function that accepts two numbers as input and produces the larger of the two as output.⁵

function: maximum_of
input: number_a, number_b
if number_a is larger than number_b:
    set the output to be number_a;
otherwise:
    set the output to be number_b;

Things to notice:

• One often joins words with underscores when, together, the words refer to a single thing. In this example, maximum_of is the name of a function. Similarly for number_a and number_b. Each refers to a single number.

• The names in the list of input elements are arbitrary labels. They refer to the elements that are passed to the function as input.

• One can attach a value to a name—called assignment in most programming languages—by using the set … to be … pattern.

• The if and otherwise lines are ended with colons (:).

• The if/otherwise pattern allows one to perform one action or another depending on a specified condition. The two actions are written, indented, under the if and otherwise lines. In this example, each action is only one step. In general, an action may include multiple steps. This pattern is typically called a conditional.

When one wants to use this function to determine a value, one writes:
maximum_of(x, y)
i.e., the function name followed, in parentheses, by the input elements.

For example, if one wants to find the larger of price_1 and price_2, one could write:
set larger_price to be maximum_of(price_1, price_2)

Two more things to notice:

• Within the function, number_a will refer to price_1, and number_b will refer to price_2.

• In Pidgin Python, one can make up names as needed. In the line above, we made up the name larger_price to keep track of the larger of the two prices.

Loops and comments

For a more complex example, suppose one has a list of numbers and wants to know its length. One might define a function as follows.

function length_of_list
input: list_x
# We will use list_length to count the elements in list_x.
# Since we have not yet seen any list elements, list_length 
# starts at 0.
set list_length to 0
repeat the following for each element in list_x:
    remove the first element from list_x
    # The next element in line becomes the new first element.
    # We increment list_length by 1 for each element.
    add 1 to list_length
# Having counted all the elements, we set output to be list_length.
set output to be list_length

A problem with this function is explained in this footnote.⁶

A second problem is explained in this footnote.⁷

Two more things to notice:

• One can include non-functional lines in a Pidgin Python program by

  starting the line with #. In virtually all programming languages, such lines are called comments. They are included to explain to a reader the intended operation of a portion of a program.

• The repeat … for each element in … pattern allows one to specify that some action or actions are to be repeated for each element in a collection. Programmers informally call this construct a loop. We repeat the indented lines once for each element in list_x.
  The same pattern can be used to repeat some actions as long as a condition holds. In that case, the repeat line would look like this.

  repeat the following as long as list_x is not empty:

Since Pidgin Python is an informal language, one might leave out the following and change as long as to while.
repeat while list_x is not empty:
or even leave out repeat to be closer to Python.
while list_x is not empty:

The pattern is as simple as while …, where the desired condition replaces … .

Summary

This post has described the elements of Pidgin Python: assignment of values, comments, conditionals, functions, loops, and names. Subsequent posts use these concepts to explain the N-Queens solver.

1. As the earlier post explains, Colab (short for Google Colaboratory) is a free, cloud-based platform that allows you to write and execute Python code inside your web browser.

2. Python is a general-purpose programming language that emphasizes simplicity and readability. (See Wikipedia’s Python page.)

3. An informal description of the steps of an algorithm. Each step is explained in terms of the actions and conditions that comprise it. The overall description is a mixture of
(a) conventions used in actual programming language and (b) informal, usually self-explanatory notations and natural language descriptions. (See Wikipedia’s Pseudocode page.)

4. A more limited definition requires that to be an algorithm, a sequence of steps must comprise “a systematic procedure that produces—in a finite number of steps—the answer to a question or the solution of a problem.” (See the Britannica entry for algorithm.) Strictly, algorithm is not an element of Pidgin Python. It is included as a prerequisite concept.

5. When a function produces a result as output, it is commonly said to return that result.

6. We run into a problem if the input list is empty. The first thing the program does to the input list is to remove its first element. But if the list is empty, there is no first element. An error will occur, and the program will abort. We can fix this problem by checking whether the input list is empty before starting the loop. Although making this check is essential for program correctness, we won’t discuss the modification since it does not further the discussion of Pidgin Python.

7. Although the length_of_list function produces the correct answer, it illustrates a subtle problem. The function repeatedly removes elements from the input list until the list is empty—thereby destroying the list whose length we seek! A simple approach to this problem is to copy the input list at the start of the function and run the length_of_list function on the copy. (This assumes we have a function copy that can produce a copy of a list.)

  set list_x_copy to be copy(list_x)
  # continue the function using list_x_copy instead of list_x