+ glhanoi->currentDisk = pop(glhanoi, glhanoi->src);
+ moveSetup(glhanoi, glhanoi->currentDisk);
+ push(glhanoi, glhanoi->dst, glhanoi->currentDisk);
+
+ fudge = fudge % 2;
+
+ if(fudge == 1 || magicNumber) {
+ swap(&glhanoi->src, &glhanoi->tmp);
+ }
+ if(fudge == 0 || glhanoi->magicNumber) {
+ swap(&glhanoi->dst, &glhanoi->tmp);
+ }
+ glhanoi->magicNumber = magicNumber;
+ } else {
+ SubProblem sp;
+ int tmp = 0;
+
+ if (glhanoi->move == 0) {
+ /* Initialize the solution stack. Original problem:
+ move all disks from pole 0 to furthest pole,
+ using all other poles. */
+ pushMove(glhanoi, glhanoi->numberOfDisks, 0,
+ glhanoi->numberOfPoles - 1,
+ REMOVE_BIT(REMOVE_BIT(ALL_POLES, 0), glhanoi->numberOfPoles - 1));
+ }
+
+ while (!solveStackEmpty(glhanoi)) {
+ int k, numAvail;
+ sp = *popMove(glhanoi);
+
+ if (sp.nDisks == 1) {
+ /* We have a single, concrete move to do. */
+ /* moveSetup uses glhanoi->src, dst. */
+ glhanoi->src = sp.src;
+ glhanoi->dst = sp.dst;
+ glhanoi->tmp = tmp; /* Probably unnecessary */
+
+ glhanoi->currentDisk = pop(glhanoi, sp.src);
+ moveSetup(glhanoi, glhanoi->currentDisk);
+ push(glhanoi, sp.dst, glhanoi->currentDisk);
+
+ return;
+ } else {
+ /* Divide and conquer, using Frame-Stewart algorithm, until we get to base case */
+ if (sp.nDisks == 1) break;
+
+ numAvail = numBits(sp.available);
+ if (numAvail < 2) k = sp.nDisks - 1;
+ else if(numAvail >= sp.nDisks - 2) k = 1;
+ /* heuristic for optimal k: sqrt(2n) (see http://www.cs.wm.edu/~pkstoc/boca.pdf) */
+ else k = (int)(sqrt(2 * sp.nDisks));
+
+ if (k >= sp.nDisks) k = sp.nDisks - 1;
+ else if (k < 1) k = 1;
+
+ tmp = bitScan(sp.available);
+ /* fprintf(stderr, "Debug: k is %d, tmp is %d\n", k, tmp); */
+ if (tmp == -1) {
+ fprintf(stderr, "Error: n > 1 (%d) and no poles available\n",
+ sp.nDisks);
+ }
+
+ /* Push on moves in reverse order, since this is a stack. */
+ pushMove(glhanoi, k, tmp, sp.dst,
+ REMOVE_BIT(ADD_BIT(sp.available, sp.src), tmp));
+ pushMove(glhanoi, sp.nDisks - k, sp.src, sp.dst,
+ REMOVE_BIT(sp.available, tmp));
+ pushMove(glhanoi, k, sp.src, tmp,
+ REMOVE_BIT(ADD_BIT(sp.available, sp.dst), tmp));
+
+ /* Repeat until we've found a move we can make. */
+ }
+ }