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