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

/*

*

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

/*

/* Caller must allocate his own struct hashtab's and pass them in.

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

};

/*

  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

/*

  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);

}

/*

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

/*

  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,

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

/*

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

lib/DbaDatabase.php:134: Warning: dba_replace() [<a href='function.dba-replace'>function.dba-replace</a>]: You cannot perform a modification to a database without proper access