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:
- The checkerboard is for aid in orienting only; black and white are the
same.
- The two players may each have a full complement of 12 pentominos, or they may
"choose up" their half of one set.
- Players alternate placing pentominos on the board. Pentominos must not
overlap.
- 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:
- captures must be made, although you can choose which capture to make
- pawns must be promoted to queens
- king is just another piece
- 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