charlesreid1.com research & teaching

CSE 143 Final Project: Hilbert Sort: 1. The Problem

Posted in Computer Science

permalink

Table of Contents

This is the first in a series of three posts detailing the Hilbert Sort problem, its solution, and its implementation. This post sets up the problem.

Hilbert Sort: Motivation

In the next few series of posts, we will cover the Hilbert Sort problem, how it works, and how to implement it.
However, before we describe the problem further, let's start with some motivation for solving this problem.

Suppose we're dealing with a very large number of independent objects on a 2D coordinate grid, each with a coordinate location \((x,y)\). (For example, a large population of particles moving in a fluid, or a large number of characters on a map in a game.)

Here is our box of particles:

Box of Particles

Now, suppose that we have more data than can be handled by a single computer, and we want to arrange the data on different computers. However, we want to arrange the data in such a way that we preserve the spatial characteristics of the data.

If we implement a naive sort method for Cartesian points that sorts points by x coordinate value, breaking ties with the y coordinate value, we end up with points that are neighbors in space, but far away in the data container's storage (like an array). This is particularly true if there are large crowds of points in the grid.

Here is an illustration of a set of points and their resulting storage schema in an array that sorts points by x coordinate. It shows two purple particles, close by in space, but with
several green particles further away distance-wise but not with respect to the x coordinate. The spatial locality of points is not preserved in the data container, so clearly, a better method of sorting and organizing points is needed.

Bad Schema

An alternative to this schema that yields better locality properties, but that leads to a much higher cost for sorting points, involves iterating over each point, and for each point, finding the closest points to it in space. However, this itself requires iterating over each point. This approach ends up walking over each point (the point whose nearest neighbors we are finding), and doing a second nested walk over each point (checking if a point is a nearest neighbor to this one). The overall cost of doing this is \(O(N^2)\).

It is a deceptively tricky problem: how to organize a large group of points in a way that preserves spatial locality?

But first, we'll cover the topic of space filling curves, then return to this topic.

Space Filling Curves

Mathematician Giuseppe Peano was a prolific teacher and researcher known for many things, but one of his more curious ideas is known as the Peano Curve. Peano was attempting to answer the question of whether a continuous curve could be bounded by a finite space, and he invented a counter-example: a recipe for breaking a curve into parts that can be replicated and repeated and applied to the copies as many times as desired, and always result in a continuous curve.

The way that space-filling curves in general are constructed is to create a pattern, then scale it down and repeat it, attaching subsequent scaled-down, repeated curves. Peano simply invented the first curve; there are many variations on the original space-filling curve idea (including the Hilbert Curve - more on that in a moment).

The original 1890 paper by Giuseppe Peano is entitled "Sur une courbe, qui remplit toute une aire plane", published in 1890 in Mathematische Annalen I, Issue 36. Unfortunately, it has no pictures, but here is a rendering from Wikimedia Commons:

Peano Curve

(Link to original on Mediawiki Commons)

Now, the Peano curve was nice, but it had some mathematical properties that made it difficult to deal with. So in 1890, David Hilbert published a follow-up paper in Mathematische Annalen I Issue 38, entitled "Ueber die stetige Abbildung einer Linie auf ein Flächenstück", which slightly modified the recipe to create a curve with more elegant mathematical properties.

Also, he included pictures.

Here is the first figure from Hilbert's paper:

Hilbert Curve

And here is a slightly cleaner rendering of the Hilbert Curve pattern repeated six times:

Hilbert Curve

(Link to original on Wikimedia Commons)

From the abstract of Hilbert's paper:

Peano has recently shown in the Mathematical Annals, 2 by an arithmetical observation, how the points of a line can be mapped continuously to the points of a surface part. The functions required for such a mapping can be produced more clearly by using the following geometrical view. Let us divide the line to be represented-about a straight line of the length 1-into four equal parts 1, 2, 3, 4, and the surface which we assume in the form of a square of the side length 1 Straight into 4 equal squares 1, 2, 3, 4 (Fig. 1). Secondly, we divide each of the partial sections 1, 2, 3, 4 again into 4 equal parts so that we obtain on the straight the 16 partial sections 1, 2, 3, ..., 16; At the same time, each of the 4 squares 1, 2, 3, 4 is divided into 4 equal squares, and the numbers 1, 2, ..., 16 are then written to the resulting 16 squares, That each successive square follows the previous one with one side (Fig. 2). If we think of this method, as shown in Fig. 3, the next step, it is easy to see how to assign a single definite point of the square to any given point of the line. It is only necessary to determine the partial stretches of the line to which the given point falls. The squares indicated by the same numbers are necessarily in one another and include a certain point of the surface piece in the boundary. This is the point assigned to the given point. The image thus found is unambiguous and continuous, and vice versa, each point of the square corresponds to one, two, or four points of the line. Moreover, it appears remarkable that, by a suitable modification of the partial lines in the squares, a clear and continuous representation can easily be found, the reversal of which is nowhere more than three-fold.
- David Hilbert, "Über die stetige Abbildung einer Linie auf ein Flächenstück", Mathematische Annalen Vol 38

Thanks to Google Translate for an incredible job.

Constructing a Hilbert Curve

To construct a Hilbert curve, you just have to follow the recipe. It doesn't matter what your square contains so far, or how many levels in you are, whether it's the first curve or the five hundredth:

  1. First, take yer square.

  2. Second, quadruple yer square. That means, make four copies, that all make a square.

  3. Now rotate the bottom left and bottom right via diagonal reflection.

  4. Fourth step is, you're done - that's you're new square!

Performing a Hilbert Sort

We will omit a proof of the statement, but given a set of unique (x,y) points, we can always construct a minimal-size Hilbert Curve that visits each point only once.

Points can be sorted, then, according to when they would be visited by said Hilbert Curve. And this ordering provides better preservation of spatial locality and structure of points when aligning them in memory, because these space-filling curves are recursive and preserve spatial locality in a top-down fashion.

For example, if we have two points in our square, one in the lower left and one in the lower right, and we are sorting them via a Hilbert Sort, we definitely know that a Hilbert curve constructed to visit both of these points will definitely visit the lower left point (the quadrant where the Hilbert curve starts) before it visits the lower right point (in the quadrant where the Hilbert curve stops).

This requires thinking about \((x,y)\) points in the box in terms of quadrants, and the order in which the Hilbert curve will visit each quadrant or region, rather than thinking in terms of the explicit Hilbert curve that will visit each particular \((x,y)\) point:

Box of Particles, Divided Into Quadrants

This is a subtle shift in the thinking about this problem, but it is crucial to a successful implementation of a Hilbert sort. The problem that will follow, which asks to implement the Hilbert sort, has many distracting details, including the Hilbert curve itself.

Remember, in Hilbert sort, the end goal is not the curve itself, but the sort order.

Here is how the quadrant-by-quadrant partitioning to sort elements ends up looking when applied repeatedly:

Repeated Applications

It is important to note that the two diagonal reflections happening in the corners are the trickiest part of this problem. We will cover this operation in greater detail in the solution blog post.

Problem Statement

Following is a paraphrased problem statement from the original ACM ICPC Regional Programming Competition problem statement that this problem and its solution was based on.

"If points \((x,y)\) are sorted primarily by x, breaking ties by y, then points that are adjacent in memory will have similar x coordinates but not necessarily similar y, potentially placing them far apart on the grid. To better preserve distances, we may sort the data along a continuous space-filling curve.

"We consider one such space-filling curve called the Hilbert curve...

"Given some locations of interest, you are asked to sort them according to when the Hilbert curve visits them. Note that while the curve intersects itself at infinitely many places, e.g., at \((\frac{S}{2}, \frac{S}{2})\), making S odd guarantees all integer points are visited just once."

Here is an example input file, giving a set of points on an \(M \times N\) grid:

    14 25
    5 5 Honolulu
    5 10 PugetSound
    5 20 Victoria
    10 5 Berkeley
    10 10 Portland
    10 15 Seattle
    10 20 Vancouver
    15 5 LasVegas
    15 10 Sacramento
    15 15 Kelowna
    15 20 PrinceGeorge
    20 5 Phoenix
    20 10 SaltLakeCity
    20 20 Calgary

The corresponding output can be verified intuitively, assuming the coordinates given above are accurate! Here is the output. Indeed, the order in which each city is visited is what we would expect if we drew a space-filling Hilbert curve over a map of the western United States and Canada.

    Honolulu
    Berkeley
    Portland
    PugetSound
    Victoria
    Vancouver
    Seattle
    Kelowna
    PrinceGeorge
    Calgary
    SaltLakeCity
    Sacramento
    LasVegas
    Phoenix

Now that we've used up all of our space here describing the problem, in a follow-up post we will go into greater detail about how to solve the problem conceptually, and come up with some pseudocode for a recursive method (since this is a recursive task). Then, a third post will go into greater detail about the final Java code to perform this task.

References

  1. "ACM Pacific Region Programming Competition." Association of Computing Machinery. 19 June 2017. <http://acmicpc-pacnw.org/>

  2. "Sur une courbe, qui remplit toute une aire plane." G. Peano. Mathematische Annalen 36 (1890), 157–160. (pdf)

  3. "Über die stetige Abbildung einer Linie auf ein Flächenstück." D. Hilbert. Mathematische Annalen 38 (1891), 459–460. (pdf)

  4. "Hilbert Curve." Wikipedia: The Free Encyclopedia. Wikimedia Foundation. Edited 29 April 2017. Accessed 23 June 2017. <https://en.wikipedia.org/wiki/Hilbert_curve>

  5. "Peano Curve." Wikipedia: The Free Encyclopedia. Wikimedia Foundation. Edited 16 October 2016. Accessed 23 June 2017. <https://en.wikipedia.org/wiki/Peano_curve>

CSE 143 Final Project: Classy

Posted in Computer Science

permalink

Table of Contents

Problem Description

Comedian John Cleese, in his memoir So Anyway..., described the social classes of his mother and father as "upper-uper-lower-middle class" and "middle-middle-middle-lower-middle class", respectively. Write a program that will sort individuals based on a labeling of their social standing by class.

The three main classes are upper, middle, and lower. Classes progress hierarchically from right to left. For example, lower-upper would come before lower-lower. There is also ordering within a class, so upper-upper is a higher class than middle-upper.

Once you have reached the lowest level of detail of one of the classes, assume that all further classes are equivalent to middle. This means upper and middle-upper are equivalent, and middle-middle-lower-middle and lower-middle are equivalent.

Input files have a line with the number of names, then one name per line, with the name, a colon, then the title. For example:

5
mom: upper upper lowre middle class
dad: middle middle lower middle class
queen_elizabeth: upper upper class
chair: lower lower class
unclebob: middle lower middle class

The proper output should be the name of each person, sorted in order according to their social status, e.g.,

queenelizabeth
mom
dad
unclebob
chair

Solution Approach

(This discusses an approach specific to Java, but a similar approach could be adopted for other languages in which comparison operators can be overloaded for objects.)

The problem lays out all of the essential components that a solution requires. This can most easily be implemented using an object and a comparator: the object represents a person, and has a field to store their name and a field to store their titles (array-like container for Strings). These objects would then implement comparators so that individuals could be compared. This functionality then allows the array to be sorted, using the built-in Collections sort function or a custom sort function.

Algorithm

The classy algorithm can be briefly described in this way: we are iterating over two lists of strings, of possibly unequal length, and comparing them right to left. We have a few very simple rules that determine whether one title comes before the other. We have a few simple rules for breaking ties.

The core of the algorithm is the comparison operation, in which we are assuming that these two things are equal, until we encounter evidence to the contrary. Briefly, the pseudocode can be expressed as follows (where we adopt the Java convention that a negative result means the first item comes before the second item):

if item1 < item2:
    return -1
else if item1 > item2: 
    return 1
else:
    # keep going

If we find a difference, we stop and return right away, but otherwise we continue, and assume the two are equal.

The problem statement tells us that if a title is missing, and the title lengths are mismatched, we should fill in with "middle". This translates into a second comparison block, in which one of the items is hard-coded as "middle", due to an empty list of titles:

if item < "middle":
    return -1
else if item > "middle"
    return 1
else:
    # keep going

Here is how these fit together: Start by splitting the input titles, most likely strings, into lists Iterate over each title, from right to left, and compare the titles. When we reach the end of the shorter list, continue comparing titles right to left, filling in "middle". If the titles are tied, break ties with name. The algorithm should be implemented in a way that has access to both the titles and the names of the two people being compared. In Java, we can define people objects, then we can either have People objects implement Comparable, or we can define our own Comparator for two People objects.

Pseudocode

When we translate the above procedure into Python-like pseudocode, here is the result:

define compare_lengths(title1, title2):
    list1 = title1.split()
    list2 = title2.split()
    for i in min(list1.size, list2.size):
        sal1 = list1.reverse[i]
        sal2 = list2.reverse[i]
        if sal1 < sal2:
            return -1
        else if sal1 > sal2:
            return 1

    larger_list = <point to larger list>
    for i in ( min(list1.size,list2.size)+1 ... max(list1.size, list2.size) ):
        salX = larger_list.reverse[i]
        if SalX < "middle":
            return -1
        if salX > "middle"
            return 1

    # If you get here, it's a tie. Use names for tie-breaker.

Using an Object-Oriented Approach

To apply object-oriented principles in this situation, we want to bundle together related data, and abstract away details. That means we want to create an object to associate the name and titles of a given person, and implement functionality to allow each person to be compared with other people.

This will allow us to create two people and compare them with greater than, less than, or equal to operators. More importantly, this will also allow us to perform sorting.

Our Java program Classy is a simple driver that loads the names and titles of people from standard input.

The Person class stores associated name and title data for each person. This class implements the Comparable interface, which requires it to implement a compareTo() method.

class Person implements Comparable<Person> {

    ...

    public int compareTo(Person p2) { 

The Person class constructor just tokenizes one line of input, populating the titles list and the person's name. Here is the declaration of those private fields:

class Person implements Comparable<Person> {
    private String name;
    private ArrayList<String> titles;

    ...

The implementation of the compareTo method utilized Stack objects to examine the sequence of titles in reverse.

Pop the stacks until one of them is empty. Then, keep popping until both are empty, using "middle" in place of the empty stack.

    /** Compare a person to another person. */
    public int compareTo(Person p2) { 

        Stack<String> st1 = new Stack<String>();
        Stack<String> st2 = new Stack<String>();

        // Add names to stack, left to right
        for(String title : this.getTitles()) {
            st1.push(title);
        }
        for(String title : p2.getTitles()) { 
            st2.push(title);
        }

        // Compare each name, from right-to-left.
        // If stack 1 is not empty, pop next item, otherwise use "middle"
        // If stack 2 is not empty, pop next item, otherwise use "middle"

        int max = Math.max(this.getTitles().size(), p2.getTitles().size());
        for(int i=0; i<max; i++) {

            // Pop names from the stack, right to left.
            String s1, s2;

            if(!st1.isEmpty()) {
                s1 = st1.pop();
            } else {
                s1 = "middle";
            }

            if(!st2.isEmpty()) {
                s2 = st2.pop();
            } else {
                s2 = "middle";
            }

            // Rather than converting strings to numbers,
            // compare the strings directly (lower < middle < upper).
            int res = s2.compareTo(s1);

            // Return the first non-zero value
            if( res != 0 ) {
                return res;
            }
        }

        // If we reach here, there was a tie.
        // Use name as tie breaker.
        return this.getName().compareTo(p2.getName());
    }

Code

Here is the entire Classy code, also available on git.charlesreid1.com:

import java.util.*; 
import java.io.*;
public class Classy { 

    public static void main(String[] args) { 
        Scanner s = new Scanner(new BufferedReader(new InputStreamReader(System.in)));

        // Read the input file: new Person for each line
        int n = Integer.parseInt(s.nextLine());
        ArrayList<Person> people = new ArrayList<Person>();
        while(s.hasNextLine()) {
            String line = s.nextLine();
            String[] deets = line.split(" ");
            Person p = new Person(deets);
            people.add(p);
        }

        Collections.sort(people);
        for(Person p : people) { 
            System.out.println(p);
        }
    }
}

class Person implements Comparable<Person> {
    private String name;
    private ArrayList<String> titles;

    /** Person constructor - pass in a String array with the deets. */
    public Person(String[] deets) { 
        name = deets[0];
        // Remove : from name
        name = name.substring(0,name.length()-1);

        // initialize list of classes 
        titles = new ArrayList<String>();
        for(int i=1; i<deets.length-1; i++) { 
            titles.add(deets[i]);
        }
        // Last word will be "class", so ignore.
    }

    /** Get a person's name. */
    public String getName() { return name; }

    /** Get a person's titles in an ArrayList. */
    public ArrayList<String> getTitles() { return titles; }

    /** Get a string representation of a person. */
    public String toString() { return getName(); }

    /** Compare a person to another person. */
    public int compareTo(Person p2) { 

        Stack<String> st1 = new Stack<String>();
        Stack<String> st2 = new Stack<String>();

        // Add names to stack, left to right
        for(String title : this.getTitles()) {
            st1.push(title);
        }
        for(String title : p2.getTitles()) { 
            st2.push(title);
        }

        // Compare each name, from right-to-left.
        // If stack 1 is not empty, pop next item, otherwise use "middle"
        // If stack 2 is not empty, pop next item, otherwise use "middle"

        int max = Math.max(this.getTitles().size(), p2.getTitles().size());
        for(int i=0; i<max; i++) {

            // Pop names from the stack, right to left.
            String s1, s2;

            if(!st1.isEmpty()) {
                s1 = st1.pop();
            } else {
                s1 = "middle";
            }

            if(!st2.isEmpty()) {
                s2 = st2.pop();
            } else {
                s2 = "middle";
            }

            // Rather than converting strings to numbers,
            // compare the strings directly (lower < middle < upper).
            int res = s2.compareTo(s1);

            // Return the first non-zero value
            if( res != 0 ) {
                return res;
            }
        }

        // If we reach here, there was a tie.
        // Use name as tie breaker.
        return this.getName().compareTo(p2.getName());
    }
}

References

  1. "ACM Pacific Region Programming Competition." Association of Computing Machinery. 19 June 2017. <http://acmicpc-pacnw.org/>

  2. "finalproject-143 (git repository)." Charles Reid. Modified 16 June 2017. Accessed 23 June 2017. <https://charlesreid1.com:3000/cs/finalproject-143/src/master/classy/Classy.java>

CSE 143 Final Project: Checkers

Posted in Computer Science

permalink

Table of Contents

The Problem

This is a programming challenge that was assigned to some of my CSE 143 students as a final project for their class.

The origin of this problem was the Association of Computing Machinery (ACM)'s International Collegiate Programming Competition (ICPC), in particular the Pacific Northwest Regional Competition, Division 1 challenges from 2015.

Link to Pacific NW ACM ICPC page.

Problem Description: Checkers

In the Checkers problem, you are presented with a checkerboard consisting of black and white squares. The boards follow a normal checkers layout, that is, all of the pieces occupy only the light or dark squares on the board.

There are several white and black pieces arranged on the checkerboard. Your goal is to answer the following question: can any one single black piece be used to jump and capture all of the white pieces in a single move? This assumes that each of the black pieces are "king" pieces and can jump in either direction.

For example, the following 7x7 board configuration has one black piece that can jump all of the white pieces on the board with a single sequence of moves. The black piece at B2 jumps to D4, then to F2.

Checkerboard 1 - demonstrate solution

If an additional white piece is added, there is no sequence of moves that will allow any black piece to jump all of the white pieces.

Checkerboard 2 - demonstrate no solution

Input File

The input file consists of one line with a single integer, representing the size of the (square) board. Following are characters representing the board state.

. represents a square that pieces cannot occupy - the off-color squares.

_ represents an unoccupied but valid square.

B represents a black piece. W represents a white piece.

Example:

8
._._._._
_._._._.
.W._.B._
_.W.W._.
.W.B._._
_._._._.
.W._.W._
_._._._.

Output

The output is simple: simply state which of the black checkers is capable of jumping each of the white checkers. If none, say "None". If multiple, say "Multiple".

The Solution

Keep It Simple

To successfully solve the checkers problem, it is important to keep it simple. There are different ways of representing the checkers problem abstractly, but the best representation in a program is the simplest one - use a 2D array of chars to represent the board.

Also as usual with permutations of arrangements on boards of fixed size, recursion will be useful here.

Solution Analysis: Parity

We can begin our analysis of the checkers problem with a few observations.

First, we know that the valid squares for checkers are squares that are off by two. But we know further that the black checkers must only move in jumps, which mean that a piece at \((i,j)\) can only reach squares indexed by \((i + 4m, j + 4m)\) or \((i + 4m + 2, j + 4n + 2)\), where \(m, n\) are positive/negative integers.

That is, the checker pieces can make jumps of 2 squares at a time. For example, if a checker starts at the square \((3,3)\) and jumps a white piece down and to the right, it moves to square \((5,5)\) or \((3+2, 3+2)\). If it jumps another white piece up and to the right, it moves to square \((3, 7)\) or \((3, 3 + 4)\).

Further, we know that a black checker can only jump checkers at squares of the form \((a + 2m + 1, b + 2n + 1)\). Thus, black checkers either have the correct parity to jump all of the white checkers, or they have the same parity as the white checkers (in which case they can be ignored).

If a black checker does not have the correct parity to jump white checkers, we can save ourselves time by not checking it.

For example, in the checkerboard below, there are four black checkers, but only one (row 2, column 3) has the correct parity to jump each of the white pieces. The other three are

The other three has the correct parity, while the black checker in the right do not.

Checkerboard 3 - illustrate parity

Solution Analysis: Graphs and Euler Tours

If we examine the squares with correct parity, we can translate the board into a graph representation. Squares with the "jump" parity are nodes on the graph that can perform jumps. (No whites should have jump parity, otherwise the board is impossible.)

Squares with the "jumped" (i.e., white pieces) parity are nodes that are being jumped. These nodes form the edges between jump parity nodes, and these edges must be occupied by a white piece for a black piece to be able to pass through them. In this way, we can think of white pieces as "bridges" between jump parity squares.

This representation leads to thinking about the tour the black checker takes through the checkerboard as an Euler tour across the graph.

An Euler Tour, made famous by the Seven Bridges of Königsberg problem solved by Euler in 1736, is a path that visits each node of the graph, traversing each edge once and only once.

Euler showed that an Euler path visiting each edge of the graph depends on the degree of each node in the graph. For an Euler path to exist, the graph must be connected and there must be exactly zero or two nodes of odd degree.

If we walk through the checker board and construct the graph (or assemble the information that the graph would have told us), we can determine whether an Euler tour exists, and find the Euler tour.

The example above shows a checkerboard with two white pieces forming two edges. The first white piece connects a jump parity square with a black piece on it to a jump parity square that is empty. The second white piece connects two empty jump parity squares.

The black "entrance" node has an odd degree (1). The second, unoccupied node has an even degree (2). The third, unoccupied node has an odd degree (1). Therefore the graph has two nodes of odd degree, so an Euler tour exists.

If we modify this example to add one additional white checker piece on a square with correct parity, the Euler Path analysis identifies this as a board with no solution:

Checkerboard 4 - illustrate no Euler tour

This is because three of the nodes have degree 1 and one node has degree 3, for a total of 4 nodes with odd degree. The requirements for an Euler Tour to exist (equivalent to saying a solution to the Checkers problem can be found for a given black checker) are violated, so no solution can be found.

If we were to add a second black checker piece two squares away, an alternate graph (highlighted in blue) can be constructed, and an alternate Euler path through the graph is available.

Checkerboard 5 - illustrate alternate Euler tour

On the red graph, each node has an odd degree, so the number of nodes with odd degree is not 0 or 2. On the blue graph, only the start and end nodes have an odd degree (1), while the rest of the nodes have a degree of 2 (one input and one output). This means an Euler Tour exists on the blue graph.

In practice, a given black piece has a given graph connecting squares on the checkerboard - we can ask each node on that graph for its degree, and the degree of its neighbors, and if a black piece results in an invalid number of odd nodes, we can abandon it.

Solution Algorithm

The algorithm to find solutions to this problem very roughly follows this pattern: First, perform a parity check to determine if a solution is impossible. Loop over each square of the board, looking for black pieces * For each black piece: * Look at each neighbor: * Determine if there is a square to jump to if neighbor is white * Determine number of odd neighbors * Fail if more than 2 odd neighbors, or 2 odd neighbors and odd self * Backtracking: explore neighbors, determine if all whites can be jumped

Solution Pseudocode

The solution code has three basic parts (four, including the input parser): Initialize and parse the board Loop over each square, checking if black piece is a solution Function to check if black piece is a solution piece (Recursive backtracking) function to jump each white piece possible to jump.

Start with the initialization of the board and looping over each black piece to check if it is a solution piece:

initialize solutions counter
initialize board

for each s in squares:
    if s is black piece:
        if s is solution piece:
            increment solutions counter
            save location

print summary

Now we just need to implement functions that can (a) check if a square contains a black piece (easy) and (b) check if a black piece is a solution piece (uh... kind of what the whole problem boils down to, no?)

We break that functionality into a separate function. Here is the pseudocode to check if a black piece in a particular square is a solution piece. This function iterates over squares with jump parity - that means this function traverses the nodes only in the graph representation of the checkerboard.

This function enforces the requirement that no node can have more than 2 odd neighbors, or be odd if it has more than 2 odd neighbors, since a graph must have 0 or 2 nodes with odd degree in the graph for an Euler Tour to exist.

While we're at it, we also check if there are any white checker pieces without a square to land in when they are jumped (i.e., landing square blocked by another black piece or at edge of board).

function is solution piece:
    for each square of similar "jump" parity:
        for each neighbor:
            check if neighbor is odd 
            if a neighbor square is white:
                if next square is not empty:
                    fail fast

    if more than 2 odd neighbors, or 2 neighbors and odd:
        fail fast

    # we have a viable solution

    recursively count number of jumped white checkers 

    if number of jumped white checkers equals number of white checkers on board:
        return true

Finding squares of similar jump parity is as easy as looping over each row and column, and checking if it is off by 2 with the row/column of the black checker piece that we are currently checking. Checking if a neighbor is odd is as straightforward as counting its degree - checking each of its four neighbors and determining which ones are open. This leaves finding the number of jumped white checkers as the only functionality left to define.

define number of jumped white checkers:
    initialize white checkers jumped counter
    for each neighbor:
        if white piece, unvisited, with an empty place to jump to:
            visit white piece
            increment white checkers jumped
            call number of jumped white checkers on next next neighbor
            # this should be the empty space
    return number white checkers jumped

References

  1. "ACM Pacific Region Programming Competition." Association of Computing Machinery. 19 June 2017. <http://acmicpc-pacnw.org/>