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


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

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

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.

   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