text:
Use NVM to tenaciously resume operation whenever aborted
Summary
The aim of this challenge is to write a tenacious program. This is a stateful program designed to output a given string, but for which, if the program is aborted at any point during the writing of the string, rerunning the program will continue where it left off, writing only the characters that have not been written so far.
Specifically, the goal of this challenge is to output the string 01 using a tenacious program.
Background
I once conjectured that with n cits, any string up to length 2(n-k) could be ouptut by a tenacious program, for some small fixed k. I'm now leaning toward thinking the goal can't be achieved :-(
This challenge, therefore, was designed to determine whether tenacious programs that output nontrivial strings are possible. 01 appears to be the shortest nontrivial goal string, and so is the subject of this challenge.
Current status: So far there are no correct answers, but it has been proven that 2 cits are not enough.
Data storage
In order to store information across multiple runs of the program, you have access to a number of cits, bits made out of non-volatile memory; these are persistent, stateful bits that can have the value 0, 1, or undefined. They have the value 0 before the first execution of the program. If the program is aborted midway through writing a cit, that cit's value becomes undefined (unless the value being written to the cit was the value previously stored there), and will remain undefined until the program writes a 0 to the cit (and is not aborted midway through the write). Reading an undefined cit will (unpredictably) produce 0 or 1 (maybe different for each read), and your program must function correctly regardless of what values are read from undefined cits.
Each cit used by your program has a distinct address, which is an integer (you may choose how many cits are used, and what their addresses are). In order to read and write from the cits, you may assume that you have access to two functions: a function that takes a constant integer (representing the address of a cit), and returns a value read from that cit; and a function that takes an integer (representing the address of a cit) and a boolean (representing the value of a cit), and writes the value to the cit. These functions are guaranteed return in finite time (unless the program is aborted while they are running).
You may choose the names of this functions as appropriate for the language you are using. If the language uses identifiers as function names, the recommended names are r to read, w to write.
Output
Due to the possibility that the program will be aborted during output, output from this challenge works a little differently from normal. Output may only be done a character at a time. You have access to a function that produces output in the following way: its argument is 0, 1, 2, or 3; if the given argument is the same as the argument to the previous call of the function (even in a previous execution of the program), or is 0 and no output has ever been produced, then the function does nothing. Otherwise, it outputs 0 if given an argument of 0 or 2, or 1 if given an argument of 1 or 3.
You may choose the name of this function as appropriate for the language you are using. If the language uses identifiers as function names, the recommended name is p.
Requirements
Write a program with the following properties:

The only state used by the program between runs is a number of cits (as defined above); all other storage used by the program must be initialised to a fixed value at the start of each run.
The program will terminate in finite time, unless aborted.
If all the cits used by the program start with value 0, and then the program is run, aborted after an arbitrary length of time (which could occur at any moment during the program's execution, even while writing a cit or writing output), run again, aborted after another arbitrary length of time, and this process is repeated until the program terminates naturally, then (no matter what timing was used for the aborts) the combined output from all the program executions will be 01.
The program is single-threaded, making no use of parallelism or concurrency (this is required for the abort behaviour to be well-defined).

(More generally, a "tenacious program" is any program with the properties above, with 01 replaced with any arbitrary string. But this challenge is just about writing a tenacious program to output 01.)
Alternatively, a proof that such a program is impossible is also considered a valid submission to this challenge.
You may alternatively write a function instead of a program, but it is only allowed to store state between calls via using cits; it cannot look at any of the state of the program that called it.
Example
Here's an example of a C program that fails to solve the challenge:
// uses one cit with address 3
#include "hal.h"            // assumed to define r(), w(), p()
int main(void) {            // entry point, no parameters or input
    if (r(3)==0)            // cit 3 read as 0, that is state 0 or undefined
        w(3,0),             // write 0 to cit 3, to ensure it's defined
        p(2);               // put 2 with output '0' initially
    w(3,1),                 // mark we have output '0'
    p(1);                   // put 1 with output '1'
}                           // halt

To see why this doesn't work, imagine that the first run of the program is aborted during w(3,1): this outputs 0, and causes cit 3 to become undefined. Then imagine that the second run happens to read the undefined cit as 1, and is aborted after p(1) completes (but before the program ends); at this point, the output is 01. The cit is still undefined, because writing 1 to an undefined cit does not define it (only writing 0 can define it). A third run of the program might now happen to read the undefined cit as 0, thus causing 0 and 1 to be output again. This produces the output 0101, which is not 01.
Checking the validity of your solution
@hammar has written a checker that determines whether a given solution is valid (and/or explains why a particular solution isn't valid). To check your own solutions, or to see how it works, you can Try it online!.
Victory condition
The program that achieves the requirements above using the fewest cits wins. In the case of a tie, programs which make fewer writes to cits per program execution are considered better (with the worst case more important than the best case); if there is still a tie, the shortest program (not counting the declarations of the provided functions) wins.

I feel like a similar question was asked - perhaps relating more to flash memory/power surges, I think - but I can't seem to find it.

@Gaffi: I made a question two weeks ago asking a program with similar properties for decimals of Pi-3 in binary to the maximum possible length given a number of cits, and other stuff, worded with power cut rather than abort. It was met with (positive) criticism asking how one would determine valid answers. I realized that likely I could not, and removed the question. With this meticulously worded code-golf, I'm confident that I can check the program, or post a shorter tenacious one, for many languages. My only regret is that I should have made the goal a tad more sexy.

Are you sure you want this to be code golf? It seems to me that the challenge is in writing such a program at all (and proving its correctness); once that's accomplished, golfing it becomes a fairly trivial exercise (and somewhat ill-defined, given that we're allowed to adapt the interface). Maybe just make it [tag:code-challenge] instead?

Another question: would proving the impossibility of non-trivial tenacious programs count as a solution? (I don't have such a proof yet, but I'm starting to think that may be the case.)

@IlmariKaronen: Proof of impossibility would be king! I have posted a solution that may be valid. See for yourself.

I'm working on a proof that any working solution must pass through a state with at least two Us.

I doubt I can come up with a proof in 11 hours (if at all), so I'd say hammar deserves the bounty for his test harness.  (Ps. My proof strategy has been to try to show that all the cits can be forced into state 0 or U after the program has halted once. I keep running into gaps, though.)

This challenge feels like someone is trying to get PCG to write their research paper :)

@Lie Ryan: This actually is from an engineer that was pissed off by the supplier of some Smart Card IC with NVM insisting that there was no way, and no reason, to physically write again in a memory cell that does not read zero. I wanted to find a way to live with this restriction, if any, and invented that (genuinely hoping there was a solution, which I now doubt). In the end I managed to convince the vendor that such write was possible and desirable, removing the Charging a non-discharged cit is inhibited constraint, and life/engineering became much easier.

While I don't have a solution nor a proof of impossibility, I figured I'd post my test harness for anyone wanting to play around with this, as I've pretty much given up at this point.
It's an implementation of the HAL modelling programs as a Haskell monad. It checks for tenacity by doing a breadth-first search over the possible sessions to check for sessions which either 1. have halted once without producing the correct output, or 2. have produced an output that is not a prefix of the desired one (this also catches programs producing infinite output).
{-# LANGUAGE GADTs #-}

module HAL where

import Control.Monad
import Data.List

import Data.Map (Map)
import qualified Data.Map as Map

import Data.Set (Set)
import qualified Data.Set as Set

newtype CitIndex = Cit Int
  deriving (Eq, Ord, Show)

data CitState = Stable Int | Unstable
  deriving (Eq, Ord, Show)

data Program a where
  Return :: a -> Program a
  Bind :: Program a -> (a -> Program b) -> Program b
  Put :: Int -> Program ()
  Read :: CitIndex -> Program Int
  Write :: CitIndex -> Int -> Program ()
  Log :: String -> Program ()
  Halt :: Program ()

instance Monad Program where
  return = Return
  (>>=) = Bind

data Session = Session
  { cits :: Cits
  , output :: [Int]
  , lastPut :: Int
  , halted :: Bool
  } deriving (Eq, Ord, Show)

data Event
  = ReadE CitIndex Int
  | PutE Int
  | WriteSuccessE CitIndex Int
  | WriteAbortedE CitIndex Int
  | LogE String
  | HaltedE
  deriving (Eq, Ord, Show)

type Log = [(Event, Cits)]

check :: Program () -> Int -> [Int] -> IO ()
check program n goal =
  case tenacity (program >> Halt) goal of
    Tenacious  -> putStrLn "The program is tenacious."
    Invalid ss -> do
      putStrLn "The program is invalid. Example sequence:"
      forM_ (zip [1..] ss) $ \(i, (log, s)) -> do
        ruler
        putStrLn $ "Run #" ++ show i ++ ", Initial state: " ++ formatState n s
        ruler
        mapM_ (putStrLn . formatEvent n) log
  where ruler = putStrLn $ replicate 78 '='

run :: Program a -> Session -> [(Maybe a, Log, Session)]
run (Return x) s = [(Just x, [], s)]
run (Bind x f) s = do
  (r1, l1, s1) <- run x s
  case r1 of
    Just y  -> [(r2, l1 ++ l2, s2) | (r2, l2, s2) <- run (f y) s1]
    Nothing -> [(Nothing, l1, s1)]
run (Put x) s = [(Just (), [(PutE x, cits s)], s')]
  where s' | lastPut s /= x = s { lastPut = x, output = output s ++ [x `mod` 2] }
           | otherwise      = s
run (Read cit) s =
  case lookupCit cit (cits s) of
    Stable x -> [(Just x, [(ReadE cit x, cits s)], s)]
    Unstable -> [(Just x, [(ReadE cit x, cits s)], s) | x <- [0, 1]]
run (Write cit x) (s @ Session { cits = cits }) =
  [(Just (), [(WriteSuccessE cit x, completed)], s { cits = completed }),
   (Nothing, [(WriteAbortedE cit x, aborted  )], s { cits = aborted })]
  where state = lookupCit cit cits
        completed = updateCit cit newState cits
          where newState = case (x, state) of
                             (0, _)        -> Stable 0
                             (1, Unstable) -> Unstable
                             (1, Stable _) -> Stable 1

        aborted = updateCit cit newState cits
          where newState = case (x, state) of
                             (0, Stable 0) -> Stable 0
                             (0, _)        -> Unstable
                             (1, Stable 1) -> Stable 1
                             (1, _)        -> Unstable
run (Halt) s = [(Just (), [(HaltedE, cits s)], s { halted = True })]
run (Log msg) s = [(Just (), [(LogE msg, cits s)], s)]

newSession :: Session
newSession = Session
  { cits = initialCits
  , output = []
  , lastPut = 0
  , halted = False }

newtype Cits = Cits (Map CitIndex CitState)
  deriving (Eq, Ord, Show)

initialCits = Cits (Map.empty)

lookupCit :: CitIndex -> Cits -> CitState
lookupCit cit (Cits m) = Map.findWithDefault (Stable 0) cit m

updateCit :: CitIndex -> CitState -> Cits -> Cits
updateCit index (Stable 0) (Cits m) = Cits $ Map.delete index m
updateCit index newState (Cits m) = Cits $ Map.insert index newState m

data Tenacity = Tenacious | Invalid [(Log, Session)]
  deriving (Eq, Ord, Show)

tenacity :: Program () -> [Int] -> Tenacity
tenacity program goal = bfs Set.empty [(newSession, [])]
  where
    bfs :: Set Session -> [(Session, [(Log, Session)])] -> Tenacity
    bfs visited [] = Tenacious
    bfs visited ((s, pred) : ss)
      | Set.member s visited = bfs visited ss
      | valid s   = bfs (Set.insert s visited) $ ss ++ [(s', (l, s) : pred) | (_, l, s') <- run program s]
      | otherwise = Invalid $ reverse (([], s) : pred)

    valid :: Session -> Bool
    valid Session { output = output, halted = halted }
      | halted    = output == goal
      | otherwise = output `isPrefixOf` goal

formatState :: Int -> Session -> String
formatState n s = "[cits: " ++ dumpCits n (cits s) ++ "] [output: " ++ dumpOutput s ++ "]"

formatEvent :: Int -> (Event, Cits) -> String
formatEvent n (event, cits) = pad (78 - n) text ++ dumpCits n cits
  where text = case event of
                 ReadE (Cit i) x         -> "read " ++ show x ++ " from cit #" ++ show i
                 PutE x                  -> "put " ++ show x
                 WriteSuccessE (Cit i) x -> "wrote " ++ show x ++ " to cit #" ++ show i
                 WriteAbortedE (Cit i) x -> "aborted while writing " ++ show x ++ " to cit #" ++ show i
                 LogE msg                -> msg
                 HaltedE                 -> "halted"

dumpCits :: Int -> Cits -> String
dumpCits n cits = concat [format $ lookupCit (Cit i) cits | i <- [0..n-1]]
  where format (Stable i) = show i
        format (Unstable) = "U"

dumpOutput :: Session -> String
dumpOutput s = concatMap show (output s) ++ " (" ++ show (lastPut s) ++ ")"

pad :: Int -> String -> String
pad n s = take n $ s ++ repeat ' '

Here is the example program given by the OP converted to Haskell.
import Control.Monad (when)

import HAL

-- 3 cits, goal is 01
main = check example 3 [0, 1]

example = do
  c <- Read (Cit 2)
  d <- Read (Cit c)
  when (0 == c) $ do
    Log "in first branch"
    Write (Cit 2) 0
    Write (Cit 1) 0
    Write (Cit 1) (1 - d)
    Write (Cit 2) 1
  Write (Cit 0) 0
  when (d == c) $ do
    Log "in second branch"
    Put 2
    Write (Cit 2) 0
  Write (Cit 0) 1
  Put 1

And here is the corresponding output, showing that the program is not tenacious.
The program is invalid. Example sequence:
==============================================================================
Run #1, Initial state: [cits: 000] [output:  (0)]
==============================================================================
read 0 from cit #2                                                         000
read 0 from cit #0                                                         000
in first branch                                                            000
wrote 0 to cit #2                                                          000
wrote 0 to cit #1                                                          000
wrote 1 to cit #1                                                          010
wrote 1 to cit #2                                                          011
wrote 0 to cit #0                                                          011
in second branch                                                           011
put 2                                                                      011
wrote 0 to cit #2                                                          010
wrote 1 to cit #0                                                          110
put 1                                                                      110
halted                                                                     110
==============================================================================
Run #2, Initial state: [cits: 110] [output: 01 (1)]
==============================================================================
read 0 from cit #2                                                         110
read 1 from cit #0                                                         110
in first branch                                                            110
wrote 0 to cit #2                                                          110
wrote 0 to cit #1                                                          100
wrote 0 to cit #1                                                          100
aborted while writing 1 to cit #2                                          10U
==============================================================================
Run #3, Initial state: [cits: 10U] [output: 01 (1)]
==============================================================================
read 1 from cit #2                                                         10U
read 0 from cit #1                                                         10U
wrote 0 to cit #0                                                          00U
aborted while writing 1 to cit #0                                          U0U
==============================================================================
Run #4, Initial state: [cits: U0U] [output: 01 (1)]
==============================================================================
read 0 from cit #2                                                         U0U
read 0 from cit #0                                                         U0U
in first branch                                                            U0U
wrote 0 to cit #2                                                          U00
wrote 0 to cit #1                                                          U00
wrote 1 to cit #1                                                          U10
wrote 1 to cit #2                                                          U11
wrote 0 to cit #0                                                          011
in second branch                                                           011
put 2                                                                      011
wrote 0 to cit #2                                                          010
wrote 1 to cit #0                                                          110
put 1                                                                      110
halted                                                                     110
==============================================================================
Run #5, Initial state: [cits: 110] [output: 0101 (1)]
==============================================================================

Unless someone can find a bug in this program, I think it checks and rejects every relevant two-cit program.
I argue that it suffices to consider programs which read all the cits and switch on a number formed by the set. Each branch of the switch will be a series of writes and puts. There's never any point putting the same number more than once in a branch, or putting the second output digit before the first one. (I'm morally certain that there's no point outputting the first digit other than at the start of a branch or the second digit other than at the end, but for now I'm avoiding that simplification).
Then each branch has a target set of cits it wants to set, and moves towards it by setting the bits it wants to be 0 as 0, and the bits it wants to be 1 as 0 then 1; these write operations can be ordered in various ways. There's no point setting a bit to 1 unless you've already set it to 0 in that run, or it's likely a nop.
It considers 13680577296 possible programs; it took a 4-core machine just under 7 hours to check them all without finding a single solution.
import java.util.*;

// State is encoded with two bits per cit and two bits for the output state.
//    ... [c_2=U][c_2=1/U][c_1=U][c_1=1/U][output_hi][output_lo]
// Output state must progress 0->1->2.
// Instruction (= program branch) is encoded with three or four bits per step.
//      The bottom two bits are the cit, or 0 for output/loop
//      If they're 0, the next two bits are 01 or 10 for output state, or 11 for halt.
//      Otherwise the next two bits are the value to write to the cit.
public class CitBruteForcer implements Runnable {

    static final int[] TRANSITION_OK = new int[]{
        // Index: write curr_hi curr_lo
        0,  // write 0 to 0 => 0
        0,  // write 0 to 1 => 0
        0,  // write 0 to U => 0
        -1, // invalid input
        1,  // write 1 to 0 => 1
        1,  // write 1 to 1 => 1
        2,  // write 1 to U => U
        -1  // invalid input
    };
    static final int[] TRANSITION_ABORT = new int[]{
        // Index: write curr_hi curr_lo
        0,  // write 0 to 0 => 0
        2,  // write 0 to 1 => U
        2,  // write 0 to U => U
        -1, // invalid input
        2,  // write 1 to 0 => U
        1,  // write 1 to 1 => 1
        2,  // write 1 to U => U
        -1  // invalid input
    };

    private final int[] possibleInstructions;
    private final int numCits, offset, step;
    private long tested = 0;

    private CitBruteForcer(int numCits, int[] possibleInstructions, int offset, int step)
    {
        this.numCits = numCits;
        this.possibleInstructions = possibleInstructions;
        this.offset = offset;
        this.step = step;
    }

    public void run()
    {
        int numStates = 1 << numCits;
        int n = possibleInstructions.length;
        long limit = pow(n, numStates);

        for (long i = offset; i < limit; i += step) {
            // Decode as a base-n number.
            int[] instructions = new int[numStates];
            long tmp = i;
            for (int j = 0; j < numStates; j++, tmp /= n) instructions[j] = possibleInstructions[(int)(tmp % n)];
            Program p = new Program(numCits, instructions);
            if (p.test()) System.out.println("Candidate: " + i);
            tested++;
        }
    }

    public static void main(String[] args) {
        int numCits = 2;
        int numThreads = 4;
        int[] possibleInstructions = buildInstructions(numCits);

        int numStates = 1 << numCits;
        int n = possibleInstructions.length;
        System.out.println(n + " possible instructions");
        long limit = pow(n, numStates);

        CitBruteForcer[] forcers = new CitBruteForcer[numThreads];
        for (int i = 0; i < numThreads; i++) {
            forcers[i] = new CitBruteForcer(numCits, possibleInstructions, i, numThreads);
            new Thread(forcers[i]).start();
        }

        int pc = 0;
        while (pc < 100) {
            // Every 10 secs is easily fast enough to update
            try { Thread.sleep(10000); } catch (InterruptedException ie) {}

            long tested = 0;
            for (CitBruteForcer cbf : forcers) tested += cbf.tested; // May underestimate because the value may be stale
            int completed = (int)(100 * tested / limit);
            if (completed > pc) {
                pc = completed;
                System.out.println(pc + "% complete");
            }
        }
        System.out.println(limit + " programs tested");
    }

    private static int[] buildInstructions(int numCits) {
        int limit = (int)pow(3, numCits);
        Set<Integer> instructions = new HashSet<Integer>();
        for (int target = 0; target <= limit; target++) {
            int toSetZero = 0, toSetOne = 0;
            for (int i = 0, tmp = target; i < numCits; i++, tmp /= 3) {
                if (tmp % 3 == 0) toSetZero |= 1 << i;
                else if (tmp % 3 == 1) toSetOne |= 1 << i;
            }
            buildInstructions(0xc, toSetZero, toSetOne, false, false, instructions);
        }
        int[] rv = new int[instructions.size()];
        Iterator<Integer> it = instructions.iterator();
        for (int i = 0; i < rv.length; i++) rv[i] = it.next().intValue();
        return rv;
    }

    private static void buildInstructions(int suffix, int toSetZero, int toSetOne, boolean emitted0, boolean emitted1, Set<Integer> instructions)
    {
        if (!emitted1) {
            buildInstructions((suffix << 4) + 0x8, toSetZero, toSetOne, false, true, instructions);
        }
        if (!emitted0) {
            buildInstructions((suffix << 4) + 0x4, toSetZero, toSetOne, true, true, instructions);
        }
        if (toSetZero == 0 && toSetOne == 0) {
            instructions.add(suffix);
            return;
        }

        for (int i = 0; toSetZero >> i > 0; i++) {
            if (((toSetZero >> i) & 1) == 1) buildInstructions((suffix << 3) + 0x0 + i+1, toSetZero & ~(1 << i), toSetOne, emitted0, emitted1, instructions);
        }
        for (int i = 0; toSetOne >> i > 0; i++) {
            if (((toSetOne >> i) & 1) == 1) buildInstructions((suffix << 3) + 0x4 + i+1, toSetZero | (1 << i), toSetOne & ~(1 << i), emitted0, emitted1, instructions);
        }
    }

    private static long pow(long n, int k) {
        long rv = 1;
        while (k-- > 0) rv *= n;
        return rv;
    }

    static class Program {
        private final int numCits;
        private final int[] instructions;
        private final Set<Integer> checked = new HashSet<Integer>();
        private final Set<Integer> toCheck = new HashSet<Integer>();

        Program(int numCits, int[] instructions) {
            this.numCits = numCits;
            this.instructions = (int[])instructions.clone();
            toCheck.add(Integer.valueOf(0));
        }

        boolean test() {
            try {
                while (!toCheck.isEmpty()) checkNext();
            } catch (Exception ex) {
                return false;
            }

            // Need each reachable state which hasn't emitted the full output to be able to reach one which has.
            Set<Integer> reachable = new HashSet<Integer>(checked);
            for (Integer reached : reachable) {
                checked.clear();
                toCheck.clear();
                toCheck.add(reached);
                while (!toCheck.isEmpty()) checkNext();
                boolean emitted = false;
                for (Integer i : checked) {
                    if ((i.intValue() & 3) == 2) emitted = true;
                }
                if (!emitted) return false;
            }

            return true;
        }

        private void checkNext() {
            Integer state = toCheck.iterator().next();
            toCheck.remove(state);
            checked.add(state);
            run(state.intValue());
        }

        private void run(final int state) {
            // Check which instructions apply
            for (int i = 0; i < instructions.length; i++) {
                boolean ok = true;
                for (int j = 1; j <= numCits; j++) {
                    int cit = (state >> (2 * j)) & 3;
                    if (cit == 2 || cit == ((i >> (j-1)) & 1)) continue;
                    ok = false; break;
                }
                if (ok) run(state, instructions[i]);
            }
        }

        private void run(int state, int instruction) {
            while (true) {
                int cit = instruction & 3;
                if (cit == 0) {
                    int emit = (instruction >> 2) & 3;
                    if (emit == 3) break;
                    if (emit > (state & 3) + 1 || emit < (state & 3)) throw new IllegalStateException();
                    state = (state & ~3) | emit;
                    instruction >>= 4;
                }
                else {
                    int shift = 2 * cit;
                    int transitionIdx = (instruction & 4) + ((state >> shift) & 3);
                    int stateMasked = state & ~(3 << shift);
                    consider(stateMasked | (TRANSITION_ABORT[transitionIdx] << shift));
                    state = stateMasked | (TRANSITION_OK[transitionIdx] << shift);
                    instruction >>= 3;
                }
                // Could abort between instructions (although I'm not sure this is strictly necessary - this is "better" than the mid-instruction abort
                consider(state);
            }
            // Halt or loop.
            consider(state);
        }

        private void consider(int state) {
            if (!checked.contains(state)) toCheck.add(state);
        }
    }
}

If I use my assumption about placement of outputs, the number of 2-cit programs drops considerably and the checking time is less than a minute, but even with this assumption the number of 3-cit programs is more than 2^80, or a factor of about 2^47 more than the 2-cit programs checked in 7 hours. Not reasonably brute-forceable, in other words.

This is was my best attempt at answering my own question. I am uncertain that it meets requirement 3, and am open to refutation. It is not tenacious :-(
/*  1 */    #include "hal.h"
/*  2 */    main(){
/*  3 */        unsigned c = r(2);  // get cit 2 into c
/*  4 */        unsigned d = r(c);  // get cit c into d
/*  5 */    // here if d==c then we have not output 1 yet
/*  6 */    //              else we have     output 0
/*  7 */        if (0==c)
/*  8 */            w( 2, 0 ),      // cit 2 to 0
/*  9 */            w( 1, 0 ),      // cit 1 to 0
/* 10 */            w( 1,!d ),      // cit 1 to complement of d
/* 11 */            w( 2, 1 );      // cit 2 to 1
/* 12 */        w( 0, 0 );          // cit 0 to 0
/* 13 */        if (d==c)
/* 14 */            p( 2 ),         // put 2, first one outputs 0
/* 15 */            w( 2, 0 );      // cit 2 to 0
/* 16 */        w( 0, 1 );          // cit 0 to 1
/* 17 */        p( 1 );             // put 1, first one outputs 1
/* 16 */    }                       // halt

My test program says that's not tenacious: 1. Run program to completion. Output: 01, Cits: 110. 2. Abort during #15. Cits: 10U. 3. Read c = 1, abort during #12. Cits: U0U. 4. Read c = 0, d = 0 and the program will print 01 again.

Sorry, the first abort should be at line #11, not #15.

source: Stack Exchange

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
ASCII Ball in Box Animation
Write a program that displays a moving ASCII ball * inside a rectangle (20 by 10 chars including border). The ball must not cross the rectangle, e.g. bump off when it hits the wall. The scene must be cleared and redrawn every 0.1 seconds and the ball must move 1 char in x and y direction every frame. The shortest program written in any language wins.
Example output (frame 1)
+------------------+
|*                 |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
+------------------+

Example output (frame 2)
+------------------+
|                  |
| *                |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
+------------------+

Example output (frame 8)
+------------------+
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|       *          |
+------------------+

Example output (frame 9)
+------------------+
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|        *         |
|                  |
+------------------+

Does printing 99 newlines qualify as clearing the screen?

Not on my monitor with 1080x1920 resolution :)

related: https://codegolf.stackexchange.com/q/110410/55735

Ruby 1.9, 115 characters
The movement logic is quite similar to Danko's answer.
This version has been tested on Linux only.
p=0
loop{u=(?|+?\s*18+"|
")*8
u[165-21*(7-p%14).abs-(17-p%34).abs]=?*
p+=1
puts"\e[2J",r=?++?-*18+?+,u,r
sleep 0.1}

With Ruby 1.9.3 under Windows 7, puts"\e[2J" just prints ←[2J (and a newline) on the screen.

@r.e.s. See my edit for a version which should run on Windows (can't test it myself unfortunately).

Using cls doesn't work for me, but system ("cls") does.

@r.e.s. use `cls`.  Literal backticks.

@MarkReed - That's what I tried to write .. Anyway, it doesn't work. Windows seems to require system("cls").

damn this one's good!

you can actually go down to 118 if you put the first two lines inside the loop. this way you don't have to remove the ball from the box any more. you can also save one character by omitting the newline after loop{.

that's 118 in total, not 117 sorry for the confusion

@padde I'm counting 117 characters. Make sure your editor doesn't add a trailing newline.

i used vim + wc, still get 118, double checked. I guess it doesn't matter (at least not now), but hey its codegolf!

@padde Vim does indeed add a trailing newline. You can verify this by looking at the file with hd.

@Ventero You are right, sorry for that!

Powershell, 144 characters
Based on Joey's excellent answer, using the fact that the ball coordinates are a function of the frame index (i), so if you have something like x=n-abs(n-(i mod (2*n))), x will go from 0 to n, back to 0, and so on...
for(){cls
($l="+$('-'*18)+")
7..0|%{$j=$_
"|$(-join(17..0|%{'* '[$j-[Math]::abs(7-$i%14)-or$_-[Math]::abs(17-$i%34)]}))|"}
$l;$i++;sleep -m 100}

Nice one. Although I was kinda proud of my if(-1,18-eq$x){$a*=-1;$x+=2*$a}if(-1,8-eq$y){$b*=-1;$y+=2*$b} which replaced four ifs earlier ;-). I was sure there had to be a formula, though.

Ruby (179 174 147)
EDIT got rid of some more chars:
l=?++?-*18+?++?\n
c=?|+?\s*18+?|+?\n
p=22
u=v=1
loop{f=l+c*8+l
f[p]=?*
puts"\e[2J"+f
p+=(u=f[p+u]==' '?u:-u)+21*(v=f[p+21*v]==' '?v:-v)
sleep 0.1}

EDIT shaved off some chars, now 174:
l="+#{'-'*18}+\n";f=l+"|#{' '*18}|\n"*8+l;x=y=u=v=1
loop{f[21*y+x]='*';$><<"\e[2J\e[f"+f;f[21*y+x]=' '
u=f[21*y+x+u]==' '?u:-u;v=f[21*(y+v)+x]==' '?v:-v
x+=u;y+=v;sleep 0.1}

Ungolfed:
l="+#{'-'*18}+\n"           # top and bottom lines
f=l+"|#{' '*18}|\n"*8+l     # complete box as string
x=y=u=v=1                   # x,y position; u,v next move
loop {                      #
  f[21*y+x]='*'             # add ball to box
  $> << "\e[2J\e[f"+f       # clear screen and print box with ball
  f[21*y+x]=' '             # remove ball from box
  u=f[21*y+x+u]==' '?u:-u   # next move in x direction
  v=f[21*(y+v)+x]==' '?v:-v # next move in y direction
  x+=u                      # perform move
  y+=v                      # --"--
  sleep 0.1                 # .zZZ...
}                           #

Shouldn't sleep .1 work too?

Nope, not in 1.9. SyntaxError: (irb):1: no .<digit> floating literal anymore; put 0 before dot. But i'll get back to that if i need it in the future, thanks!

If you're on 1.9 you can use char literals to shorten a few things, e.g. ?* instead of '*', etc.

Using Ruby 1.9.3 under Win7, this prints rectangles one after (below) the other, each having ←[2J←[f+------------------+ as the first line.

then change $> << "\e[2J\e[f"+f to 'cls';$><<f (use backticks for cls)

Python 2, 234
I'm sure this can be golfed more, but I gotta go so here's what I have sofar. will work more on it later
import os,time
a,b,c,d,e,n='+- |*\n'
w=d+c*18+d+n
s=a+b*18+a+n
x,y=0,0
g,h=17,7
j,k=1,1
while 1:
 if 0>x or x>g:j*=-1;x+=j
 if 0>y or y>h:k*=-1;y+=k
 os.system('cls');print s+w*y+d+c*x+e+c*(g-x)+d+n+w*(h-y)+s;x+=j;y+=k;time.sleep(0.1)

note: works on Windows command console. Other operating systems may use a different command than cls to clear the screen, such as clear

does print "\e[H\e[2J" work on windows?

@padde - It doesn't seem to work when I run your Ruby program under Windows 7 (see my comment to your post).

JavaScript (275 283)
s=Array(19).join(' ');n='\n';z=Array(9).join('|'+s+'|'+n).split(n,8);
x=y=0;a=b=1;t='+'+s.replace(/ /g,'-')+'+';
setInterval(function(){u=z[y];z[y]=u.replace(eval('/( {'+x+'}) /'),'$1*');
$('#o').text(t+n+z.join('\n')+n+t);z[y]=u;x+=a;y+=b;if(!x|x==17)a=-a;if(!y|y==7)b=-b},100)

Demo: http://jsfiddle.net/eKcfu/2/
I wrote this up pretty quickly so I'm sure there's still quite a bit of room for improvement.  Suggestions are welcome :)
Edit 1: Remove unnecessary separate function call, embed directly in setInterval.

PowerShell, 184 185 215
Only semi-golfed as my brain isn't working properly when I'm sick ...
A few nice tricks in it, though.
for($a=$b=1){cls
($l="+$('-'*18)+")
0..7|%{$j=$_
"|$(-join(0..17|%{'* '[$j-$y-or$_-$x]}))|"}
$l
$x+=$a;$y+=$b
if(-1,18-eq$x){$a*=-1;$x+=2*$a}if(-1,8-eq$y){$b*=-1;$y+=2*$b}sleep -m 100}

[Edit]: Looping over the field is much shorter.

Haskell, 212 characters
import System
main=mapM_ f$s 19`zip`s 9
s n=[2..n]++[n-1,n-2..3]++s n
f p=r"clear">>putStr(unlines[[" |-+*"!!(19#i+2*(9#j)+4*e((i,j)==p))|i<-[1..20]]|j<-[1..10]])>>r"sleep 0.1"
b#n=e$n<2||n>b
e=fromEnum
r=system

Uses a more functional approach for calculating the coordinates, by making the infinite sequence for each coordinate separately and then zipping them together (lines 2 and 3). The rest is drawing code.

QBasic (QB64), 178 173 bytes
a$="+------------------+
?a$
for c=1to 8
?"|                  |
next
?a$
do
x=19-abs(17-(i mod 34))
y=9-abs(7-(i mod 14))
locate y,x
?"*
_delay .1
locate y,x
?" "
i=i+1
loop

-5 bytes thanks to DLosc

Some more golfs I just noticed: the side-wall print statement can be ?"|"SPC(18)"| (unfortunately, using STRING$ to generate the hyphens doesn't save any bytes); you don't need parentheses around the mod expressions; you've got an unnecessary double quote after the space on the third-last line; and, finally, I suspect you can save bytes by CLSing and redrawing the whole box each time through the loop.

Perl 5, 141 characters
print"\e[H\e[2J",$h="+"."-"x18 ."+
",(map{"|".$"x$q,(abs$t%14-7)-$_?$":"*",$"x(17-$q),"|
"}0..7),$h,select'','','',0.1while$q=abs$t++%34-17,1

Does not start on the upper left corner as the example output does, but that is not stated as a requirement.

Ruby 1.9, 162 characters
35 chars shy of @Ventero's answer, but I was impressed that I could get it down this far while still using a relatively straightforward approach to the actual logic.  The ^[ is a literal ESC (1 char).
x=y=0
v=h=1
s=' '
loop{puts"^[[2J"+b="+#{?-*18}+",*(0..7).map{|i|"|#{i!=y ?s*18:s*x+?*+s*(17-x)}|"},b
y+=v
y+=v*=-1if y<0||y>7
x+=h
x+=h*=-1if x<0||x>17
sleep 0.1}

R, 233 characters
s=c("\n+",rep("-",18),"+");for (j in 1:8){cat(s,sep="");cat(rep(c("\n|",rep("",17),"|"),j-1));cat(c("\n|",rep(" ",j-1),"*",rep(" ",18-j),"|"),sep="");cat(rep(c("\n|",rep("",17),"|"),8-j));cat(s,sep="");Sys.sleep(0.1);system("clear")}

Another bash entry - 213 204 chars
Not really a prize winner, but it was fun nonetheless. It uses vt100 char sequences for the drawing. (the code reported here uses 215 chars for readability, 2 chars can be removed by escaping, e.g. '*' -> \*
e(){ printf "\e[$1";}
e 2J;e H
h='+------------------+'
echo $h
for((;++j<9;));do printf '|%18s|\n';done
echo $h
e '3;2H*'
while :;do
e 'D '
((i/17%2))&&e D||e C
((++i/7%2))&&e A||e B
e 'D*'
sleep .1
done

Powershell, 139 bytes
Inspired by Danko Durbić's answer.
for(){cls
,"+$('-'*18)+
"*2-join("|$(' '*18)|
"*8-replace"^(\W{$(21*[Math]::abs(7-$i%14)+[Math]::abs(17-$i++%34))}.) ",'$1*')
sleep -m 100}

This script uses the -replace operator to draw * inside the rectangle.
Less golfed script to explain how it works:
for(){
    cls
    $y=[Math]::abs(7-$i%14)
    $x=[Math]::abs(17-$i++%34)
    $b="+$('-'*18)+`n"
    $m="|$(' '*18)|`n"*8-replace"^(\W{$(21*$y+$x)}.) ",'$1*'
    ,$b*2-join($m)          # draw it
    sleep -m 100
}

Bash 278  300, 296
h="+------------------+"
w="|                  |"
g(){
echo -e "\e[$2;$1H$3"
}
g 1 1 $h
for i in {1..8}
do
echo "$w"
done
echo $h
x=4
y=4
p=1
q=1
for((;;))
do
((x==19&&p==1||x==2&&p==-1))&&p=-$p
((y==9&&q==1||y==2&&q==-1))&&q=-$q
x=$((x+p))
y=$((y+q))
g $x $y \*
sleep .1
g $x $y " "
done

The \e in the line echo -e "\e[$2;$1H$3" can be produced by
echo -e "\x1b"

to replace it. As binary 0x1b it is 3 chars shorter; I count just 1 for "\e", because only the layouting software forces me to use \e.

An anonymous user suggested edits to remove the $ symbols inside ((...)) and replace x=$(($x+$p)) with ((x+=p)) and similarly on the following line. (They also suggested using \e for the escape character).

I would suggest in addition that \* might work as a replacement for "*".

@PeterTaylor: Thanks to the anonymous user. I incorporated suggestion no 1, and use no 2 in modified form, and yours.

@userunknown: You're rep of 1,337 needs to be permanently locked in place :P

@mellamokb: I would prefer 0xCAFE, #5CA7A or -32768.

@mellamokb: It's gone.

TI Basic, 169 167 bytes
1→X
1→Y
1→S
1→T
While 1
ClrHome
Output(Y,X,"*
S(X>1 and X<20)+(X=1)-(X=20→S
T(Y>1 and Y<10)+(Y=1)-(Y=10→T
X+S→X
Y+T→Y
For(N,1,20,19
For(O,1,10,9
Output(O,N,"+
End
End
For(N,2,19
For(O,1,10,9
Output(O,N,"-
End
End
For(O,2,9
Output(O,1,"|
Output(O,20,"|
End
End

Horribly slow, but it works.

(X=20)→S can be (X=20→S, and you can take advantage of Ans to save a few bytes in the final For( loop. I'm positive lines 8 and 9 can be golfed, but I'm not sure how at the moment.

@M.I.Wright Where would I put the Ans?

"| \ Output(O,1,Ans \ Output(O,20,Ans should work.

@M.I.Wright But isn't that replacing a two character string with a three character string? And adding the two character string above it, making it +4?

What do you mean? Ans is a one-byte token, typed with 2nd (-). That'll end up saving one byte, since the | token is two bytes on the calculator.

@M.I.Wright Is there an online byte counter anywhere? I was just going off of character count.

Let us continue this discussion in chat.

You can golf this using http://codereview.stackexchange.com/questions/82847/ti-basic-bouncing-ball-animation

dim(identity(1->A While 1 Ans->B Ans+∟A->A ClrHome ∟Bcos(πʳ(Ans=1 or Ans>{19,9 For(N,1,20 For(O,1,10 Output(O,N,sub("* |-+",2+(N=1 or N=20)+2not(fPart(log(O))-min(Ans={O,N End End End
should be significantly shorter. Sorry about the formatting.

PHP, 196 186 148 bytes
I removed avoiding an integer overflow to save 6 bytes. It will run for 29 billion years before overflow; still 6.8 years on a 32 bit system. I´d say that´s acceptable.
Calculating the position instead of adjusting it saved a lot, preparing the complete template at once another lot.
for(;++$i;$s[-3-21*abs($i%14-7)-abs($i%34-17)]="*",print$f(_,9e5,"
").$s.$z,usleep(1e5))$s=($f=str_pad)($z=$f("+",19,"-")."+
",189,$f("|",19)."|
");
").$z;

Run with -nr. Requires PHP 7.1.
breakdown:
for(;++$i;      # infinite loop:
                    # 2. set asterisk at appropriate position
    $s[-3-21*abs($i%14-7)-abs($i%34-17)]="*";
                    # 3. clear screen: print 900k newlines
    print$f(_,9e5*0+2,"\n")
            .$s.$z, # 4. print field
    usleep(1e5))    # 5. sleep 100000 microseconds
                    # 1. create template
    $s=($f=str_pad)($z=$f("+",19,"-")."+\n",189,$f("|",19)."|\n");

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Best Scoring Boggle Board
I was interested in seeing the answers to this (now defunct) question, but it has never been corrected/improved.
Given a set of 6-sided Boggle dice (configuration stolen from this question), determine in two minutes of processing time which board configuration will allow for the highest possible score. (i.e. which dice in which location with which side up allows for the largest scoring word pool?)

OBJECTIVE

Your code should run for no more than 2 minutes (120 seconds). At that time, it should automatically stop running and print the results.
Final challenge score will be the average Boggle score of 5 runs of the program.

In the event of a tie, the winner will be whichever algorithm found more words.
In the event there is still a tie, the winner will be whichever algorithm found more long (8+) words.

RULES/CONSTRAINTS

This is a code challenge; code length is irrelevant.
Please refer to this link for a word list (use ISPELL "english.0" list - the SCOWL list is missing some pretty common words).

This listing may be referred to/imported/read in your code any way you wish.
Only words matched by the regex ^([a-pr-z]|qu){3,16}$ will be counted. (Only lowercase letters, 3-16 characters, qu must be used as a unit.)

Words are formed by linking adjacent letters (horizontal, vertical, and diagonal) to spell words out in the correct order, without using a single die more than once in a single words.

Words must be 3 letters or longer; shorter words will earn no points.
Duplicated letters are acceptable, just not dice.
Words that span the edges/cross over from one side of the board to the other are not allowed.

The final Boggle (not challenge) score is the total of the point values for all the words that are found.

The point value assigned for each word is based on the length of the word. (see below)
Normal Boggle rules would deduct/discount words found by another player. Assume here no other players are involved and all found words count towards the total score.
However, words found more than once in the same grid should only be counted once.

Your function/program must FIND the optimal arrangement; simply hard-coding a predetermined list won't do.
Your output should be a 4x4 grid of your ideal game board, a list of all the found words for that board, and the Boggle score to match those words.

DIE CONFIGURATION
A  A  E  E  G  N
E  L  R  T  T  Y
A  O  O  T  T  W
A  B  B  J  O  O
E  H  R  T  V  W
C  I  M  O  T  U
D  I  S  T  T  Y
E  I  O  S  S  T
D  E  L  R  V  Y
A  C  H  O  P  S
H  I  M  N  Qu U
E  E  I  N  S  U
E  E  G  H  N  W
A  F  F  K  P  S
H  L  N  N  R  Z
D  E  I  L  R  X

STANDARD BOGGLE SCORING TABLE
Word length => Points
<= 2 - 0 pts
   3 - 1
   4 - 1
   5 - 2
   6 - 3
   7 - 5
>= 8 - 11 pts
*Words using the "Qu" die will count the full 2 letters for their word, not just the 1 die.

EXAMPLE OUTPUT
A  L  O  J
V  U  T  S
L  C  H  E
G  K  R  X

CUT
THE
LUCK
HEX
....

140 points

If any further clarification is needed, please ask!

I would prefer to have a dictionary provided to standardize the objective.  Note also that this is not a new idea, as a simple google search will reveal :)  The highest score I've seen is 4527 (1414 total words), found here: http://ai.stanford.edu/~chuongdo/boggle/index.html

@mellamokb Sure, the task's not new, but making it as short as possible is the trick.... ;-)

Is the program required to terminate this century?

@mellamokb great link. They use a genetic algorithm to randomly find good boards. I would not be surprised if a more intelligent algorithm could find a better board though.

@PeterTaylor Ideally, yes. :-) I had envisioned people coming up with various ways to take shortcuts, rather than iterate through every possible permutation - though anyone wanting (willing) to go that route is free to do so.

I don't think this is a great idea for a code-golf. Why not just make it a code-challenge?

@gnibbler If I do that, then what would be the winning criteria? Best Boggle score? AFAIK, there is just one correct answer there, and multiple people could get it. I'm not opposed to your suggestion, but I'm not sure how it would work.

Sometimes code challenges are made based on the efficiency of the algorithm, i.e., how long it takes the program to run on standardized hardware.

@mellamokb Is the a public resource for this? I am aware of ideone and codepad, but I don't think these will cut it, will they? I don't have a machine myself that is capable of running tests for all cases.

@Gaffi: I'm not so sure the maximum point value is currently actually known.  The search space is so large that every algorithm I've seen has used AI or some sort of genetic algorithm.  It may still be possible to find a larger score.  Nevertheless, it doesn't matter what is "known" to be the largest score, because the programs written in this challenge have to find the highest they can at runtime without cheating using prior knowledge, so perhaps the criteria can be the one that generates the largest point value while running in less then 30 seconds, or something like that.

@mellamokb I suppose I can live with that... I will adapt the question. I think I'll allow for multiple runs (best of 20, let's say) in case the (assumed) randomness of a given algorithm returns a low 'best'.

What is Qu? Is it just a mistake or a place where I should do "Q" and "U" at once?

@GlitchMr In English, Q is typically only ever used with U. Boggle accounts for this by putting the two letters on the same die as one unit.

The word list specification is unclear. Are you counting only those words listed in english.0 in lower case? (Standard word game rules exclude abbreviations/initialisms and proper nouns).

@PeterTaylor In my own code, I take all words (case insensitive) excluding any with ' (i.e. it's, ca'nt). No, I did not specify these constraints, but I agree yours work fairly well. Based on this specific list, how does this sound? All words with: -no punctuation; -a lower-case initial letter. I did not scan the entire file, but these two rules alone cover (exclude) a large amount of words. Do you have another suggestion?

I was thinking regex ^([a-pr-z]|qu){3,16}$ (which would incorrectly exclude 3-letter words with qu, but there aren't any).

@PeterTaylor Works for me... Fixed.

Since I don't think I'm going to get my current idea working in time, I'll throw it out for anyone who wants to try to beat the deadline. Basically I inverted the problem: first find a really good pair of words (i.e. two words which individually have substrings giving a score of 4+ points per letter) which between them fit in 16 dice, and then try to find a permutation of dice which gets lots of extra words.

Are you familiar with POTM? The problem type and the 2-minute time limit are reminiscent of that contest :)

@hobbs I was not, but I'm looking now. Thanks for the info!

C, averaging 500+ 1500 1750 points
This is a relatively minor improvement over version 2 (see below for notes on previous versions). There are two parts. First: Instead of selecting boards randomly from the pool, the program now iterates over every board in the pool, using each one in turn before returning to the top of the pool and repeating. (Since the pool is being modified while this iteration occurs, there will still be boards that get chosen twice in a row, or worse, but this is not a serious concern.) The second change is that the program now tracks when the pool changes, and if the program goes for too long without improving the pool's contents, it determines that the search has "stalled", empties the pool, and starts over with a new search. It continues to do this until the two minutes are up.
I had initially thought that I would be employing some kind of heuristic search to get beyond the 1500-point range. @mellamokb's comment about a 4527-point board led me to assume that there was plenty of room for improvement. However, we are using a relatively small wordlist. The 4527-point board was scoring using YAWL, which is the most inclusive wordlist out there -- it's even bigger than the official US Scrabble wordlist. With this in mind, I re-examined the boards my program had found and noticed that there appeared to be a limited set of boards above 1700 or so. So for example, I had multiple runs that had discovered a board scoring 1726, but it was always the exact same board that was found (ignoring rotations and reflections).
As another test, I ran my program using YAWL as the dictionary, and it found the 4527-point board after about a dozen runs. Given this, I am hypothesizing that my program is already at the upper limit of the search space, and therefore the rewrite I was planning would introduce extra complexity for very little gain.
Here is my list of the five highest-scoring boards my program has found using the english.0 wordlist:
1735 :  D C L P  E I A E  R N T R  S E G S
1738 :  B E L S  R A D G  T I N E  S E R S
1747 :  D C L P  E I A E  N T R D  G S E R
1766 :  M P L S  S A I E  N T R N  D E S G
1772:   G R E P  T N A L  E S I T  D R E S

My belief is that the 1772 "grep board" (as I've taken to calling it), with 531 words, is the highest-scoring board possible with this wordlist. Over 50% of my program's two-minute runs end with this board. I've also left my program running overnight without it finding anything better. So if there is a higher-scoring board, it would likely have to have some aspect that defeats the program's search technique. A board in which every possible small change to the layout causes a huge drop in the total score, for example, might never be discovered by my program. My hunch is that such a board is very unlikely to exist.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>

#define WORDLISTFILE "./english.0"

#define XSIZE 4
#define YSIZE 4
#define BOARDSIZE (XSIZE * YSIZE)
#define DIEFACES 6
#define WORDBUFSIZE 256
#define MAXPOOLSIZE 32
#define STALLPOINT 64
#define RUNTIME 120

/* Generate a random int from 0 to N-1.
 */
#define random(N)  ((int)(((double)(N) * rand()) / (RAND_MAX + 1.0)))

static char const dice[BOARDSIZE][DIEFACES] = {
    "aaeegn", "elrtty", "aoottw", "abbjoo",
    "ehrtvw", "cimotu", "distty", "eiosst",
    "delrvy", "achops", "himnqu", "eeinsu",
    "eeghnw", "affkps", "hlnnrz", "deilrx"
};

/* The dictionary is represented in memory as a tree. The tree is
 * represented by its arcs; the nodes are implicit. All of the arcs
 * emanating from a single node are stored as a linked list in
 * alphabetical order.
 */
typedef struct {
    int letter:8;   /* the letter this arc is labelled with */
    int arc:24;     /* the node this arc points to (i.e. its first arc) */
    int next:24;    /* the next sibling arc emanating from this node */
    int final:1;    /* true if this arc is the end of a valid word */
} treearc;

/* Each of the slots that make up the playing board is represented
 * by the die it contains.
 */
typedef struct {
    unsigned char die;      /* which die is in this slot */
    unsigned char face;     /* which face of the die is showing */
} slot;

/* The following information defines a game.
 */
typedef struct {
    slot board[BOARDSIZE];  /* the contents of the board */
    int score;              /* how many points the board is worth */
} game;

/* The wordlist is stored as a binary search tree.
 */
typedef struct {
    int item: 24;   /* the identifier of a word in the list */
    int left: 16;   /* the branch with smaller identifiers */
    int right: 16;  /* the branch with larger identifiers */
} listnode;

/* The dictionary.
 */
static treearc *dictionary;
static int heapalloc;
static int heapsize;

/* Every slot's immediate neighbors.
 */
static int neighbors[BOARDSIZE][9];

/* The wordlist, used while scoring a board.
 */
static listnode *wordlist;
static int listalloc;
static int listsize;
static int xcursor;

/* The game that is currently being examined.
 */
static game G;

/* The highest-scoring game seen so far.
 */
static game bestgame;

/* Variables to time the program and display stats.
 */
static time_t start;
static int boardcount;
static int allscores;

/* The pool contains the N highest-scoring games seen so far.
 */
static game pool[MAXPOOLSIZE];
static int poolsize;
static int cutoffscore;
static int stallcounter;

/* Some buffers shared by recursive functions.
 */
static char wordbuf[WORDBUFSIZE];
static char gridbuf[BOARDSIZE];

/*
 * The dictionary is stored as a tree. It is created during
 * initialization and remains unmodified afterwards. When moving
 * through the tree, the program tracks the arc that points to the
 * current node. (The first arc in the heap is a dummy that points to
 * the root node, which otherwise would have no arc.)
 */

static void initdictionary(void)
{
    heapalloc = 256;
    dictionary = malloc(256 * sizeof *dictionary);
    heapsize = 1;
    dictionary->arc = 0;
    dictionary->letter = 0;
    dictionary->next = 0;
    dictionary->final = 0;
}

static int addarc(int arc, char ch)
{
    int prev, a;

    prev = arc;
    a = dictionary[arc].arc;
    for (;;) {
        if (dictionary[a].letter == ch)
            return a;
        if (!dictionary[a].letter || dictionary[a].letter > ch)
            break;
        prev = a;
        a = dictionary[a].next;
    }
    if (heapsize >= heapalloc) {
        heapalloc *= 2;
        dictionary = realloc(dictionary, heapalloc * sizeof *dictionary);
    }
    a = heapsize++;
    dictionary[a].letter = ch;
    dictionary[a].final = 0;
    dictionary[a].arc = 0;
    if (prev == arc) {
        dictionary[a].next = dictionary[prev].arc;
        dictionary[prev].arc = a;
    } else {
        dictionary[a].next = dictionary[prev].next;
        dictionary[prev].next = a;
    }
    return a;
}

static int validateword(char *word)
{
    int i;

    for (i = 0 ; word[i] != '\0' && word[i] != '\n' ; ++i)
        if (word[i] < 'a' || word[i] > 'z')
            return 0;
    if (word[i] == '\n')
        word[i] = '\0';
    if (i < 3)
        return 0;
    for ( ; *word ; ++word, --i) {
        if (*word == 'q') {
            if (word[1] != 'u')
                return 0;
            memmove(word + 1, word + 2, --i);
        }
    }
    return 1;
}

static void createdictionary(char const *filename)
{
    FILE *fp;
    int arc, i;

    initdictionary();
    fp = fopen(filename, "r");
    while (fgets(wordbuf, sizeof wordbuf, fp)) {
        if (!validateword(wordbuf))
            continue;
        arc = 0;
        for (i = 0 ; wordbuf[i] ; ++i)
            arc = addarc(arc, wordbuf[i]);
        dictionary[arc].final = 1;
    }
    fclose(fp);
}

/*
 * The wordlist is stored as a binary search tree. It is only added
 * to, searched, and erased. Instead of storing the actual word, it
 * only retains the word's final arc in the dictionary. Thus, the
 * dictionary needs to be walked in order to print out the wordlist.
 */

static void initwordlist(void)
{
    listalloc = 16;
    wordlist = malloc(listalloc * sizeof *wordlist);
    listsize = 0;
}

static int iswordinlist(int word)
{
    int node, n;

    n = 0;
    for (;;) {
        node = n;
        if (wordlist[node].item == word)
            return 1;
        if (wordlist[node].item > word)
            n = wordlist[node].left;
        else
            n = wordlist[node].right;
        if (!n)
            return 0;
    }
}

static int insertword(int word)
{
    int node, n;

    if (!listsize) {
        wordlist->item = word;
        wordlist->left = 0;
        wordlist->right = 0;
        ++listsize;
        return 1;
    }

    n = 0;
    for (;;) {
        node = n;
        if (wordlist[node].item == word)
            return 0;
        if (wordlist[node].item > word)
            n = wordlist[node].left;
        else
            n = wordlist[node].right;
        if (!n)
            break;
    }

    if (listsize >= listalloc) {
        listalloc *= 2;
        wordlist = realloc(wordlist, listalloc * sizeof *wordlist);
    }
    n = listsize++;
    wordlist[n].item = word;
    wordlist[n].left = 0;
    wordlist[n].right = 0;
    if (wordlist[node].item > word)
        wordlist[node].left = n;
    else
        wordlist[node].right = n;
    return 1;
}

static void clearwordlist(void)
{
    listsize = 0;
    G.score = 0;
}

static void scoreword(char const *word)
{
    int const scoring[] = { 0, 0, 0, 1, 1, 2, 3, 5 };
    int n, u;

    for (n = u = 0 ; word[n] ; ++n)
        if (word[n] == 'q')
            ++u;
    n += u;
    G.score += n > 7 ? 11 : scoring[n];
}

static void addwordtolist(char const *word, int id)
{
    if (insertword(id))
        scoreword(word);
}

static void _printwords(int arc, int len)
{
    int a;

    while (arc) {
        a = len + 1;
        wordbuf[len] = dictionary[arc].letter;
        if (wordbuf[len] == 'q')
            wordbuf[a++] = 'u';
        if (dictionary[arc].final) {
            if (iswordinlist(arc)) {
                wordbuf[a] = '\0';
                if (xcursor == 4) {
                    printf("%s\n", wordbuf);
                    xcursor = 0;
                } else {
                    printf("%-16s", wordbuf);
                    ++xcursor;
                }
            }
        }
        _printwords(dictionary[arc].arc, a);
        arc = dictionary[arc].next;
    }
}

static void printwordlist(void)
{
    xcursor = 0;
    _printwords(1, 0);
    if (xcursor)
        putchar('\n');
}

/*
 * The board is stored as an array of oriented dice. To score a game,
 * the program looks at each slot on the board in turn, and tries to
 * find a path along the dictionary tree that matches the letters on
 * adjacent dice.
 */

static void initneighbors(void)
{
    int i, j, n;

    for (i = 0 ; i < BOARDSIZE ; ++i) {
        n = 0;
        for (j = 0 ; j < BOARDSIZE ; ++j)
            if (i != j && abs(i / XSIZE - j / XSIZE) <= 1
                       && abs(i % XSIZE - j % XSIZE) <= 1)
                neighbors[i][n++] = j;
        neighbors[i][n] = -1;
    }
}

static void printboard(void)
{
    int i;

    for (i = 0 ; i < BOARDSIZE ; ++i) {
        printf(" %c", toupper(dice[G.board[i].die][G.board[i].face]));
        if (i % XSIZE == XSIZE - 1)
            putchar('\n');
    }
}

static void _findwords(int pos, int arc, int len)
{
    int ch, i, p;

    for (;;) {
        ch = dictionary[arc].letter;
        if (ch == gridbuf[pos])
            break;
        if (ch > gridbuf[pos] || !dictionary[arc].next)
            return;
        arc = dictionary[arc].next;
    }
    wordbuf[len++] = ch;
    if (dictionary[arc].final) {
        wordbuf[len] = '\0';
        addwordtolist(wordbuf, arc);
    }
    gridbuf[pos] = '.';
    for (i = 0 ; (p = neighbors[pos][i]) >= 0 ; ++i)
        if (gridbuf[p] != '.')
            _findwords(p, dictionary[arc].arc, len);
    gridbuf[pos] = ch;
}

static void findwordsingrid(void)
{
    int i;

    clearwordlist();
    for (i = 0 ; i < BOARDSIZE ; ++i)
        gridbuf[i] = dice[G.board[i].die][G.board[i].face];
    for (i = 0 ; i < BOARDSIZE ; ++i)
        _findwords(i, 1, 0);
}

static void shuffleboard(void)
{
    int die[BOARDSIZE];
    int i, n;

    for (i = 0 ; i < BOARDSIZE ; ++i)
        die[i] = i;
    for (i = BOARDSIZE ; i-- ; ) {
        n = random(i);
        G.board[i].die = die[n];
        G.board[i].face = random(DIEFACES);
        die[n] = die[i];
    }
}

/*
 * The pool contains the N highest-scoring games found so far. (This
 * would typically be done using a priority queue, but it represents
 * far too little of the runtime. Brute force is just as good and
 * simpler.) Note that the pool will only ever contain one board with
 * a particular score: This is a cheap way to discourage the pool from
 * filling up with almost-identical high-scoring boards.
 */

static void addgametopool(void)
{
    int i;

    if (G.score < cutoffscore)
        return;
    for (i = 0 ; i < poolsize ; ++i) {
        if (G.score == pool[i].score) {
            pool[i] = G;
            return;
        }
        if (G.score > pool[i].score)
            break;
    }
    if (poolsize < MAXPOOLSIZE)
        ++poolsize;
    if (i < poolsize) {
        memmove(pool + i + 1, pool + i, (poolsize - i - 1) * sizeof *pool);
        pool[i] = G;
    }
    cutoffscore = pool[poolsize - 1].score;
    stallcounter = 0;
}

static void selectpoolmember(int n)
{
    G = pool[n];
}

static void emptypool(void)
{
    poolsize = 0;
    cutoffscore = 0;
    stallcounter = 0;
}

/*
 * The program examines as many boards as it can in the given time,
 * and retains the one with the highest score. If the program is out
 * of time, then it reports the best-seen game and immediately exits.
 */

static void report(void)
{
    findwordsingrid();
    printboard();
    printwordlist();
    printf("score = %d\n", G.score);
    fprintf(stderr, "// score: %d points (%d words)\n", G.score, listsize);
    fprintf(stderr, "// %d boards examined\n", boardcount);
    fprintf(stderr, "// avg score: %.1f\n", (double)allscores / boardcount);
    fprintf(stderr, "// runtime: %ld s\n", time(0) - start);
}

static void scoreboard(void)
{
    findwordsingrid();
    ++boardcount;
    allscores += G.score;
    addgametopool();
    if (bestgame.score < G.score) {
        bestgame = G;
        fprintf(stderr, "// %ld s: board %d scoring %d\n",
                time(0) - start, boardcount, G.score);
    }

    if (time(0) - start >= RUNTIME) {
        G = bestgame;
        report();
        exit(0);
    }
}

static void restartpool(void)
{
    emptypool();
    while (poolsize < MAXPOOLSIZE) {
        shuffleboard();
        scoreboard();
    }
}

/*
 * Making small modifications to a board.
 */

static void turndie(void)
{
    int i, j;

    i = random(BOARDSIZE);
    j = random(DIEFACES - 1) + 1;
    G.board[i].face = (G.board[i].face + j) % DIEFACES;
}

static void swapdice(void)
{
    slot t;
    int p, q;

    p = random(BOARDSIZE);
    q = random(BOARDSIZE - 1);
    if (q >= p)
        ++q;
    t = G.board[p];
    G.board[p] = G.board[q];
    G.board[q] = t;
}

/*
 *
 */

int main(void)
{
    int i;

    start = time(0);
    srand((unsigned int)start);

    createdictionary(WORDLISTFILE);
    initwordlist();
    initneighbors();

    restartpool();
    for (;;) {
        for (i = 0 ; i < poolsize ; ++i) {
            selectpoolmember(i);
            turndie();
            scoreboard();
            selectpoolmember(i);
            swapdice();
            scoreboard();
        }
        ++stallcounter;
        if (stallcounter >= STALLPOINT) {
            fprintf(stderr, "// stalled; restarting search\n");
            restartpool();
        }
    }

    return 0;
}

Notes for version 2 (June 9)
Here's one way to use the initial version of my code as a jumping-off point. The changes to this version consist of less than 100 lines, but tripled the average game score.
In this version, the program maintains a "pool" of candidates, consisting of the N highest-scoring boards that the program has generated so far. Every time a new board is generated, it is added to the pool and the lowest-scoring board in the pool is removed (which may very well be the board that was just added, if its score is lower than what's already there). The pool is initially filled with randomly generated boards, after which it keeps a constant size throughout the program's run.
The program's main loop consists of of selecting a random board from the pool and altering it, determining this new board's score and then putting it into the pool (if it scores well enough). In this fashion the program is continually refining high-scoring boards. The main activity is to make stepwise, incremental improvements, but the size of the pool also allows the program to find multi-step improvements that temporarily make a board's score worse before it can make it better.
Typically this program finds a good local maximum rather quickly, after which presumably any better maximum is too distant to be found. And so once again there's little point to running the program longer than 10 seconds. This might be improved by e.g. having the program detect this situation and start a fresh search with a new pool of candidates. However, this would net only a marginal increase. A proper heuristic search technique would likely be a better avenue of exploration.
(Side note: I saw that this version was generating about 5k boards/sec. Since the first version typically did 20k boards/sec, I was initially concerned. Upon profiling, however, I discovered that the extra time was spent managing the wordlist. In other words, it was entirely due to the program finding so many more words per board. In light of this, I considered changing the code to manage the wordlist, but given that this program is only using 10 of its allotted 120 seconds, such an optimization would be very premature.)
Notes for version 1 (June 2)
This is a very, very simple solution. All it does it generate random boards, and then after 10 seconds it outputs the one with the highest score. (I defaulted to 10 seconds because the extra 110 seconds permitted by the problem specification typically doesn't improve the final solution found enough to be worth waiting for.) So it's extremely dumb. However, it has all the infrastructure to make a good starting point for a more intelligent search, and if anyone wishes to make use of it before the deadline, I encourage them to do so.
The program starts by reading the dictionary into a tree structure. (The form isn't quite as optimized as it could be, but it's more than good enough for these purposes.) After some other basic initialization, it then begins generating boards and scoring them. The program examines about 20k boards per second on my machine, and after about 200k boards the random approach starts to run dry.
Since only one board is actually being evaluated at any given time, the scoring data is stored in global variables. This allows me to minimize the amount of constant data that has to be passed as arguments to the recursive functions. (I'm sure this will give some people hives, and to them I apologize.) The wordlist is stored as a binary search tree. Every word found has to be looked up in the wordlist, so that duplicate words aren't counted twice. The wordlist is only needed during the evaulation process, however, so it's discarded after the score is found. Thus, at the end of the program, the chosen board has to be scored all over again, so that the wordlist can be printed out.
Fun fact: The average score for a randomly-generated Boggle board, as scored by english.0, is 61.7 points.

Obviously, I need to improve my own efficiency. :-)

My genetic approach gets about 700-800 points generating about 200k boards, so you're clearly doing something far better than me in the way you produce the next generation.

My own tree structure, having been implemented only for the master wordlist thus far, while it works and allows me to validate boards, it bogs down my system memory (actively lags to the point that it takes a considerable amount of time to force the process to terminate early). This is surely my own fault, but I'm working at it! Edit: Already fixed! ;-)

@PeterTaylor I thought about trying a genetic algorithm, but I couldn't think of a plausible mechanism for combining two boards. How are you doing it? Are you selecting the parent randomly for each slot on the board?

I split the board state into the permutation of dice and the faces showing on the dice. For permutation crossover I use "order crossover 1" from http://www.cs.colostate.edu/~genitor/1995/permutations.pdf and for face crossover I do the obvious. But I have an idea for a totally different approach which I need to find the time to implement.

With my completely random approach, I've noticed too that the maximum score is generally found very quickly. I've started toying with making minor modifications to the current best, but I'm not quite there yet. Also, as a thought for anyone else, since my processing is so slow, I have limited myself to 5 letters maximum per word. My next idea is, after the first minute, take the highest scoring board at that point and start looking for larger words. The (presumably flawed) idea is that a board with a higher number of small words may also contain a higher number of large words.

Very interesting notes about the GREP board!

VBA (average currently ranging 80-110 points, unfinished)
Here's my working process, but it's far from the best possible; my absolute best score found on any board after many test runs is around 120. There still needs to be some better general cleanup and I'm sure there are more efficiencies to be gained in a number of places.

2012.05.09:

Original posting

2012.05.10 - 2012.05.18:

Improved the scoring algorithm
Improved the pathfinding logic

2012.06.07 - 2012.06.12:

Reduced word limit to 6 from 8. Allows for more boards with smaller words. Appears to have made a slight improvement in average score. (10-15 or so boards checked per run vs. 1 to 2)
Following breadbox's suggestion, I've created a tree structure to house the word-list. This does speed up back-end checking of the words on a board significantly.
I played with changing the maximum word size (speed vs. score) and I haven't yet decided if 5 or 6 is a better option for me. 6 results in 100-120 total boards checked, while 5 results in 500-1000 (both of which are still far below the other examples provided so far).
Problem: After many successive runs, the process begins to slow, so there is still some memory to be managed.

This probably looks horrid to some of you, but as I said, WIP. I am very open to constructive criticism! Sorry for the very lengthy body...

Dice Class Module:
Option Explicit

Private Sides() As String

Sub NewDie(NewLetters As String)
    Sides = Split(NewLetters, ",")
End Sub

Property Get Side(i As Integer)
    Side = Sides(i)
End Property

Tree Class Module:
Option Explicit

Private zzroot As TreeNode

Sub AddtoTree(ByVal TreeWord As Variant)
Dim i As Integer
Dim TempNode As TreeNode

    Set TempNode = TraverseTree(TreeWord, zzroot)
    SetNode TreeWord, TempNode

End Sub

Private Function SetNode(ByVal Value As Variant, parent As TreeNode) As TreeNode
Dim ValChar As String
    If Len(Value) > 0 Then
        ValChar = Left(Value, 1)
        Select Case Asc(ValChar) - 96
            Case 1:
                Set parent.Node01 = AddNode(ValChar, parent.Node01)
                Set SetNode = parent.Node01
            Case 2:
                Set parent.Node02 = AddNode(ValChar, parent.Node02)
                Set SetNode = parent.Node02
            ' ... - Reduced to limit size of answer.
            Case 26:
                Set parent.Node26 = AddNode(ValChar, parent.Node26)
                Set SetNode = parent.Node26
            Case Else:
                Set SetNode = Nothing
        End Select

        Set SetNode = SetNode(Right(Value, Len(Value) - 1), SetNode)
    Else
        Set parent.Node27 = AddNode(True, parent.Node27)
        Set SetNode = parent.Node27
    End If
End Function

Function AddNode(ByVal Value As Variant, NewNode As TreeNode) As TreeNode
    If NewNode Is Nothing Then
        Set AddNode = New TreeNode
        AddNode.Value = Value
    Else
        Set AddNode = NewNode
    End If
End Function
Function TraverseTree(TreeWord As Variant, parent As TreeNode) As TreeNode
Dim Node As TreeNode
Dim ValChar As String
    If Len(TreeWord) > 0 Then
        ValChar = Left(TreeWord, 1)

        Select Case Asc(ValChar) - 96
            Case 1:
                Set Node = parent.Node01
            Case 2:
                Set Node = parent.Node02
            ' ... - Reduced to limit size of answer.
            Case 26:
                Set Node = parent.Node26
            Case Else:
                Set Node = Nothing
        End Select

        If Not Node Is Nothing Then
            Set TraverseTree = TraverseTree(Right(TreeWord, Len(TreeWord) - 1), Node)
            If Not TraverseTree Is Nothing Then
                Set TraverseTree = parent
            End If
        Else
            Set TraverseTree = parent
        End If
    Else
        If parent.Node27.Value Then
            Set TraverseTree = parent
        Else
            Set TraverseTree = Nothing
        End If
    End If
End Function

Function WordScore(TreeWord As Variant, Step As Integer, Optional parent As TreeNode = Nothing) As Integer
Dim Node As TreeNode
Dim ValChar As String
    If parent Is Nothing Then Set parent = zzroot
    If Len(TreeWord) > 0 Then
        ValChar = Left(TreeWord, 1)

        Select Case Asc(ValChar) - 96
            Case 1:
                Set Node = parent.Node01
            Case 2:
                Set Node = parent.Node02
            ' ... - Reduced to limit size of answer.
            Case 26:
                Set Node = parent.Node26
            Case Else:
                Set Node = Nothing
        End Select

        If Not Node Is Nothing Then
            WordScore = WordScore(Right(TreeWord, Len(TreeWord) - 1), Step + 1, Node)
        End If
    Else
        If parent.Node27 Is Nothing Then
            WordScore = 0
        Else
            WordScore = Step
        End If
    End If
End Function

Function ValidWord(TreeWord As Variant, Optional parent As TreeNode = Nothing) As Integer
Dim Node As TreeNode
Dim ValChar As String
    If parent Is Nothing Then Set parent = zzroot
    If Len(TreeWord) > 0 Then
        ValChar = Left(TreeWord, 1)

        Select Case Asc(ValChar) - 96
            Case 1:
                Set Node = parent.Node01
            Case 2:
                Set Node = parent.Node02
            ' ... - Reduced to limit size of answer.
            Case 26:
                Set Node = parent.Node26
            Case Else:
                Set Node = Nothing
        End Select

        If Not Node Is Nothing Then
            ValidWord = ValidWord(Right(TreeWord, Len(TreeWord) - 1), Node)
        Else
            ValidWord = False
        End If
    Else
        If parent.Node27 Is Nothing Then
            ValidWord = False
        Else
            ValidWord = True
        End If
    End If
End Function

Private Sub Class_Initialize()
    Set zzroot = New TreeNode
End Sub

Private Sub Class_Terminate()
    Set zzroot = Nothing
End Sub

TreeNode Class Module:
Option Explicit

Public Value As Variant
Public Node01 As TreeNode
Public Node02 As TreeNode
' ... - Reduced to limit size of answer.
Public Node26 As TreeNode
Public Node27 As TreeNode

Main Module:
Option Explicit

Const conAllSides As String = ";a,a,e,e,g,n;e,l,r,t,t,y;a,o,o,t,t,w;a,b,b,j,o,o;e,h,r,t,v,w;c,i,m,o,t,u;d,i,s,t,t,y;e,i,o,s,s,t;d,e,l,r,v,y;a,c,h,o,p,s;h,i,m,n,qu,u;e,e,i,n,s,u;e,e,g,h,n,w;a,f,f,k,p,s;h,l,n,n,r,z;d,e,i,l,r,x;"
Dim strBoard As String, strBoardTemp As String, strWords As String, strWordsTemp As String
Dim CheckWordSub As String
Dim iScore As Integer, iScoreTemp As Integer
Dim Board(1 To 4, 1 To 4) As Integer
Dim AllDice(1 To 16) As Dice
Dim AllWordsTree As Tree
Dim AllWords As Scripting.Dictionary
Dim CurWords As Scripting.Dictionary
Dim FullWords As Scripting.Dictionary
Dim JunkWords As Scripting.Dictionary
Dim WordPrefixes As Scripting.Dictionary
Dim StartTime As Date, StopTime As Date
Const MAX_LENGTH As Integer = 5
Dim Points(3 To 8) As Integer

Sub Boggle()
Dim DiceSetup() As String
Dim i As Integer, j As Integer, k As Integer

    StartTime = Now()

    strBoard = vbNullString
    strWords = vbNullString
    iScore = 0

    ReadWordsFileTree

    DiceSetup = Split(conAllSides, ";")

    For i = 1 To 16
        Set AllDice(i) = New Dice
        AllDice(i).NewDie "," & DiceSetup(i)
    Next i

    Do While WithinTimeLimit

        Shuffle

        strBoardTemp = vbNullString
        strWordsTemp = vbNullString
        iScoreTemp = 0

        FindWords

        If iScoreTemp > iScore Or iScore = 0 Then
            iScore = iScoreTemp
            k = 1
            For i = 1 To 4
                For j = 1 To 4
                    strBoardTemp = strBoardTemp & AllDice(k).Side(Board(j, i)) & "  "
                    k = k + 1
                Next j
                strBoardTemp = strBoardTemp & vbNewLine
            Next i
            strBoard = strBoardTemp
            strWords = strWordsTemp

        End If

    Loop

    Debug.Print strBoard
    Debug.Print strWords
    Debug.Print iScore & " points"

    Set AllWordsTree = Nothing
    Set AllWords = Nothing
    Set CurWords = Nothing
    Set FullWords = Nothing
    Set JunkWords = Nothing
    Set WordPrefixes = Nothing

End Sub

Sub ShuffleBoard()
Dim i As Integer

    For i = 1 To 16
        If Not WithinTimeLimit Then Exit Sub
        Board(Int((i - 1) / 4) + 1, 4 - (i Mod 4)) = Int(6 * Rnd() + 1)
    Next i

End Sub

Sub Shuffle()
Dim n As Long
Dim Temp As Variant
Dim j As Long

    Randomize
    ShuffleBoard
    For n = 1 To 16
        If Not WithinTimeLimit Then Exit Sub
        j = CLng(((16 - n) * Rnd) + n)
        If n <> j Then
            Set Temp = AllDice(n)
            Set AllDice(n) = AllDice(j)
            Set AllDice(j) = Temp
        End If
    Next n

    Set FullWords = New Scripting.Dictionary
    Set CurWords = New Scripting.Dictionary
    Set JunkWords = New Scripting.Dictionary

End Sub

Sub ReadWordsFileTree()
Dim FSO As New FileSystemObject
Dim FS
Dim strTemp As Variant
Dim iLength As Integer
Dim StartTime As Date

    StartTime = Now()
    Set AllWordsTree = New Tree
    Set FS = FSO.OpenTextFile("P:\Personal\english.txt")

    Points(3) = 1
    Points(4) = 1
    Points(5) = 2
    Points(6) = 3
    Points(7) = 5
    Points(8) = 11

    Do Until FS.AtEndOfStream
        strTemp = FS.ReadLine
        If strTemp = LCase(strTemp) Then
            iLength = Len(strTemp)
            iLength = IIf(iLength > 8, 8, iLength)
            If InStr(strTemp, "'") < 1 And iLength > 2 Then
                AllWordsTree.AddtoTree strTemp
            End If
        End If
    Loop
    FS.Close

End Sub

Function GetScoreTree() As Integer
Dim TempScore As Integer

    If Not WithinTimeLimit Then Exit Function

    GetScoreTree = 0

    TempScore = AllWordsTree.WordScore(CheckWordSub, 0)
    Select Case TempScore
        Case Is < 3:
            GetScoreTree = 0
        Case Is > 8:
            GetScoreTree = 11
        Case Else:
            GetScoreTree = Points(TempScore)
    End Select

End Function

Sub SubWords(CheckWord As String)
Dim CheckWordScore As Integer
Dim k As Integer, l As Integer

    For l = 0 To Len(CheckWord) - 3
        For k = 1 To Len(CheckWord) - l
            If Not WithinTimeLimit Then Exit Sub

            CheckWordSub = Mid(CheckWord, k, Len(CheckWord) - ((k + l) - 1))

            If Len(CheckWordSub) >= 3 And Not CurWords.Exists(CheckWordSub) Then
                CheckWordScore = GetScoreTree

                If CheckWordScore > 0 Then
                    CurWords.Add CheckWordSub, CheckWordSub
                    iScoreTemp = iScoreTemp + CheckWordScore
                    strWordsTemp = strWordsTemp & CheckWordSub & vbNewLine
                End If

                If Left(CheckWordSub, 1) = "q" Then
                    k = k + 1
                End If
            End If

        Next k
    Next l

End Sub

Sub FindWords()
Dim CheckWord As String
Dim strBoardLine(1 To 16) As String
Dim Used(1 To 16) As Boolean
Dim i As Integer, j As Integer, k As Integer, l As Integer, m As Integer, n As Integer
Dim StartSquare As Integer
Dim FullCheck As Variant

    n = 1
    For l = 1 To 4
        For m = 1 To 4
            If Not WithinTimeLimit Then Exit Sub
            strBoardLine(n) = AllDice(n).Side(Board(m, l))
            n = n + 1
        Next m
    Next l

    For i = 1 To 16
        For k = 1 To 16

            If Not WithinTimeLimit Then Exit Sub
            If k Mod 2 = 0 Then
                For j = 1 To 16
                    Used(j) = False
                Next j

                Used(i) = True
                MakeWords strBoardLine, Used, i, k / 2, strBoardLine(i)
            End If

        Next k
    Next i

    For Each FullCheck In FullWords.Items
        SubWords CStr(FullCheck)
    Next FullCheck

End Sub

Function MakeWords(BoardLine() As String, Used() As Boolean, _
    Start As Integer, _
    Direction As Integer, CurString As String) As String
Dim i As Integer, j As Integer, k As Integer, l As Integer

    j = 0

    Select Case Direction
        Case 1:
            k = Start - 5
        Case 2:
            k = Start - 4
        Case 3:
            k = Start - 3
        Case 4:
            k = Start - 1
        Case 5:
            k = Start + 1
        Case 6:
            k = Start + 3
        Case 7:
            k = Start + 4
        Case 8:
            k = Start + 5
    End Select

    If k >= 1 And k <= 16 Then
        If Not WithinTimeLimit Then Exit Function

        If Not Used(k) Then
            If ValidSquare(Start, k) Then
                If Not (JunkWords.Exists(CurString & BoardLine(k))) And Not FullWords.Exists(CurString & BoardLine(k)) Then
                    Used(k) = True
                    For l = 1 To MAX_LENGTH
                        If Not WithinTimeLimit Then Exit Function
                        MakeWords = CurString & BoardLine(k)
                        If Not (JunkWords.Exists(MakeWords)) Then
                            JunkWords.Add MakeWords, MakeWords
                        End If
                        If Len(MakeWords) = MAX_LENGTH And Not FullWords.Exists(MakeWords) Then
                            FullWords.Add MakeWords, MakeWords
                        ElseIf Len(MakeWords) < MAX_LENGTH Then
                            MakeWords BoardLine, Used, k, l, MakeWords
                        End If
                    Next l
                    Used(k) = False
                End If
            End If
        End If
    End If

    If Len(MakeWords) = MAX_LENGTH And Not FullWords.Exists(MakeWords) Then
        FullWords.Add MakeWords, MakeWords
        Debug.Print "FULL - " & MakeWords
    End If

End Function

Function ValidSquare(StartSquare As Integer, EndSquare As Integer) As Boolean
Dim sx As Integer, sy As Integer, ex As Integer, ey As Integer

    If Not WithinTimeLimit Then Exit Function

    sx = (StartSquare - 1) Mod 4 + 1
    ex = (EndSquare - 1) Mod 4 + 1

    sy = Int((StartSquare - 1) / 4 + 1)
    ey = Int((EndSquare - 1) / 4 + 1)

    ValidSquare = (sx - 1 <= ex And sx + 1 >= ex) And (sy - 1 <= ey And sy + 1 >= ey) And StartSquare <> EndSquare

End Function

Function WithinTimeLimit() As Boolean
    StopTime = Now()
    WithinTimeLimit = (Round(CDbl(((StopTime - StartTime) - Int(StopTime - StartTime)) * 86400), 0) < 120)
End Function

I haven't looked through the code, but 50 points is ridiculuously low. I've played randomly generated boards with scores over 1000 (using SOWPODS - the word list supplied may be less extensive). You might want to check for a sign error!

@PeterTaylor Thanks for the suggestion. I know that score's much too low, and I know that part of the problem lies in the fact that I can see obvious words being missed...

@PeterTaylor Also, for the record, I'm continually posting my progress, rather than wait for my final product, since nobody else has taken a stab at it yet. I would like to keep the question somewhat alive until that happens.

I should also note that this is not being run on the fastest machine out there, so that doesn't help, either.

@PeterTaylor I was actually not aware of the SOWPODS list (which happens to be 5.6x bigger than the list I've identified for use). Thanks - I'll not be updating the question, however.

@Gaffi 10 seconds to compute the score? That's 9.999 seconds too long. You have to rethink your code. If you refuse to turn your wordlist into a tree, then at least do this: Make a list (hashtable, whatever) of all the two-letter prefixes. Then when you start to follow a path on the board, if the first two letters aren't in the list, skip that entire subtree of possible paths. Again, building the full tree is best, but the two-letter prefix list will help and is very cheap to make.

@breadbox I generally won't refuse to do anything. However, if I don't know how, I'm kind of at a loss. i.e. hastables (which I have used in VBA) are not built-in, so I've always had to use third-party code/libraries to get that kind of functionality. Unfortunately, I'm not proficient enough to do this on my own. The two letter prefix idea is a good one though, and I will look at implementing that. Thanks for your input!

@breadbox I looked into setting up a binary tree following this tutorial (converted from .NET to VBA), but it takes 12 seconds to read the word list vs. less than 1 for a Collection/Dictionary. I did not test it for extraction speed yet.

@Gaffi Note that what I'm describing is NOT a binary tree, because each node can have more than 2 children, up to 26. It's actually a trie, or what is sometimes called a DAWG but without the size-optimization. Building a trie shouldn't take that long (though what do I know about VBA), but even if it takes 12 seconds you'll still be ahead of the game after your second board. If you can read C code you could look at the createdictionary() function in my submission for further guidance.

@breadbox Point taken; thanks for the links. I imagine I can adapt my binary implementation up to 26 letters without much effort, though VBA is just generally not the fastest code around...

@Gaffi Nice improvement. But don't stop there!

Quick look at size of the search space.
   16! => 20922789888000 Dice Permutations
(6^16) =>  2821109907456 Face Permutations
 59025489844657012604928000 Boggle Grids

Reducing to exclude the repetition on each die.
              16! => 20922789888000 Dice Permutations
(4^4)*(5^6)*(6^5) => 31104000000 Unique Face Permutations
   650782456676352000000000 Boggle Grids

@breadbox store the dictionary as an Hash Table O(1) checking.
EDIT
Best Board (I've witnessed so far)
L  E  A  N
S  E  T  M
T  S  B  D
I  E  G  O

Score: 830
Words: 229
SLEETIEST  MANTELETS
MANTEELS  MANTELET  MATELESS
MANTEEL  MANTELS  TESTEES  BETISES  OBTESTS  OBESEST
SLEETS  SLEEST  TESTIS  TESTES  TSETSE  MANTES  MANTEL  TESTAE  TESTEE
STEELS  STELES  BETELS  BESETS  BESITS  BETISE  BODGES  BESEES  EISELS
GESTES  GEISTS  OBTEST
LEANT  LEATS  LEETS  LEESE  LESES  LESTS  LESBO  ANTES  NATES  SLEET  SETAE
SEATS  STIES  STEEL  STETS  STEAN  STEAM  STELE  SELES  TAELS  TEELS  TESTS
TESTE  TELES  TETES  MATES  TESTA  TEATS  SEELS  SITES  BEETS  BETEL  BETES
BESET  BESTS  BESIT  BEATS  BODGE  BESEE  DOGES  EISEL  GESTS  GESTE  GESSE
GEITS  GEIST  OBESE
LEAN  LEAT  LEAM  LEET  LEES  LETS  LEST  LESS  EATS  EELS  ELSE  ETNA  ESES
ESTS  ESSE  ANTE  ANTS  ATES  AMBO  NATS  SLEE  SEEL  SETA  SETS  SESE  SEAN
SEAT  SEAM  SELE  STIE  STET  SEES  TAEL  TAES  TEEL  TEES  TEST  TEAM  TELE
TELS  TETS  TETE  MATE  MATS  MAES  TIES  TEAT  TEGS  SELS  SEGO  SITS  SITE
BEET  BEES  BETA  BETE  BETS  BEST  BEAN  BEAT  BEAM  BELS  BOGS  BEGO  BEGS
DOGE  DOGS  DOBS  GOBS  GEST  GEIT  GETS  OBES
LEA  LEE  LET  LES  EAN  EAT  EEL  ELS  ETA  EST  ESS  ANT  ATE  NAT  NAE  NAM
SEE  SET  SEA  SEL  TAN  TAE  TAM  TEE  TES  TEA  TEL  TET  MNA  MAN  MAT  MAE
TIE  TIS  TEG  SEG  SEI  SIT  BEE  BET  BEL  BOD  BOG  BEG  DOG  DOB  ITS  EGO
GOD  GOB  GET  OBS  OBE
EA  EE  EL  ET  ES  AN  AT  AE  AM  NA  ST  TA  TE  MA
TI  SI  BE  BO  DO  IT  IS  GO  OD  OB

Get me a machine with that much RAM and we'll talk.

You need to divide the dice permutations by 8 to account for the symmetries of the square. Also, how do you get (4^4)(5^6)(6^5)? I make it (4^3)(5^7)(6^6), for a total searc space of just over 2^79.

@Peter Taylor : You're right.
I must have deleted one to many, when do the unique faces.
I think we can agree there is 83 unique faces, (excluding repeats across die). Pick any 16 without repeats.
'83 x 82 x 81 x 80 x 79 x 78 x 77 x 76 x 75 x 74 x 73 x 72 x 71 x 70 x 69 x 68'
Approx: 1.082 x (10^30) ==> ~2^100
What ever it is, its a big number.

@AdamSpeight I originally assumed that your comment about storing the dictionary as a hashtable was just a joke, and so I basically ignored it. My apologies. A proper response would be: Actually, a hashtable is a lousy data structure for this problem. It can only answer the question "is X a valid word?", so you have to build all possible strings in order to find the words. A DAWG lets you ask "is X a prefix of any valid word? and if so, what letters can follow it?" This allows you to prune the search space to a tiny tiny fraction of its total size.

Hashtable is terrible as it prevents you culling word fragments that will never become complete words (dicttree.ceiling(fragment).startsWith(fragment)). Although any given boggle board has many millions of potential words, you can throw out a huge portion of them after 2-3 letters have been strung together. Tree traversal is slower than hashtable lookup, but the tree allows you to sidestep 99+ percent of the work through backtracking.

My entry is over here on Dream.In.Code ~30ms per a board search (on a 2 core machine, should be quicker with more cores)

Still looking into it, but your first link  on that page is missing the : in http://. ;-)

Very nice. I'm going to try to steal that for myself as a learning experience. .NET to VBA isn't too hard.

Would you mind updating the answer to include you average score when running the ISPELL list (not SOWPODS)? That is part of the challenge, and I'm interested to see how your results compare to breadbox's.