KE Solution

• ---+---+---+

| 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 == (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 */

1. 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.
• /

1. ifdef TESTING

typedef char *Te_ktype; typedef struct {

Te_ktype te_key; int te_attrib;

} Tab_entry;

1. define KEY(tekey) (tekey)
2. define KEYEQ(a, b) (!strcmp(a, b))
3. define HASHER(s) (hashfunc(s))
4. define MTCODE (0)
5. define MTSLOT(s) ((s) == MTCODE)
6. define ALLOWDEL
7. define DELCODE ((char *)1)
8. define DELETED(s) ((s) == DELCODE)
9. define VALID(tekey) ((tekey) && ! DELETED(tekey))

hashfunc(s)

char *s;

{

int c, resu = 0;

while (c = *s++)

resu += resu * 31 + c;

return resu;

}

1. else

typedef unsigned short Te_ktype; typedef struct {

Te_ktype te_key;

} Tab_entry;

1. define EPEND 0x4000
2. define OPEND 0x8000
3. define KEY(tekey) ((tekey) & (EPEND | OPEND))
4. define KEYEQ(a, b) (!(KEY(a ^ b)))
5. define HASHER(s) ((s) + ((s) >> 1) - ((s) >> 3))
6. define MTCODE (0)
7. define MTSLOT(s) ((s) == MTCODE)
8. ifdef ALLOWDEL
9. define DELCODE 0x4000
10. define VALID(tekey) KEY(tekey)
11. define DELETED(s) ((s) == DELCODE)
12. else
13. define VALID(tekey) (tekey)
14. define DELETED(s) (0)
15. endif
16. 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;

1. ifdef ALLOWDEL

   int htnumd;

2. 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.)
• /

1. ifdef MINMEM

2. define MINMEM

   /* Memory is scarce: Following parms reorg from 88% to 69% */

3. define TPARM1 3
4. define TPARM3 2

5. else

   /* Moderate: Following parms reorg from 75% to 37% */

6. define TPARM1 2
7. define TPARM3 6 /* increase to 8 for maximum speed */
8. 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.
• /

1. define NUMSIZE 129

static long psizeNUMSIZE? = {

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 = NUMSIZE / 2; inci; inci >>= 1)

if (psizecumi + inci? < siz)

cumi += inci;

return cumi + 1;

}

/* Caller must inspect return code (rc) to determine result

• rc == 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 == 0)

return 0;

hk = hashval % siz; hp = base + hk; kp = hp->te_key;

1. ifdef ALLOWDEL

   if (VALID(kp)) {

   if (KEYEQ(kp, key))

   return hp;

   delp = 0;

   } else if (MTSLOT(kp))

   return hp;

   else

   delp = hp;

2. else

   if (MTSLOT(kp) || KEYEQ(kp, key))

   return hp;

3. 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;

4. ifdef ALLOWDEL

   if (VALID(kp)) {

   if (KEYEQ(kp, key))

   return hp;

   } else if (MTSLOT(kp))

   return delp ? delp : hp;

   else if (!delp)

   delp = hp;

5. else

   if (MTSLOT(kp) || KEYEQ(kp, key))

   return hp;

6. 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;

1. ifdef ALLOWDEL

   tabp->htnumi -= tabp->htnumd; tabp->htnumd = 0;

2. endif

   tabp->htsize = siz;

3. ifdef TESTING

   printf("Reorganizing from %d to %d\n", oldsiz, siz);

4. endif

   tabp->htmaxalloc = siz - (siz >> TPARM1) - 1; tabp->htpmoved = 1; nhp = tabp->httab = malloc(siz * sizeof(Tab_entry)); if (!nhp) {

   printf("Malloc(%d) failed\n", 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);

   }

}

1. 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++;

}

}

1. endif

/* cover for hashreorg(); bypass for personal control */ hashmreorg(tabp)

struct hashtab *tabp;

{

int siz;

if ((siz = tabp->htsziz) >= NUMSIZE - 1) {

printf(" (maxsize) ... abort\n"); exit(99);

}

1. ifdef ALLOWDEL

   siz += tabp->htnumd > tabp->htnumi >> 2

   ? TPARM3 / 2 : TPARM3;

2. else

   siz += TPARM3;

3. endif

   if (siz >= NUMSIZE)

   siz = NUMSIZE - 1;

   tabp->htsziz = siz; siz = psizesiz?; 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 = hp = hashfind(HASHER(key), key, tabp);

if (hp && VALID(hp->te_key))

return 0;

if (tabp->htnumi >= tabp->htmaxalloc) {

hashmreorg(tabp);

• tepp = hp = hashfind(HASHER(key), key, tabp);

}

1. ifdef ALLOWDEL

   if (DELETED(hp->te_key))

   tabp->htnumd -= 1;

   else

   tabp->htnumi += 1;

2. else

   tabp->htnumi += 1;

3. endif

   hp->te_key = key; return 1;

}

/* END -- Hash routines. */

1. 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 (== bits_in_short minus 2_info_bits)
• is key bits in Te_ktype.
• /

1. define LOG_NC 16
2. define NUMCOMPART (1 << LOG_NC)
3. define P2COMP(pos) ((pos) & (1 << LOG_NC) - 1)
4. define P2RESID(pos) ((pos) >> LOG_NC)
5. define CR2POS(comp, resid) ((resid) << LOG_NC | (comp))

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

/* BEGIN -- Multi-compartment hashing */

struct hashtab Htab2?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, Htabtno? + 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), Htabtno? + 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(argv1?, "-full")) {

fullflag = 1; argc--; argv++;

} else

fullflag = 0;

if (argc > 1)

Startpos = atoi(argv1?);

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 == 3)

Endpos = atoi(argv2?);

else

Endpos = reversec(Startpos);

if (fullflag) {

gen_solve(Startpos, Endpos, argv-1?); showpos(Endpos); exit(0);

} if (Endpos == reversec(Startpos))

Endpos = 0;

else

te_insert(1, Endpos, OPEND);

te_insert(0, Startpos, OPEND); mk_movemap(); printf("Start pos = %d Target = %d\n", 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 = &Htabside?cno?, tp = 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 !!!\n"); printf("%d\n", 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.
• /

1. define MT_CELL(pos) (0x1f & (pos)) /* eMpTy cell */
2. define KCOL(x) (1 << 5 + (x)) /* Knight COLor */

reversec(pos) {

return ((pos) ^ 0x3fffffe0 ^ KCOL(MT_CELL(pos)));

}

int momap25?8?;

makemove(pos, mov) {

int hop = MT_CELL(pos); int nhop = momaphop?mov?; return

nhop == -1 ? 0 : (pos & 0x3fffffe0 | nhop) ^ (pos & KCOL(nhop) ? KCOL(nhop) | KCOL(hop) : 0);

}

int mpars8?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 + mparsm?0?; ny = y + mparsm?1?; if (nx < 0 || nx > 4 || ny < 0 || ny > 4)

momap5*x + y?m? = -1;

else

momap5*x + y?m? = 5*nx + ny;

}

}

showpos(npos) {

int x, y; static cnt = 0;

printf("\n(%d) Position %d\n", cnt, npos);

• +cnt;

for (x = 0; x < 5; x++) for (y = 0; y < 6; y++)

printf("%c", y == 5

? '\n' : npos & KCOL(x*5 + y) ? 'X' : x*5 + y == 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.
• /

1. include

gen_solve(pos_start, pos_this, cmdname)

char *cmdname;

{

int pos_goal, subp30?; int numi; char command1000?, resp100?; FILE *thepipe; int cnt;

showpos(pos_start); for (pos_goal = numi = 0; pos_this != pos_goal; numi++) {

subpnumi? = pos_goal = 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(subpnumi?, subpnumi - 1?, cmdname);

}

/* END -- Driver to iterate program */

1. endif