/*********************************************************************** William Keister (1907-1997) was a pioneer in switching theory and design at Bell Labs. When he retired in 1972, he was director of Bell Labs' Computing Technology Center at Holmdel, New Jersey. Mr. Keister's interest in puzzles began as a boy in Montgomery, Alabama, where he designed puzzles when he wasn't busy building crystal radio sets and writing poetry. In the late 1930s and 40s, when engineers were only beginning to appreciate the logic that would later form the basis of computers, Mr. Keister began to look at logic puzzles and how they could be solved through formal design methods. "At the time," he says, "we knew that computing machines could add, multiply, and divide, but it was not so apparent that they could be programmed to perform logic." Mr. Keister began working in his spare time to prove that puzzles could be solved through logic design. One day he raided Bell Labs' stock room, gathering up pushbuttons, electronic relays, and light bulbs to build an electronic version of the Chinese Ring Puzzle. After a few hours work, he realized he had wired it up wrong, but studying what he had done he also realized that he had stumbled onto a whole series of binary code sequence puzzles, of which the famous Chinese Ring Puzzle was just one variation. He went on to sketch out a whole series of logic puzzles and show how they could be solved mathematically with Boolean algebra, a precursor to today's computer languages. http://www.puzzles.com/products/ElephantSpinOut/ElephantInventor.htm References: Chinese Rings - Baguenaudier - Brain Puzzler - Spin Out - W. Ahrens; Mathematische Unterhaltungen und Spiele, Band I, 2. Auflage, B. G. Teubner Leipzig, 1909 Chapter III.3.VI Der Baguenaudier p61-72 Recusion: c(n) = c(n-1) + 2c(n-2) + 1, c(1) = 1, c(2) = 2 or 1 depending if you want to count the dropping of the first two rings together as two moves or not. - W. W. Rouse Ball, H. S. M. Coxeter; Mathematical Recreations and Essays, 11th Edition, 1939 Chapter XI.3 Chinese Rings p307-310 c(n) = (2^(n+1)-1)/3 for n odd and c(n) = (2^(n+1)-2)/3 for n even. - Elwyn R. Berlekamp, John H. Conway, Richard K. Guy; Winning Ways Volume two, Academic Press (1982) pages 750-753 - A. K. Dewdney; Computer Recreations: Yin and yang: recursion and iteration, the Tower of Hanoi and the Chinese rings, Sci. Amer. 251 (1984), no. 5 (November), 19-28. Reprinted, with Addendum, in The Armchair Universe: An Exploration of Computer Worlds, W. H. Freeman and Co., New York, 1988, pp. 186-199. - Leroy J. Dickey; Grey codes, towers of Hanoi, Hamiltonian paths on the N-cube, and Chinese rings, APL Quote Quad 24 (1993), no. 2 (December), 18-24. - V. Dubrovsky; Nesting Puzzles, Part II: Chinese Rings Produce a Chinese Monster, Quantum 6 (Mar 1996) 61-65 and (Apr 1996) 58-59 - H. E. Dudeney; Amusements in Mathematics, Nelson 1917 (reprint: Dover Publ. 1958) Problem 417: The Tiring Irons (chinese rings) p142-143, 247-248 - What is the position after the 9999th move in the n=14 game? - Martin Gardner; Knotted Doughnuts and other Mathematical Entertainments, Freeman and Company, New York, 1986. Chapter 2: The Binary Gray Code p11-27 - Jaap's Puzzle Page; http://www.org2.com/jaap/puzzles/ Spinout / The Brain / Chinese Rings - Louis H. Kauffman; Tangle complexity and the topology of the Chinese rings. Mesirov, Jill P. (ed.) et al., Mathematical approaches to biomolecular structure and dynamics. Proceedings of the 1994 IMA summer program on molecular biology. New York, NY: Springer. IMA Vol. Math. Appl. 82, 1-10 (1996). Zbl 862.05028 - William Keister; U.S. Patent 3637215 (1972) SpinOut U.S. Patent 3637216 (1972) The Hexadecimal Puzzle - Donald E. Knuth; The Art of Computer Programming, (Pre-Fascicle 2a 2002) Section 7.2.1.1: Generating all n-tuples - M. Kraitchik; Mathematical recreations, p 89-91 - Edouard Lucas; Recreations Mathematiques, four volumes, Paris, 1891-1894. (reprinted A Blanchard, Paris, 1960) (1883) Vol 1, Part 7: Le Jeu du Baguenaudier - Jozef Przytycki, Adam S. Sikora; Topological Insights from the Chinese Rings, preprint 1999 http://gwis2.circ.gwu.edu/~przytyck/publications/ - Jean-Bernard Roux; Un casse-tete pour voyageur de commerce, http://hypo.ge-dip.etat-ge.ch/www/math/html/node41.html - baguenaudier, Spin-out, code de Gros-Grey, Keister - Jan de Ruiter; The Quattro Puzzle, CFF 40, p12-15 - G. C. Shephard; The mathematics of a mechanical puzzle, The Mathematical Gazette, 61 (1977) 174-178 - N. J. A. Sloane, S. Plouffe; The Encyclopedia of Integer Sequences, Academic Press, (1995) http://www.research.att.com/~njas/sequences/ sequence A000975 : 0,1,2,5,10,21,42,85,170,341,682 - MagNif Brain Puzzler Prod. #2225 (The Brain) http://magnif.com/puzzles.htm Sequence: 0,1,2,5,10,21,42,85,170,341,682 Recurences: (1) c(2n) = 2 c(2n-1), c(2n+1) = 2 c(2n) + 1, c(0) = 0 (2) c(n) = c(n-1) + 2c(n-2) + 1, c(1) = 1, c(2) = 2 Generating Function: GF(x) = x/((1-x)(1-x-2x^2)) = x/((1-2x)(1-x^2)). -- http://www.mathematik.uni-bielefeld.de/~sillke/ mailto:Torsten.Sillke@uni-bielefeld.de ***********************************************************************/ #include #include #include #include const int LEN = 16; char pattern[] = "10000000000000000000000000000000"; int hex (const char* v, const char* w, const int len, const int out) { char dv[LEN+1]; char dw[LEN+1]; int i, d=0, m=0; bool equal = true; for (i=len-1;i>=0;i--) { if (equal) { dv[i] = v[i]; dw[i] = w[i]; equal = v[i] == w[i]; } else { // fill in the pattern. dv[i] = dw[i] = pattern[d++]; } } dv[len] = dw[len] = 0; if (equal) { if (out==1) cout << v << endl; } else { // Precondition: d(v,dv) < d(v,w) and d(dw,w) < d(v,w) // with d(a,b) = max({ i | a[i] != b[i] }). int mv = hex(v,dv,len,out); // One Move to go from dv to dw. if (out==1) cout << setw(d+1) << "|" << endl; if (out==2) cout << "0123456789abcdef"[d]; int mw = hex(dw,w,len,out); m = mv + mw + 1; } return m; } void usage (ostream & os = cout) { os << "Usage: Hexadecimal Puzzle\n" << " Shows the moves to get to position\n" << " given a . The default pattern is 10*\n" << " which gives the Chinese rings (Spin-Out).\n" << " The Hexadecimal Puzzle was invented by William Keister (1907-1997).\n" << "\n" << "Arguments: \n" << " [ []]\n" << "\n" << " The output option Out comes in three forms.\n" << " Out=0 counts the number of moves only.\n" << " Out=1 is a long output giving each move. (default)\n" << " Out=2 shows the sequence of moves. \n" << endl; } int main (int ac, char** av) { char v[LEN+1], w[LEN+1]; int len, m, out=1; if (ac <= 2) { usage(); return 1; } strncpy(v, av[1], LEN); strncpy(w, av[2], LEN); if (ac > 3) { strncpy(pattern, av[3], LEN); len = strlen(pattern); for (m = len; m < LEN; m++) pattern[m] = '0'; } if (ac > 4) out = atoi(av[4]); v[LEN] = 0; w[LEN] = 0; len = strlen(v); if (strlen(w) != len) { cout << "Start and End must have equal length." << endl; return 1; } m = hex (v,w,len,out); cout << "Moves " << m << '\n'; return 0; }