One of the fundamental parts of the paper we are basing this work on is a type of sequence the authors of the paper call a non-sum-one-difference-zero sequence, or an NS1D0 sequence. These sequences are key to the paper and our work because they offer the connection between the n-queens problem and the Steiner Triple Systems; from an NS1D0 sequence we can produce a Steiner Triple System, and the modified version of the n-queens problem can produce NS1D0 sequences. In future weeks, I plan to break down each of those steps in the process in greater detail, but for now let's discuss the NS1D0 sequences.
How do you define an NS1D0 sequence?
Every NS1D0 sequence has an order n, which must be an odd integer greater than 1. This order determines the length of the sequence as well as the numbers that can be within the sequence with these rules:
The length of the sequence will be (n-1)/2 + 1, with items in the sequence numbered from 0 to (n-1)/2. Those items are typically denoted as a sub i, but given the constraints of this platform I will label them as a[i].
The sequence will contain integers between 0 and n-1.
Beyond those base rules, each sequence is defined in terms of these four rules:
a[0] will always be 0, and a[(n-1)/2] will always be 1.
n/2 (rounded up) will not be in the sequence.
For every integer b such that 1 < b < n, either b may be in the sequence OR ((1 - b) % n) may be in the sequence, but not both.
For every integer c such that 1 <= c < n, exactly one of c OR ((-c) % n) must be expressed as the difference of two consecutive elements in the sequence. [1]
Some examples sequences are below:
Every order n can have multiple valid NS1D0 sequences. In fact, as n increases, the number of valid NS1D0 sequences increases:
Generating NS1D0 sequences programmatically
The easiest way to get these NS1D0 sequences is through a brute force approach, which is what I did first. I wrote a python script that generates all possible sequences based on the two basic rules (length and number contents) as well as rule 1 of the core rules (a[0] = 0, a[(n-1)/2] = 1). Then, I combed through each of those sequences to see which fit with the other three rules. This approach works fine with n < 17, but as the number of possible sequences stacks up, so too does running time and computational power used, so another approach is needed.
We are hoping that the process of developing a specialized n-queens board and solving it which is described in the paper is a more useful and efficient way of finding these sequences.
Edit:
[1]. Both the paper and the original post here state rule four as "only one" of those numbers can be expressed in that way. It is more accurate to say that "exactly one" of those numbers must be expressed in that way, as a sequence without those numbers does not fulfill the requirements of an NS1D0 sequence. This may seem like a trivial difference in words, but given that rule 3 uses the same wording, while allowing for the possibility of 0 occurrences, it is important that a distinction is made. I have also updated my tables to include accurate representations of NS1D0 sequences and accurate numbers of true NS1D0 sequences.
Edit 2:
I will leave my previous edit for posterity, but I've come to realize that the wording of the two rules is actually consistent. I did not realize this previously, because having rule 3 require either one of b or 1-b in the sequence in actuality winds up requiring that exactly one of them be present, due to the number of slots in the sequence. Despite the wording being consistent between the two rules, I believe the wording is unclear and should be amended to "exactly one" rather than "only one".
תגובות