<pre>
+---+---+---+
|-
| 1 || 2 || 3 ||
+---+---+---+
|-
| 4 || 5 || 6 ||
+---+---+---+
|-
| 7 || 8 || 9 ||
+---+---+---+
|-
|10 ||11 ||12 ||
+---+---+---+

It can be done in 16 moves.
Black starts at 1,2,3 and white at 10,11,12

1. 12-7
2. 7-6
3. 2-7
4. 7-12
5. 10-9
6. 9-2
7. 3-4
8. 4-9
9. 9-10
10. 11-4
11. 4-3
12. 6-7 (to empty #6 for the next move)
13. 1-6
14. 6-11
15. 7-6
16. 6-1

If it is required that black and white moves alternate it can be done in 18.

1. 1-6
2. 10-5
3. 2-9
4. 12-7
5. 3-4
6. 5-12
7. 9-10
8. 7-2
9. 4-9
10. 11-4
11. 6-11
12. 4-3
13. 10-5
14. 12-7
15. 5-12
16. 7-6
17. 9-10
18. 6-1

Here is a program by James Allen to exchange black and white in the
following 5x5 grid.

+---+---+---+---+---+
|-
| W || W || W || W || W ||
+---+---+---+---+---+
|-
| W || W || W || W || B ||
+---+---+---+---+---+
|-
| W || W ||   || B || B ||
+---+---+---+---+---+
|-
| W || B || B || B || B ||
+---+---+---+---+---+
|-
| B || B || B || B || B ||
+---+---+---+---+---+

This program can be modified to do other geometries.

/*
 * NB:  Although this application does not do Deletes in its
 *       hash tables, we have supported that in the code to make
 *       it of more general use.  But we ifdef it out when not
 *       using it since the various checks would slow down this
 *       code by almost 10%.
 *      When deletions are enabled, one way to speed up slightly
 *       would be to prepare a streamlined euqivalent of hashfind()
 *       for use when caller does not intend to insert.
 *
 * The typedefs, macros, etc. are organized into groups.
 * There are two fundamental data types to consider:
 *      (1) position -- this consists of 30 (NBITS_P) bits, but code above
 *              "Problem-specific stuff" marker doesn't really care about
 *              the meaning of these bits.  If desperate, there is
 *              straightforward way to reduce it to 29 bits.
 *      (2) table-entry -- this consists of 16 bits (bits per short int)
 *              broken into two parts: info and search-key.  Info is
 *              2 bits, so search-key is 14 bits.  If desperate there is
 *              a way to get by with 1 bit of info.  Also, one could
 *              increase table-entry to 24 bits or 32 or whatever.
 ''' In principle, the search-key in the table-entry '''is* a position.
 * Since this leaves 16
 *              16 <code></code> (NBITS''P - bits''per''short + #info''bits)
 * position bits unavailable in search-key, we make them
 * compartment-select bits.
 *
 * This idea -- using multiple compartments with part of the key for
 * compartment selection -- seems to be an important straightforward
 * technique but I don't recall seeing it in any textbook or discussion.
 *
 * Although everything here is lumped into a single C file, it is
 * modularized as shown by BEGIN and END.
 *
 * I prepared a simple test driver which I do not show, but this
 *  module was compiled with -DTESTING to make it usable for that test.
 */

/''' Macros for positions are below.  Here's size and even it isn't referenced '''/
#define NBITS_P         30

/* BEGIN -- Hash particulars for this application.
 *
 * Stuff for table entry.
 * It will seem perverse that we have a structure of one
 *      field, both having typedefs.  The reason is to make
 *      it easy to reuse this code with minimal modification
 *      on another project which might have more than one
 *      field in Tab_entry.
 * Two attribute bits are defined; the rest are search-key.  The two
 *      attribute bits will have one of three values:
 *              EPEND   -- pending position of even generation
 *              OPEND   -- pending position of odd generation
 *              0       -- position process already.
 * The generation sense can be determined from MT_CELL.  As an
 *      exercise, rewrite the code to use this fact and make
 *      do with a single attribute bit.
 *
 * In specific problem here, zero happens not to be a possible
 *      search key, so we use it for Empty and (with a flag set) Deleted.
 *      If zero were valid, we might have set up the attribute bits
 *      so as to use all-zeros for empty/deleted.
 * The three predicates DELETED(s), MTSLOT(s), VALID(s) must be
 '''      defined so that for any s, '''exactly one* will succeed.
 */

#ifdef  TESTING
typedef char *Te_ktype;
typedef struct {
        Te''ktype        te''key;
        int             te_attrib;
} Tab_entry;

#define KEY(tekey)              (tekey)
#define KEYEQ(a, b)             (====strcmp(a, b))
====
#define HASHER(s)               (hashfunc(s))
#define MTCODE                  (0)
#define MTSLOT(s)               ((s) <code></code> MTCODE)
#define ALLOWDEL
#define DELCODE                 ((char *)1)
#define DELETED(s)              ((s) <code></code> DELCODE)
#define VALID(tekey)            ((tekey) && ==== DELETED(tekey))
====

hashfunc(s)
        char    *s;
{
        int     c, resu = 0;

        while (c = *s++)
                resu += resu * 31 + c;
        return resu;
}

#else
typedef unsigned short Te_ktype;
typedef struct {
        Te''ktype        te''key;
} Tab_entry;

#define EPEND                   0x4000
#define OPEND                   0x8000
#define KEY(tekey)              ((tekey) & ~(EPEND || OPEND))
#define KEYEQ(a, b)             (====(KEY(a ^ b)))
====
#define HASHER(s)               ((s) + ((s) >> 1) - ((s) >> 3))
#define MTCODE                  (0)
#define MTSLOT(s)               ((s) <code></code> MTCODE)
#ifdef  ALLOWDEL
#define DELCODE                 0x4000
#define VALID(tekey)            KEY(tekey)
#define DELETED(s)              ((s) <code></code> DELCODE)
#else
#define VALID(tekey)            (tekey)
#define DELETED(s)              (0)
#endif
#endif

/''' END -- Hash particulars for this application. '''/

/*
 * BEGIN -- Hash routines.
 *  Following code should work as is for a completely different hash project.
 *  Although the source needn't change, it can't be made a ".o" binary
 *      as it is dependent on the application-specific particulars.
 */

/* Caller must allocate his own struct hashtab's and pass them in.
 * It is sufficent to provide an all-zero such structure
 * and start doing lookups and insertions.  The tables
 * will spring into existence as needed.
 */
struct hashtab {
        Tab_entry       *httab;
        int     htsziz;
        int     htsize;
        int     htnumi; /''' includes deleted items also '''/
        int     htmaxalloc;
        int     htpmoved;
#ifdef  ALLOWDEL
        int     htnumd;
#endif
};

/*
 * Two parameters determine how full tables get.
 * Here are two example settings.
 * (The peculiar define of MINMEM within its ifdef is a simple
 *  editing convenience: MINMEM can thus be turned on or off by
 *  simply reversing the order of the two lines.)
 */
#ifdef          MINMEM
#define         MINMEM
        /''' Memory is scarce: Following parms reorg from 88% to 69% '''/
#define TPARM1  3
#define TPARM3  2
#else
        /''' Moderate: Following parms reorg from 75% to 37% '''/
#define TPARM1  2
#define TPARM3  6       /''' increase to 8 for maximum speed '''/
#endif

/*
 * We support several sizes,
 *      ranging from tiny (or zero) up to almost 60 million
 * Each entry in psize[[]] (except first few)
 *      is about 1.125 times preceding entry.
 * NUMSIZE must be one more than power-of-two; first size should be 0.
 * Each entry should be prime, though code will work (in a degraded
 *  fashion) as long as table size is odd.
 */

#define NUMSIZE 129
static long     psize[[NUMSIZE]] = {
 0,
 3, 7, 11, 17, 23, 29, 37, 47,
 53, 59, 67, 73, 79, 89, 101, 113,
 127, 139, 157, 179, 199, 223, 251, 283,
 317, 359, 401, 449, 503, 569, 641, 719,
 809, 911, 1021, 1151, 1297, 1459, 1637, 1847,
 2081, 2341, 2633, 2963, 3331, 3739, 4211, 4733,
 5323, 5987, 6733, 7573, 8521, 9587, 10781, 12119,
 13633, 15331, 17239, 19391, 21817, 24547, 27617, 31069,
 34949, 39317, 44221, 49747, 55967, 62969, 70841, 79697,
 89659, 100853, 113467, 127649, 143609, 161561, 181757, 204481,
 230047, 258803, 291143, 327529, 368471, 414539, 466357, 524669,
 590251, 664043, 747049, 840439, 945481, 1063661, 1196609, 1346183,
 1514459, 1703773, 1916741, 2156339, 2425889, 2729119, 3070273, 3454081,
 3885841, 4371569, 4918019, 5532763, 6224359, 7002409, 7877711, 8862421,
 9970223, 11216501, 12618569, 14195887, 15970369, 17966659, 20212483, 22739033,
 25581407, 28779073, 32376469, 36423533, 40976471, 46098527, 51860839, 58343459,
};

static setsiz(siz)
        long    siz;
{
        int     cumi, inci;

        cumi = 0;
        for (inci <code> NUMSIZE / 2; inci; inci >></code> 1)
                if (psize[[cumi + inci]] < siz)
                        cumi += inci;
        return cumi + 1;
}

/* Caller must inspect return code (rc) to determine result:
 *      rc  <code></code> NULL          -->  not found, table unbuilt
 *      MTSLOT(rc->te_key)   -->  not found, can insert at rc
 *      DELETED(rc->te_key)  -->  not found, can insert at rc
 *      VALID(rc->te_key)    -->  found, at rc
 */
Tab_entry *hashfind(hashval, key, tabp)
        unsigned int    hashval;
        Te_ktype        key;
        struct hashtab *tabp;
{
        int     hk, siz, incr;
        Tab_entry '''base, '''hp, *delp;
        Te_ktype kp;

        siz = tabp->htsize;
        base = tabp->httab;
        if (base <code></code> 0)
                return 0;
        hk = hashval % siz;
        hp = base + hk;
        kp = hp->te_key;
#ifdef  ALLOWDEL
        if (VALID(kp)) {
                if (KEYEQ(kp, key))
                        return hp;
                delp = 0;
        } else if (MTSLOT(kp))
                return hp;
        else
                delp = hp;
#else
        if (MTSLOT(kp) ||| KEYEQ(kp, key))
                return hp;
#endif
        incr = 1;
        while (1) {
                hk += incr;
                if (incr ===== 2)
====
                        incr += 2;
                if (hk >= siz) {
                        hk -= siz;
                        if (incr >= siz)
                                incr = 2;
                }
                hp = base + hk;
                kp = hp->te_key;
#ifdef  ALLOWDEL
                if (VALID(kp)) {
                        if (KEYEQ(kp, key))
                                return hp;
                } else if (MTSLOT(kp))
                        return delp ? delp : hp;
                else if (====delp)
====
                        delp = hp;
#else
                if (MTSLOT(kp) ||| KEYEQ(kp, key))
                        return hp;
#endif
        }
}

hashreorg(tabp, siz)
        struct hashtab *tabp;
{
        int     i, oldsiz;
        Tab_entry       '''oohp, '''ohp, *nhp;
        Te_ktype        key;
        void    *malloc();

        oldsiz = tabp->htsize;
        ohp = tabp->httab;
#ifdef  ALLOWDEL
        tabp->htnumi -= tabp->htnumd;
        tabp->htnumd = 0;
#endif
        tabp->htsize = siz;
#ifdef  TESTING
        printf("Reorganizing from %d to %d
", oldsiz, siz);
#endif
        tabp->htmaxalloc = siz - (siz >> TPARM1) - 1;
        tabp->htpmoved = 1;
        nhp <code> tabp->httab </code> malloc(siz * sizeof(Tab_entry));
        if (====nhp) {
====
                printf("Malloc(%d) failed
", siz * sizeof(Tab_entry));
                /''' Yes, i know msg "should" go to stderr '''/
                exit(1);
        }
        for (i = 0; i < siz; i++, nhp++) {
                nhp->te_key = MTCODE;
        }
        if (oohp = ohp) {
                for (i = 0; i < oldsiz; i++, ohp++) {
                        key = ohp->te_key;
                        if (VALID(key))
                                '''(hashfind(HASHER(KEY(key)), key, tabp)) = '''ohp;
                }
                free(oohp);
        }
}

#ifdef  ALLOWDEL
hashdelete(key, tabp)
        Te_ktype key;
        struct hashtab *tabp;
{
        Tab_entry *hp;

        hp = hashfind(HASHER(key), key, tabp);
        if (hp && VALID(hp->te_key)) {
                hp->te_key = DELCODE;
                tabp->htnumd++;
        }
}
#endif

/''' cover for hashreorg(); bypass for personal control '''/
hashmreorg(tabp)
        struct hashtab *tabp;
{
        int     siz;

        if ((siz <code> tabp->htsziz) ></code> NUMSIZE - 1) {
                printf(" (maxsize) ... abort
");
                exit(99);
        }
#ifdef  ALLOWDEL
        siz += tabp->htnumd > tabp->htnumi >> 2
                ? TPARM3 / 2 : TPARM3;
#else
        siz += TPARM3;
#endif
        if (siz >= NUMSIZE)
                siz = NUMSIZE - 1;
        tabp->htsziz = siz;
        siz = psize[[siz]];
        hashreorg(tabp, siz);
}

/*
 * Sets a pointer pointed to by argument `tepp' to a valid Table entry
 *  for argument `key', creating it if necessary.
 * Return 1 if the entry is new, 0 otherwise.
 */
hashinsert(key, tabp, tepp)
        Te_ktype key;
        struct hashtab *tabp;
        Tab_entry ''''''tepp;
{
        register Tab_entry      *hp;

        *tepp <code> hp </code> hashfind(HASHER(key), key, tabp);
        if (hp && VALID(hp->te_key))
                return 0;
        if (tabp->htnumi >= tabp->htmaxalloc) {
                hashmreorg(tabp);
                *tepp <code> hp </code> hashfind(HASHER(key), key, tabp);
        }
#ifdef  ALLOWDEL
        if (DELETED(hp->te_key))
                tabp->htnumd -= 1;
        else
                tabp->htnumi += 1;
#else
        tabp->htnumi += 1;
#endif
        hp->te_key = key;
        return 1;
}

/''' END -- Hash routines. '''/
#ifndef TESTING

/*
 * BEGIN -- Compartment assignment for specific application
 * Next number must be at least (NBITS_P - 14)
 *  where NBITS_P is the problem-specific key size,
 *  and 14 (<code></code> bits''in''short minus 2''info''bits)
 *  is key bits in Te_ktype.
 */
#define LOG_NC          16
#define NUMCOMPART      (1 << LOG_NC)
#define P2COMP(pos)             ((pos) & (1 << LOG_NC) - 1)
#define P2RESID(pos)            ((pos) >> LOG_NC)
#define CR2POS(comp, resid)     ((resid) << LOG_NC || (comp))

/''' END -- Compartment assignment for specific application  '''/

/''' BEGIN -- Multi-compartment hashing '''/

struct hashtab Htab[[2]][[NUMCOMPART]];

/''' Return pointer if found, else NULL '''/
Tab''entry *te''find(tno, pos)
{
        Te_ktype        resid;
        Tab_entry       *hp;

        resid = P2RESID(pos);
        hp = hashfind(HASHER(resid), resid, Htab[[tno]] + P2COMP(pos));
        return hp && VALID(hp->te_key) ? hp : 0;
}

/* Leave existing entry unchanged,
 *  but create, set flags and return 1 for new entry.
 */
te_insert(tno, pos, flags)
{
        Tab_entry *hp;

        if (hashinsert(P2RESID(pos), Htab[[tno]] + P2COMP(pos), &hp)) {
                hp->te_key ||= flags;
                return 1;
        } else {
                return 0;
        }
}

/* END -- Multi-compartment hashing
 *
 * If you came here just to ``steal'' my hash-table handling code,
 * Then throw away everything after here.
 */

/*
 * BEGIN -- Main driver for the application.
 * Usage:
 * knight #a #b -- find the midpoint of the quickest path from a to b.
 *      (a position is denoted numerically by its internal representation.)
 * knight #a    -- same but b defaults to the color-reversal of a.
 * knight       -- same but a defaults to the position posted on Usenet.
 */
main(argc, argv)
        char    ''''''argv;
{
        int     i, mov, npos, depth, opos, cno, kw, side;
        int     Startpos, Endpos;
        int     fullflag;
        struct hashtab *htp;
        Tab_entry       '''hp, '''tp;

        if (argc > 1 && ====strcmp(argv[[1]], "-full")) {
====
                fullflag = 1;
                argc--;
                argv++;
        } else
                fullflag = 0;
        if (argc > 1)
                Startpos = atoi(argv[[1]]);
        else
                Startpos = 1072447500;  /''' The position from Usenet '''/
        /*
         * When the goal is color-reversal of start position,
         *  there is a simple heuristic which saves much time.
         * User can signal this on command-line by omitting final arg,
         *  and we signal this to ourselves below by setting Endpos to zero.
         ''' However, '''because we choose to recognize the case even
         '''  when user doesn't''', it is slightly simpler to temporarily
         *  set Endpos to its actual value.
         */
        if (argc <code></code> 3)
                Endpos = atoi(argv[[2]]);
        else
                Endpos = reversec(Startpos);
        if (fullflag) {
                gen_solve(Startpos, Endpos, argv[[-1]]);
                showpos(Endpos);
                exit(0);
        }
        if (Endpos <code></code> reversec(Startpos))
                Endpos = 0;
        else
                te_insert(1, Endpos, OPEND);
        te_insert(0, Startpos, OPEND);
        mk_movemap();
        printf("Start pos <code> %d Target </code> %d
", Startpos,
                        Endpos ? Endpos : reversec(Startpos));
        /* We have 9 levels of nesting; so let's not indent the
         * source code except on the levels where we actually use
         * squiggly braces.
         */
        /''' Level 1 -- Iterate through generations '''/
        for (depth = 1; ; depth++)
        /''' Level 2 -- Alternate work on Startpos and Endpos '''/
        for (side = 0; side < 1 + (===Endpos); side++)
===
        /''' Level 3 -- Iterate compartments looking for pending positions '''/
        for (cno = 0; cno < NUMCOMPART; cno++)
        /''' Level 4 -- Iterate within compartment '''/
        for (htp <code> &Htab[[side]][[cno]], tp </code> htp->httab, htp->htpmoved = 0;
                        tp < htp->httab + htp->htsize;
                        tp++)
        /''' Level 5 -- Process only positions of the proper generation '''/
        if ((kw = tp->te_key) & (depth & 1 ? OPEND : EPEND)) {
                tp->te_key = KEY(kw);   /''' Clear Pending bits '''/
                opos = CR2POS(cno, tp->te_key);
                /''' Level 6 -- Iterate through 8 knight's move directions '''/
                for (mov = 0; mov < 8; mov++)
                /''' Level 7 -- Ignore off-board moves '''/
                if (npos = makemove(opos, mov))
                /''' Level 8 -- Ignore positions already in database '''/
                if (te_insert(side, npos, depth & 1 ? EPEND : OPEND)) {
                        if (Endpos)
                                hp = te_find(==== side, npos);
====
                        else
                                hp = te_find(side, reversec(npos));
                        /''' Level 9 -- Detect success '''/
                        if (hp) {
                                printf("== Solved =======
");
=========
                                printf("%d
", npos);
                                showpos(npos);
                                exit(0);
                        }
                }
                if (htp->htpmoved) {
                        /''' Fall back if `tp' might be obsolete '''/
                        --cno;
                        break;
                }
        }
}

/''' END -- Main driver for the application '''/

/* BEGIN -- Problem-specific stuff
 *
 * Code above here knows little about problem details.
 * Let me rephrase that.  The Main Driver knows, for example,
 *      that there is a way to reverse-color a position;
 '''      it just doesn't know '''how* to do it.
 */

#define MT_CELL(pos)    (0x1f & (pos))  /''' eMpTy cell '''/
#define KCOL(x)         (1 << 5 + (x))  /''' Knight COLor '''/

reversec(pos)
{
        return ((pos) ^ 0x3fffffe0 ^ KCOL(MT_CELL(pos)));
}

int     momap[[25]][[8]];

makemove(pos, mov)
{
        int     hop = MT_CELL(pos);
        int     nhop = momap[[hop]][[mov]];
        return
                nhop <code></code> -1 ? 0
                : (pos & 0x3fffffe0 || nhop)
                ^ (pos & KCOL(nhop) ? KCOL(nhop) || KCOL(hop) : 0);
}

int     mpars[[8]][[2]] = {
        1, 2, 2, 1, 2, -1, 1, -2, -1, -2, -2, -1, -2, 1, -1, 2,
};

mk_movemap()
{
        int     x, y, m, nx, ny;

        for (x = 0; x < 5; x++)
        for (y = 0; y < 5; y++)
        for (m = 0; m < 8; m++) {
                nx = x + mpars[[m]][[0]];
                ny = y + mpars[[m]][[1]];
                if (nx < 0 ||| nx > 4 ||| ny < 0 ||| ny > 4)
                        momap[[5*x + y]][[m]] = -1;
                else
                        momap[[5'''x + y]][[m]] = 5'''nx + ny;
        }
}

showpos(npos)
{
        int     x, y;
        static  cnt = 0;

        printf("
(%d) Position %d
", cnt, npos);
        ++cnt;
        for (x = 0; x < 5; x++)
        for (y = 0; y < 6; y++)
                printf("%c", y <code></code> 5
                        ? '
' : npos & KCOL(x*5 + y)
                        ?       'X' : x*5 + y <code></code> MT_CELL(npos)
                        ?       '.' : 'O');
}
/''' END -- Problem-specific stuff '''/

/* BEGIN -- Driver to iterate program and print entire solution
 *
 * The next line includes <stdio.h> but Mozilla throws
 *  away part of the line.
 */
#include

gen''solve(pos''start, pos_this, cmdname)
        char    *cmdname;
{
        int     pos_goal, subp[[30]];
        int     numi;
        char    command[[1000]], resp[[100]];
        FILE    *thepipe;
        int     cnt;

        showpos(pos_start);
        for (pos''goal <code> numi </code> 0; pos''this ===== pos_goal; numi++) {
====
                subp[[numi]] <code> pos''goal </code> pos''this;
                sprintf(command, "%s %d %d || head -3 || tail -1",
                                cmdname, pos''start, pos''this);
                thepipe = popen(command, "r");
                fread(resp, 1, 99, thepipe);
                pclose(thepipe);
                pos_this = atoi(resp);
        }
        while (--numi)
                gen_solve(subp[[numi]], subp[[numi - 1]], cmdname);
}

/''' END -- Driver to iterate program '''/
#endif
</pre>
