Beeler, M., Gosper, R.W., and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb. 29, 1972. Retyped and converted to html ('Web browser format) by Henry Baker, April, 1995.

PROPOSED COMPUTER PROGRAMS, IN ORDER OF INCREASING RUNNING TIME (Schroeppel)

Previous Up Next

PROBLEM 77:

Count the polyominos up to, say, order 20. From Applied Combinatorial Mathematics, pages 201 and 213:
ORDER   E. H.   NOT ENCLOSING HOLES
1       1       1
2       1       1
3       2       2
4       5       5
5       12      12
6       35      35
7       108     107
8       369     363
9       1285    1248
10      4655    4271
11      17073
12      63600
13      238591
14      901971
15      3426576
16      13079255
17      50107911
18      192622052
The order 13 through 18 data is from Computers in Number Theory, 1971, Atkin & Birch, ed., Academic Press, which has not been independently checked. It also gives bounds 3.72 < limit as N goes to infinity of Nth root of number of polyominos of order N (including those enclosing holes) < 4.5. Also an asymptotic formula for the number of polyominos:

    N     -.98+-.02
4.06  * (N         ) * constant.
Polyominos may be constructed in 3-space (Soma-like) pieces) or higher dimensions; a curious thought is into how many dimensions does the average, say, 20-omino extend?

PROBLEM 78:

Solve "minichess", chess played on a 5 x 5 board where each side has lost the king's rook, knight, bishop, and 3 pawns, and the opponents are shoved closer together (1 empty row intervening, no double pawn moves).

PROBLEM 79:

Solve the tiger puzzle, a sliding block puzzle mentioned in Scientific American February 1964, pages 122-130.

PROBLEM 80:

Find smallest squared square (a square composed entirely of smaller, unequal squares). Smallest known has 24 small squares (Martin Gardner's Scientific American Book, vol. 2, page 206). See also the following two illustrations. Recently, someone constructed a squared rectangle with sides in the ratio 1:2. It contains 1353 squares.

Figure 3(a). The smallest known (in 1961, and yet today as far as we know) squared square. Reprinted by special permission from Martin Gardner, The Second Scientific American Book of Mathematical Puzzles and Diversions, 1961, Simon and Schuster, New York, New York.

Figure 3(b). A squared rectangle found by Schroeppel using "String Handling Interpretive Translator", a string processing language written by Samson. Sides are 884808 = 2^3 * 3^2 * 12289 and 752225 = 5^2 * 30089; semiperimeter is 1637033 = 419 * 3907. this has 28 squares, which is more than most published squared rectangles.

PROBLEM 81:

Count the magic squares of order 5. There are about 320 million, not counting rotations and reflections.

PROBLEM 82:

List (that is, count) the semigroups of 7 elements; also, the groups of 256 elements (estimated: 11000).

PROBLEM 83 (Gosper):

Compute the integer-valued step function F(R), 0<R<1, the number of circles of radius R which fit into a unit circle. F skips the value 6, and probably 18. How many and how big are the gaps in the range of F? What happens in n dimensions (including n = infinity)?

PROBLEM 84:

Solve pentominos on an 8 x 8 checkerboard game(s).

Rules:

  1. The checkerboard is for aid in orienting only; black and white are the same.
  2. The two players may each have a full complement of 12 pentominos, or they may "choose up" their half of one set.
  3. Players alternate placing pentominos on the board. Pentominos must not overlap.
  4. The last player to place a pentomino wins.

PROBLEM 85:

With regard to dissection theorems, the following are known: a triangle into a square, 4 pieces (proven minimal); a pentagon into a square, 6 pieces (best known) etc. ("Geometric Dissections" by Harry Lindgreen, Scientific American November 1961). A program can probably check the known dissections for minimality! See following illustration, for example.

Figure 4. A surprising square <--> hexagon dissection, adapted from page 164 of the November, 1961 issue of Scientific American, which see for further diagrams and discussion.

PROBLEM 86:

Find the number of domino coverings for various objects. for example, an asymptotic formula is known for rectangles; also, on a square board, if side mod 4 = 0, coverings appears to be a square; on a square board, if side mode 4 = 2, coverings appears to be twice a square. See Applied Comb. Math., chap. 4.4-4.6, p. 105-121. Article by E. W. Montroll.

PROBLEM 87:

Analyze giveaway chess, which is as follows:
  1. captures must be made, although you can choose which capture to make
  2. pawns must be promoted to queens
  3. king is just another piece
  4. player to give away all pieces first wins

PROBLEM 88:

Analyze "escalation chess", where white gets 1 move, black 2, white 3, etc. If a player is in check, he must get out of check on his first move. He may not move into check. Taking your opponent's king is verboten, but you can pile up triple checks, etc. A player is checkmated if he can't get his king out of check on his first move.

PROBLEM 89:

In the game "4 pawns", black has 4 pawns, a king, and two moves to white's one. Prove the pawns win. The object in this game is to capture the king. Black is allowed to move through check.

PROBLEM 90:

Solve Scarne's game, "Teeko", which is played on a 5 x 5 board by two players who alternate placing, one at a time, their 4 counters each, after which the counters are moved around (including diagonally). 4 in a row or square wins.

PROBLEM 91:

Solve "five-in-a-row" on an infinite board.

PROBLEM 92:

Solve Tic-Tac-Toe on a 4 x 4 x 4 board. The consensus is a win for the first player, but it's unproven. The first player wins on 4 x 4 x 4 x 4.

PROBLEM 93:

Solve checkers. There are about 10^12 positions. (Computing time currently estimated (Schroeppel) at 1 year).

Programs below this line are considered unfeasible.

PROBLEM 94:

Solve Hex on large boards (11 to 23 on a side); through order 7 have been analyzed by hand. There is a proof that in games where having an extra move can never (repeat: never) hurt you, the worst the first player can be forced to do is draw. Thus, with Hex, in which there is no draw, the first player can always win.

PROBLEM 95:

Solve chess. There are about 10^40 possible positions; in most of them, one side is hopelessly lost.

PROBLEM 96:

Solve Go. About 10^170 positions.

Previous Up Next