414298141056 Quarto Draws Suffice!
In how many distinct ways can the integers 0 through 15 be arranged
in a 4x4 array such that the bit-wise OR over each row, each column,
and each diagonal is 15, and the bit-wise AND over each row, column,
and diagonal is 0?
For example, the following arrangement satisfies the requirement:
1 0 13 3
7 2 9 10
11 5 4 14
12 15 6 8
This example can be trivially transformed into any of several other
examples by means of rotation, reflection, and EXCLUSIVEly ORing
each element with any single element. Assuming each of the results
is distinct (?), this means that the above array represents a set
of 128 arrays with the required property. But how many such sets
are there?
This led to Problem #5 on my Most Wanted list of unsolved problems,
summarized as follows:
In how many distinct ways can the integers 0 through 15
be arranged in a 4x4 array such that the bitwise OR over
each row, column, and diagonal is 15, and the bitwise
AND over each row, column, and diagonal is 0?
This question was first posted on the Internet in early 1993, but
was evidently just outside the range of a brute-force search on the
typical personal computer at that time.
In 1996, someone named Ian (ianm@tpower.com) sent the following
comments on a restricted version of this problem
Ian wrote:
Partial (very) solution. Using my trusty PC, if you look for
solutions that only meet the row constraint...I come up with
778339*24^5 solutions. How I came up with that number - there
are 30816=24*1284 valid combinations of 4 of 0..15 that meet the
AND/OR constraint. Here is the program I used...(Pascal). I am
trying to think of a reasonable way to tackle the entire problem.
This is a nice way of approaching the problem. In summary, Ian's
method is to examine each of the 1820 4-element subsets of {0,1,2,..,15}
to find the 1284 subsets with cumulative AND equal to 0 and cumulative
OR equal to 15. Each of these subsets represents a valid row. Then
he finds all combinations of four subsets that are mutually exclusive
(because no number can appear in more than one row). We find 778339
such combinations. Of course, within each row any of the 4! arrangements
is equally valid, so there are (4!)^4 distinct ways of arranging the
four numbers in the four rows. Furthermore, any of the 4! permutations
of the rows themselves is equally valid, so we arrive at the result
778339*(24)^5 = 6,197,620,801,536
Ian's method of checking the combinations of valid rows is to express
each of the 1284 valid four-number subsets as a 16-bit binary number
containing four 1's (corresponding to the four numbers in the subset).
He then applied a four-nested loop on the 1284 numbers to construct
the four-combinations and check that the pair-wise ANDs are zero. Of
course if we had to check all 10^11 sets of four out of 1284 it would
take quite a while. However, it turns out the pairwise exclusivity
conditions effectively truncate the loops with relatively little wasted
running. (On my old 33 MHz 486 PC it takes about 13 minutes.)
It's worth noting that if you arrange the 1284 valid combinations in
lexigraphical order, i.e., with the order given by the loops
for a=0 to 15
for b=a+1 to 15
for c=b+1 to 15
for d=c+1 to 15
it turns out that all the valid combinations of four have indicies
in the ranges shown below
1st index 1 321
2nd index 322 980
3rd index 594 1240
4th index 808 1284
Also, for any given 1st index, the number of valid combinations is
one of just 13 values, as summarized in the table below:
# of 1st indicies
having exactly
q valid
combinations q (#)*(q)
---------------- ------ --------
4 1997 7988
24 2049 49176
48 2205 105840
48 2287 109776
48 2425 116400
24 2440 58560
24 2481 59544
24 2520 60480
16 2648 42368
48 2703 129744
6 2904 17424
3 2973 8919
4 3030 12120
-------- --------
321 778339
This seems to suggest that there might be a combinatorial way of
determining these numbers, or perhaps the corresponding numbers
for some other arrangement of the 1284 valid combinations.
Another interesting aspect of Ian's result is the comparison
with a "probabilistic" estimate for the solution of the complete
quarto problem. I once wrote a little program to generate random
permutations of the numbers 0 through 15 and check to see if they
were quarto squares. Based on this analysis it appears that about
1 out of every 50.52 squares is a quarto square, so the total number
of distinct quarto squares is about (16!)/50.52 = 4.14E+11. This
is roughly 1/15 of 778339*(24)^5 which, as Ian has shown, is the
number of squares that satisfy the quarto conditions in just one
direction (e.g., for the rows).
Anyway, toward the end of 1996 there was in sharp increase in
activity on the unrestricted question, as several people sensed that
a direct search was just feasible on a high-speed Pentium computer.
Finally, Steve Zook wrote a counting program and determined that the
number in question is
414298141056
Steve's program used a simple depth-first search algorithm to count
by complete enumeration the quarto draws having a zero in the upper
left cell, knowing that each of those corresponds to 16 distinct
quarto draws by performing an exclusive-OR of each cell's contents
with a constant from 0 to 15. To optimize pruning he assigned the
cell contents in the order shown below
0 1 2 3
4 9 7 10
5 8 12 13
6 11 15 14
This allows excluding non-draws as soon as possible. The result
of his count was 25,893,633,816. Multiplying this by 16 gives
the number 414298141056.
I also recieved other purported solutions to this problem, but
most of them were clearly wrong. To evaluate the few that were
in the right ballpark (like Steve's) I tried to find a relatively
efficient way of counting these "quarto draws" so that I could
verify which (if any) of them was correct.
The method I used was based on the observation that the set P of
all permutations can be partitioned into 16 equally-sized subsets,
each of which consists of the elements of P that are equivalent up
to XORing by a constant. Furthermore, each of those 16 subsets can
be partitioned into 24 equally-sized subsets, each consisting of the
elements that are equivalent up to a permutation of the binary bits.
Thus, we have a 384-to-1 mapping of the elements of P onto the
elements of the set B, where B is the set of permutations with "0"
in the upper left corner and with the numbers "1", "2", "4", and "8"
appearing in ascending order. On this basis we need to examine only
the 16!/384 = 54486432000 elements of B. If q denotes the number of
quarto draws in B then Q = 384*q is the total number of quarto
draws in P.
We can reduce the problem further by considering the 1365 possible
placements of the numbers 1,2,4,8 in ascending order (with 0 in the
upper left). Notice that if we "flip" the square about the diagonal
through 0, the number of quarto draws for the new arrangement will
be identical to the original. Thus, if flipping the square yields
a distinct arrangement (up to permutations of the binary bits), we
need only count the solutions for one of the arrangements, and
double it.
In addition, notice that for any placement of 1,2,4,8 if we exchange
the middle two rows and then exchange the middle two columns, the
number of quarto draws for the new arrangement will be identical to
the original. This is the only one of the 24 possible permutations
of the rows/columns that leaves fixed the upper left corner and all
the contents of the rows, columns, and diagonals.
Therefore, my overall approach is to scan through the 1365 placements
of 1,2,4,8 in ascending order, with 0 in the upper left, and look at
all four of the equivalent arrangements given by flipping about the 0
diagonal and exchanging the two middle rows/columns. In most cases
this gives four distinct placements, but in some cases it gives only
two (because of symmetry), and in a few cases it gives only one. If
any of these four equivalent arrangements has already been examined,
I discard it and go on to the next. If none of them have been seen
before, I check for quarto draws and multiply the result by the
number of distinct but equivalent placements (usually four).
Of course, some of the 1365 placements can be seen to contain
zero quarto draws because the number 0,1,2,4,8 already constitute
a row, column, or diagonal that violates the quarto draw condition.
It turns out that 36 of the 1365 placements can be immediately
discounted out on that basis. (These 36 are composed of four sets
of two equivalent placements, and seven sets of four equivalent
placements.)
Of the remaining placements we find that 312 give four equivalent
but distinct placements, 38 give two, and 5 give only one. So,
the totals are
(312)*4 = 1248
(38)*2 = 76
(5)*1 = 5
nulls = 36 = (4)*2 + (7)*4
----
Total 1365
This means we only need to check 355 placements, each of which
represents 11! = 39916800 cases, so overall we need to check
exactly 14170464000 (about 14 billion) individual 4x4 squares.
With a straight-forward implementation on a 200 MHz Pentium computer
this takes about 9 hours. The result is that the set B contains
exactly 1078901409 quarto draws, which means the overall set P of
all possible permutations contains 414298141056 quarto draws.
This means that 1 out of 50.5017711 permutations is a quarto draw,
in good agreement with Monte Carlo simulations that count the
number of quarto draws in a large number of randomly constructed
permutations.
By the way, the five placements that are invariant under the flipping
and middle row/colums exchange operations are illustrated below
0 * * - 0 - - * 0 - - * 0 - - - 0 - - -
* - - - - * - - - - * - - * * - - - - *
* - - - - - * - - * - - - * * - - - - *
- - - - * - - - * - - - - - - - - * * -
The asterisks denote the locations of the numbers 1,2,4,8 (in
ascending order) and the dashes represent the remaining 11
numbers. The numbers of quarto draws contained in these five
placements are, respectively,
201599 prime
347496 (2^3)(3)(14479)
2344528 (2^4)(23^2)(277)
935024 (2^4)(58439)
2686796 (2^2)(7)(95957)
These five are special cases because of their symmetry. Most of
the placements give four distinct equivalent placements under the
flipping and row/column exchange operations. For example, the
four placements shown below are equivalent
0 * * - 0 * - - 0 * * - 0 - * -
* * - - * * - - - - - - * - - -
- - - - * - - - * - * - * - * -
- - - - - - - - - - - - - - - -
Each of these four placements contains 169560 = (2^3)(3^3)(5)(157)
quarto draws.
The question about Quarto draws was based on the understanding
that a "winning" configuration is one containing four pegs all
with a common property in any row, column, or main diagonal. This
is how I understood the rules of the game Quarto, having heard a
brief description of the game in 1992. Alternatively, we could ask
for the number of draws if ALL of the diagonals are considered,
i.e., interpreting the square as a torus that wraps around the
edges, or we could consider the case involving ONLY the rows and
columns, with no diagonals at all.
Out of curiosity I recently did a web search on the game Quarto
to find out the precise definition of the rules. The only
definition I can find is one that says a "win" involves any four
cells IN A ROW OR A SQUARE. I suppose this means, for example,
the four corner cells would count, as would the four middle cells,
and so on. There are nine + four + one = 14 sets of four cells
arranged in a square pattern orthogonal with the sides of the
board. If we treat the array as a torus, the number of distinct
orthogonal square arrangements is 20. As for the phrase "IN A ROW",
I assume this also includes the (main?) diagonals along with the
rows and columns.
The following is a summary of some computed results on the number
of distinct Quarto draws based on various interpretations of the
rules. The terms "maindiags" and "alldiags" refer to the sets of
four diagonal cells based on a single bounded array or a torus,
respectively. Likewise the terms "mainsqrs" and "allsqrs" refer to
sets of four cells in a square pattern based on a single bounded
array or a torus, respectively.
factorization
OR=15, AND=0 number of number/384
--------------------------- ------------- ------------------
rows+cols 1329371360640 (3^2)(5)(76931213)
rows+cols+maindiags 414298141056 (3)(359633803)
rows+cols+alldiags 85842854016 (17)(197)(66751)
rows+cols+mainsqrs 35347120896 (2)(19)(59)(41057)
rows+cols+mainsqrs+maindiags 18596841216 (2)(173)(139969)
rows+cols+mainsqrs+alldiags 7376330496 (2)(29)(227)(1459)
rows+cols+allsqrs 7031789952 (11)(19)(41)(2137)
rows+cols+allsqrs+maindiags 4031409024 (3)(499)(7013)
rows+cols+allsqrs+alldiags 2522431872 (3)(383)(5717)
With the exception of the rows+cols+maindiags, these results have not
been checked. Also, I've not considered square arrangements that
are oblique to the sides of the board.
Return to MathPages Main Menu