/* cc -g -O triangles.c -lm -o tri 2>&1 | more
nohup nice ./tri -x 1 -y 3 > tri.out 2>&1
#
#  Copyright (c) 2021 - 2022   David Albert Bagley, bagleyd AT verizon.net
#
#		   All Rights Reserved
#
#  Permission to use, copy, modify, and distribute this software and
#  its documentation for any purpose and without fee is hereby granted,
#  provided that the above copyright notice appear in all copies and
#  that both that copyright notice and this permission notice appear in
#  supporting documentation, and that the name of the author not be
#  used in advertising or publicity pertaining to distribution of the
#  software without specific, written prior permission.
#
#  This program is distributed in the hope that it will be "usable",
#  but WITHOUT ANY WARRANTY; without even the implied warranty of
#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
#
#  NOTE: you may THRASH your hard drive if you run out of RAM...
#  IF YOU HAVE LOTS OF DISK ACTIVITY AFTER EXECUTING THIS, TERMINATE IT!

https://kconrad.math.uconn.edu/blurbs/grouptheory/15puzzle.pdf

DO NOT even try for simple orders like 15 i.e.-c -x 1 -y 4, by the 37th
move it will eat all memory and freeze 16 Gig system for corners.
Highest I recommend (if you have this much memory (less if you do not))
is to solve an order 12 puzzle that is: -x 3 -y 2.
-x 1 -y 3 -> mirror 16 moves, CW/CCW 12, furthest 16
-x 2 -y 2 -> 16 moves, furthest 16
-x 3 -y 2 -> 56 moves, furthest 96
-c -x 1 -y 3 -> mirror 19 moves, CW/CCW 20, furthest 23
-c -x 2 -y 2 -> 19 moves, furthest 22
-c -x 3 -y 2 -> 43 moves, furthest 43

Option piecemeal -p may be able to extend this to find a good but probably
not best solution.
-p -x 1 -y 4 -> mirror 120, CW/CCW 94/92
-p -c -x 1 -y 4 -> mirror 58, CW/CCW 64/70

head /proc/meminfo
  MemTotal:       16058756 kB
head /proc/cpuinfo
  cpu MHz
*/

/* Converted from hexagons.c						 */

/* This program calculates the triangles puzzle problem.		 */
/* l (usually l = 4) tiles to be exchanged .				 */

/* Input:								 */
/* # of tiles								 */
/* # of nodes you expect it to take to search for a solution.		 */
/* Start and Final positions hard coded					 */

/* Output:							 	 */
/* The optimum route to exchange the tiles, but must obey rule		 */
/* no tile can go through another tile.					 */
/* As it  stands now a full solution will not be printed if number of    */
/* greater than X.						 	 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define FILE_NAME_LENGTH 1024
#define FALSE		0
#define TRUE		1
#define DOWN		0
#define UP		1
#define TR		0
#define RIGHT		1
#define BR		2
#define BL		3
#define LEFT		4
#define TL		5
#define COORD		6
#define TRBL		0
#define TLBR		1
#define ROW		2
#define ROW_TYPES	3
#define LOW		0
#define HIGH		1
#define POSSIBILITIES	COORD  /* maximum number of possible moves */
#define AREA		(sizeY * sizeY + 2 * sizeY * (sizeX - 1))
#define PREVAREA	((sizeY - 1) * (sizeY - 1) + 2 * (sizeY - 1) * (sizeX - 1))
#define BLANK		0
#define BLANK2		(AREA - 1)
#define CHAINS		3  /* for deleting nodes from hash table */
#define ARRAYTWEAKS	19 /* if <= tiles it will consult array for tweaks */
#define FREQBITS	22 /* sets frequency of what node & move its at now, for feedback */
#define NOFULLSOLUTION	10  /* lower this if you do not have the memory */

#define MINIMUM_MOVES 0
#define FURTHER 1
#define MODES 2

#define MIRROR 0
#define ROTATE_CCW 1
#define ROTATE_CW 2
#define STARTS 3

int corners = FALSE;
int debug = 0;
int mode = MINIMUM_MOVES;
int initial = MIRROR;
int arch = 8;

#define OPP_DIR(dir) ((dir + 3) % 6)
#define OPP_BLANK(blank) ((blank == BLANK) ? BLANK2 : BLANK)
#define MAX(i, j) (((i) > (j)) ? (i) : (j))
#define MIN(i, j) (((i) < (j)) ? (i) : (j))
#define CEIL(i) ((int) (i + 0.999999)) /* rough ceiling */
/* min bits needed to store a move */
#define MINBITS() CEIL(log2(AREA))
/* max tiles to store in a unit of memory */
#define MAXNUMINUNIT() ((int) (arch / MINBITS()))
/* min units to store all tiles */
#define MINUNITS() CEIL((double) AREA / MAXNUMINUNIT())

#ifdef ARCH128
#include <bitset>
using namespace std;
const int len = 128;
/* does not work past ? due to to_ulong() conversion, also slow */
#define TO_LONG(x) (x).to_ulong()
#define LONG bitset<len>
#else
#define TO_LONG(x) (x)
#define LONG unsigned long long
#endif

#define LOOKUP(x) ((units>1)?(TO_LONG(*x+((*(x+1))*253))%hashSize):\
	(TO_LONG(*x)%hashSize))

static int tiles;
static int size, hashSize;
static int bits, units, numInUnit, freqmask, loop;
static LONG bitmask, inputSize;

#define numTile(l) ((l >> 1) + ((l & 1) ? tiles : 0))
#define tileChar(l) ((l == BLANK) ? '-' : ((corners && l == BLANK2) ? '+' : ((l < 10) ? l + '0' : l - 10 + 'a')))
#define tileDigit(l) ((l == BLANK) ? 0 : ((corners && l == BLANK2) ? -1 : l))
#define SETBIT(t, p) (((LONG) (p)) << (bits * (t % numInUnit)))
#define setStart(t, p) startTiles[t / numInUnit] |= SETBIT(t, p)
#define setFinish(t, p) finishTiles[t / numInUnit] |= SETBIT(t, p)
#define setTile(t, p) shrunkPositionOfTile[t / numInUnit] |= SETBIT(t, p)

#define BITMASK ((1 << bits) - 1)
#define getStart(t) (((startTiles[t / numInUnit]) >> (bits * (t % numInUnit))) & BITMASK)
#define getFinish(t) (((finishTiles[t / numInUnit]) >> (bits * (t % numInUnit))) & BITMASK)
#define getTile(t) (((shrunkPositionOfTile[t / numInUnit]) >> (bits * (t % numInUnit))) & BITMASK)

/* move counts are for ROTATE_CCW */
/* ones marked 128 are currently beyond reach for 16G */
static int moves1d[MODES][ARRAYTWEAKS] = { /* 1x1 -15x1 */
  {0, 0, 1, 2, 3, 4, 5, 6, 7, 12, 9,
     11, 12, 13, 14, 15},
  {0, 1, 2, 3, 7, 5, 6, 7, 8, 18, 10,
     11, 12, 13, 14, 15}};
static int moves2dx2[MODES][ARRAYTWEAKS / 2 - 1] = { /* 2x2 - 8x2 */
  {6, 16, 20, 26, 42, 128, 128},
  {6, 21, 36, 55, 80, 128, 128}};
static int moves2dx3[MODES][ARRAYTWEAKS / 3 - 2] = { /* 3x3 */
  {128},
  {128}};
static int moves[MODES][ARRAYTWEAKS] = {
  {0, 1, 2, 3, 4, 5, 6, /*12 18*/ 20, 28, 26, 10,
     /*20 32*/ 42, 12, 128, 128, 128, 128, 128, 128},
  {0, 1, 2, 6, 4, 21, 6, /*15 19*/ 36, 31, 55, 10,
     /*36 40*/ 80, 12, 128, 128, 128, 128, 128, 128}};

static int hashSizes[ARRAYTWEAKS] = {31, 253, 1021, 65533, 131071,
  262141, 1048573, 8388607, 259000001, 259000001, 259000001,
  259000001, 259000001, 259000001, 259000001, 259000001};

/* These values are maximum for FURTHER, as may be more than one way to get there */
static int moveSizes[ARRAYTWEAKS] = {
  5, 5, 5, 5, 902, 902, 902, 902, 38495, 443553, 83000000, 
  83000000, 83000000, 83000000, 83000000, 83000000,
  83000000, 83000000, 83000000};
static long long minSizes[ARRAYTWEAKS] = { /* nodes */
  24, 24, 24, 24, 5040, 5040, 5040, 5040, 362880, 3628800, 2675020213LL,
  2675020213LL, 2675020213LL, 2675020213LL, 2675020213LL, 2675020213LL,
  2675020213LL, 2675020213LL, 2675020213LL};

/* corners move size 35117437, nodes 513021125 */


static LONG *nodeLog = NULL;
static char *backPoss = NULL;
static int *move = NULL, *backPath = NULL;
static int newNode = 0, currNode = 0;

/* hashless, debug level 2 check */
/* slow but good to check the hashes are working */
static int newBottom = 0;
static int unitMem;

typedef struct _hashtype {
	int node;
	struct _hashtype *next;
} hashtype;

static hashtype **hash;
static hashtype *chain[CHAINS];
static int hashNewIndex;
static long long c;

static int sizeX = 0, sizeY = 0;
static char *tileOfPosition = NULL; /* easier to see */
static char *startPosition = NULL, *finishPosition = NULL;
static char *positionOfTile = NULL;
static int startSpacePosition, finishSpacePosition;
static int startSpacePosition2, finishSpacePosition2;
static LONG *startTiles = NULL, *finishTiles = NULL;
static LONG *shrunkPositionOfTile = NULL;
static int blanks = 1;
static int frozenRows = 0, frozenTrBl = 0;
static char startFile[FILE_NAME_LENGTH] = "";
static char finishFile[FILE_NAME_LENGTH] = "";
static int piecemeal = 0;
static int redirect = 0;
static LONG intMask = 0;
static LONG *rowMask = NULL;
static LONG *trblMask = NULL;
static LONG *tlbrMask = NULL;

/* may not be a good idea */
static int spaceRow[2][ROW_TYPES];
static int space2Row[ROW_TYPES];
static int spacePosition[2] = {0, 1};
static int space2Position = 0;
static int spaceTile[2] = {BLANK, 1};
static int space2Tile = BLANK;

static int
SQRT(const int i)
{
	int j = 0;

	while (j * j <= i)
		j++;
	return (j - 1);
}

static void
swapChar(char *a, char *b)
{
	char c;

	c = *b;
	*b = *a;
	*a = c;
}

static void
swapInt(int *a, int *b)
{
	int c;

	c = *b;
	*b = *a;
	*a = c;
}

static int
fromRow(const int row)
{
	return (sizeX + row) * (sizeX + row) - (sizeX - 1) * (sizeX - 1);
}

static int
positionFromRow(int rowPosition, int posRow)
{
	return rowPosition + fromRow(posRow);
}

static int
positionInRow(int row, int trbl, int tlbr)
{
	return sizeX + trbl - tlbr + row - 1;
}

static int
toPosition(int row, int trbl, int tlbr)
{
	return positionFromRow(positionInRow(row, trbl, tlbr), row - 1);
}

static int
toOrient(int row, int trbl, int tlbr)
{
	return ((positionInRow(row, trbl, tlbr) % 2 == 1) ? DOWN : UP);
}

int
toRow(const int pos)
{
	return SQRT(pos + (sizeX - 1) * (sizeX - 1)) - sizeX + 1;;
}

/* Passing row so there is no sqrt calculation again */
int
toTrBl(const int pos, const int posRow)
{
	return ((pos - fromRow(posRow - 1)) >> 1);
}

int
toTlBr(const int pos, const int posRow)
{
	return ((fromRow(posRow) - pos - 1) >> 1);
}

static char *
dirToString(int i)
{
	switch (i) {
	case TR:
		return "TR";
	case RIGHT:
		return "RIGHT";
	case BR:
		return "BR";
	case BL:
		return "BL";
	case LEFT:
		return "LEFT";
	case TL:
		return "TL";
	default:
		return "?";
	}
}

static char *
dirToStringNoCorn(int i, int orient)
{
	switch (i) {
	case TR:
		if (orient)
			return "RIGHT";
		else
			return "UP";
	case RIGHT:
		return "RIGHT";
	case BR:
		if (orient)
			return "DOWN";
		else
			return "RIGHT";
	case BL:
		if (orient)
			return "DOWN";
		else
			return "LEFT";
	case LEFT:
		return "LEFT";
	case TL:
		if (orient)
			return "LEFT";
		else
			return "UP";
	default:
		return "?";
	}
}

static int
tileNFrom(int pos, int n, int rowType, int orient, int direction)
{
	if (rowType == ROW) /* This one is easy */
		return (pos + ((direction == UP) ? -n : n));
	else {
		int row = toRow(pos);
		int trbl = toTrBl(pos, row);
		int tlbr = toTlBr(pos, row);
		int offset1, offset2;

		if (direction == UP) {
			offset1 = -((n >> 1) + (n & 1));
			offset2 = -(n >> 1);
		} else {
			offset1 = n >> 1;
			offset2 = (n >> 1) + (n & 1);
		}
		if (rowType == TRBL)
			return ((orient == DOWN) ?
				toPosition(row + offset1, trbl, tlbr + offset2) :
				toPosition(row + offset2, trbl, tlbr + offset1));
		else /*if (rowType == TLBR)*/
			return ((orient == DOWN) ?
				toPosition(row + offset1, trbl + offset2, tlbr) :
				toPosition(row + offset2, trbl + offset1, tlbr));
	}
}

static int
tile1From(int pos, int rowType)
{
	int row = toRow(pos);
	int trbl = toTrBl(pos, row);
	int tlbr = toTlBr(pos, row);
	int orient = toOrient(row, trbl, tlbr);
/*printf("tile1From: pos%d, rowType%s, row%d, trbl%d, tlbr%d, orient%d\n",
pos, dirToString(rowType), row, trbl, tlbr, orient);*/
	if (orient == UP)
		switch(rowType) {
		case TR:
			if (row != sizeY - 1)
				return toPosition(row + 1, trbl, tlbr);
			else	
				return -1;
		case RIGHT:
			if (trbl != 0)
				return pos - 1;
			else
				return -1;
		case BR:
			if (trbl != 0)
				return pos - 1;
			else
				return -1;
		case BL:
/*FIXME */
			if (tlbr != 0)
				return pos + 1;
			else
				return -1;
		case LEFT:
			if (tlbr != 0)
				return pos + 1;
			else
				return -1;
		case TL:
			if (row != sizeY - 1)
				return toPosition(row + 1, trbl, tlbr);
			else
				return -1;
		default:
			return -1;
		}
	else
		switch(rowType) {
		case TR:
		case RIGHT:
			return pos - 1;
		case BR:
		case BL:
			return toPosition(row - 1, trbl, tlbr);
		case LEFT:
		case TL:
			return pos + 1;
		default:
			return -1;
		}
}

static void
freeHash(int index) {
	hashtype **oldChain = &(chain[index]);
	hashtype *ctemp = *oldChain;
	hashtype **oldHashPt;
	hashtype *htemp, *temp;

	while (ctemp) {
		oldHashPt = &(hash[LOOKUP(&nodeLog[ctemp->node * units])]);
		htemp = *oldHashPt;

		if ((*oldHashPt)->node == ctemp->node) {
			*oldHashPt = htemp->next;
			(void) free((void *) htemp);
			/* fnc++; */
		} else {
			while (htemp->next->node != ctemp->node)
				htemp = htemp->next;
			temp = htemp->next;
			htemp->next = temp->next;
			(void) free((void *) temp);
			/* fc++; */
		}
		*oldChain = (*oldChain)->next;
		(void) free((void *) ctemp);
		ctemp = *oldChain;
	}
}


#ifdef DEBUG
static void
printHash() {
	int i;

	for (i = 0; i < hashSize; i++) {
		hashtype *temp = hash[i];

		while (temp != NULL) {
			(void) printf("%d: %d %lld\n", i, temp->node,
				nodeLog[temp->node * units]);
			temp = temp->next;
		}
	}
}
#endif

static int
inHash() {
	LONG *psPOT = shrunkPositionOfTile;
	LONG *tempsPOT, *pnodeLog;
	hashtype *temp;
	int i;

	temp = hash[LOOKUP(psPOT)];
/*printf("temp %lld\n", temp);*/
	while (temp != NULL) {
		tempsPOT = psPOT;
		pnodeLog = &(nodeLog[temp->node * units]);
		for (i = 0; i < units; i++) {
/*printf("in here %lld %lld", *pnodeLog, *tempsPOT);*/
			if (*pnodeLog != *tempsPOT)
				goto HASHCONTINUE;
/*printf("in hash %lld %lld", *pnodeLog, *tempsPOT);*/
			pnodeLog++;
			tempsPOT++;
		}
		return TRUE;
HASHCONTINUE:   temp = temp->next;
	}
	return FALSE;
}

static void
memoryError(const char * string) {
	(void) fprintf(stderr, "Not enough memory for %s.\n", string);
	(void) fprintf(stderr, "Try a smaller number of nodes with -n.\n");
	(void) fprintf(stderr, "Exiting\n");
	exit(1);
}

static void
printTilesDigit(char * inTileOfPosition) {
	int position;
	char *ptOP = inTileOfPosition;

	int r = 0, oldR = -1, length = 0, space, temp;

	for (position = 0; position < AREA; position++) {
		if (oldR != r) {
			for (space = 0; space < sizeY - r - 1; space++)
				(void) fprintf(stderr, "    ");
			oldR = r;
		}
		(void) fprintf(stderr, "%2d", tileDigit(*ptOP));
		temp = (r + 1) * (r + 1) + 2 * (r + 1) * (sizeX - 1) - 1;
		if (position == temp) {
			(void) fprintf(stderr, "\n");
			r++;
		} else
			(void) fprintf(stderr, "  ");
		ptOP++;
	}
}

static void
printTiles(char * inTileOfPosition) {
	int position;
	char *ptOP = inTileOfPosition;

	int r = 0, oldR = -1, length = 0, space, temp;

	for (position = 0; position < AREA; position++) {
		if (oldR != r) {
			for (space = 0; space < sizeY - r - 1; space++)
				(void) printf("  ");
			oldR = r;
		}
		(void) printf("%c", tileChar(*ptOP));
		temp = (r + 1) * (r + 1) + 2 * (r + 1) * (sizeX - 1) - 1;
		if (position == temp) {
			(void) printf("\n");
			r++;
		} else
			(void) printf(" ");
		ptOP++;
	}
}

static void
printPositions(char * inPositionOfTile) {
	int tile;
	char *ppOT = inPositionOfTile;
	char *inTileOfPosition;

	/*printf("print Positions\n");*/
	if (!(inTileOfPosition = (char *) calloc(AREA,
			sizeof (char)))) {
		memoryError("printPositions");
	}
	for (tile = 0; tile < AREA; tile++)
		inTileOfPosition[inPositionOfTile[tile]] = tile;
	printTiles(inTileOfPosition);
	if (inTileOfPosition)
		(void) free((void *) inTileOfPosition);
}

static void
putInHash(int index, int node) {
	hashtype **oldHashPt = &(hash[LOOKUP(&nodeLog[node * units])]);
	hashtype **oldChain = &(chain[index]);
	hashtype *htemp = *oldHashPt;
	hashtype *ctemp = *oldChain;

	if (!(htemp = (hashtype *) malloc(sizeof (hashtype)))) {
		memoryError("adding to hash table");
	}
	htemp->node = node;
	if (*oldHashPt == NULL) {
		*oldHashPt = htemp;
		htemp->next = NULL;
		/* nc++; */
	} else {
		htemp->next = *oldHashPt;
		*oldHashPt = htemp;
		c++;
	}
	if (!(ctemp = (hashtype *) malloc(sizeof (hashtype)))) {
		memoryError("adding to chain");
	}
	ctemp->node = node;
	ctemp->next = *oldChain;
	*oldChain = ctemp;
}

static void
putCurrent(int node) {
	LONG *pnodeLog = &(nodeLog[node * units]);
	LONG *psPOT = shrunkPositionOfTile;
	int j;
	/*char *ppOT = positionOfTile;
	int i, j, shift, n = 0;

	for (j = 0; j < units; j++)
		shrunkPositionOfTile[j] = 0;
	for (i = 0; i < AREA; i++)
		setTile(i, positionOfTile[i]);
	for (;;) {
		shift = 0;
		*psPOT = 0;
		for (j = 0; j < numInUnit; j++) {
			*psPOT |= (((LONG) *ppOT) << shift);
			shift += bits;
			ppOT++;
			n++;
			if (n >= AREA) {
				*pnodeLog = *psPOT;
				return;
			}
		}*/
	for (j = 0; j < units; j++) {
		*pnodeLog = *psPOT;
		psPOT++;
		pnodeLog++;
	}
}

static void
calculateRows(int fromUpPosition, int fromDownPosition)
{
	int posRow = toRow(fromUpPosition);

	spacePosition[UP] = fromUpPosition;
	spacePosition[DOWN] = fromDownPosition;
	spaceRow[UP][ROW] = posRow;
	spaceRow[UP][TRBL] = toTrBl(fromUpPosition, posRow);
	spaceRow[UP][TLBR] = toTlBr(fromUpPosition, posRow);
	posRow = toRow(fromDownPosition);
	spaceRow[DOWN][ROW] = posRow;
	spaceRow[DOWN][TRBL] = toTrBl(fromDownPosition, posRow);
	spaceRow[DOWN][TLBR] = toTlBr(fromDownPosition, posRow);
}

static void
calculateRows2(int fromPosition)
{
	int posRow = toRow(fromPosition);

	space2Position = fromPosition;
	space2Row[ROW] = posRow;
	space2Row[TRBL] = toTrBl(fromPosition, posRow);
	space2Row[TLBR] = toTlBr(fromPosition, posRow);
}

static void
getCurrent(int node) {
	int i, j, shift, n = 0;
	LONG *pnodeLog = &(nodeLog[node * units]);
	LONG *psPOT = shrunkPositionOfTile;
	char *ptOP = tileOfPosition;
	char value;

	for (;;) {
		shift = 0;
		*psPOT = *pnodeLog;
		for (j = 0; j < numInUnit; j++) {
			value = (char) TO_LONG((((LONG) *psPOT) >> shift) &
				bitmask);
			*ptOP = value;
			/*tileOfPosition[n] = value;*/
			positionOfTile[value] = n;
			shift += bits;
			ptOP++;
			n++;
			if (n >= AREA) {
				return;
			}
		}
		pnodeLog++;
		psPOT++;
	}
}

static char
decideSwap() {
	if (initial == MIRROR && (corners || sizeY > 3))
		return ((sizeY & 1) == 1);
	return FALSE;
}

static void
setStartPosition() {
	int i, j, switch1, switch2;

	if (initial == MIRROR) {
		if (sizeY < 2) {
			for (i = 0; i < AREA; i++) {
				if (i == 0)
					startPosition[i] = 0;
				else if (corners && i == 1)
					startPosition[i] = AREA - 1;
				else
					startPosition[i] = i - ((corners) ? 2 : 1) + 1;
			}
			startSpacePosition = 0;
			if (corners)
				startSpacePosition2 = startSpacePosition + 1;
		} else if (!corners && sizeX == 1 && sizeY == 3) {
			startPosition[0] = 1;
			startPosition[1] = 4;
			startPosition[2] = 7;
			startPosition[3] = 6;
			startPosition[4] = 0;
			startPosition[5] = 5;
			startPosition[6] = 3;
			startPosition[7] = 2;
			startPosition[8] = 8;
			startSpacePosition = fromRow(sizeY - 2);
		} else if (!corners && sizeX == 2 && sizeY == 2) {
			startPosition[0] = 3;
			startPosition[1] = 6;
			startPosition[2] = 5;
			startPosition[3] = 0;
			startPosition[4] = 4;
			startPosition[5] = 2;
			startPosition[6] = 1;
			startPosition[7] = 7;
			startSpacePosition = fromRow(sizeY - 2);
		} else {
			int parityCalc = sizeY % 4;
			int paritySwap = (parityCalc == 0) ||
				(parityCalc == 1 && sizeX % 2 == 1) ||
				(parityCalc == 3 && sizeX % 2 == 0);
			for (i = 0; i < AREA; i++) {
				int row, trbl, tlbr;

				row = toRow(i);
				trbl = toTrBl(i, row);
				tlbr = toTlBr(i, row);
				if (i == PREVAREA)
					startPosition[i] = 0;
				else if (i == PREVAREA + 1) {
					if (corners)
						startPosition[i] = AREA - 1;
					else
						startPosition[i] = i;
				} else if (!corners && i == AREA - 1)
					startPosition[i] = i;
				else if (!corners && paritySwap && i == AREA - 2)
					startPosition[i] = i;
				else if (!corners && paritySwap && i == PREVAREA + 2)
					startPosition[i] = i;
				else
					startPosition[i] = toPosition(row, tlbr, trbl - 1);
			}
			startSpacePosition = fromRow(sizeY - 2);
			if (corners)
				startSpacePosition2 = startSpacePosition + 1;
		}
	} else {
/*		for (i = 0; i < AREA; i++) {
			calculateRows2(i);
			j = toPosition(space2Row[ROW], space2Row[TLBR], space2Row[TRBL]) + 1;
			startPosition[i] = j;
			if (j == AREA) {
				startSpacePosition = i;
				startPosition[startSpacePosition] = 0;
			}
			if (j == AREA - 1) {
				if (corners) {
					startSpacePosition2 = i;
					startPosition[startSpacePosition2] = AREA - 1;
				} else {
					startPosition[i] = (sizeY - 1) * (sizeY - 1) + 1;
				}
			}
			if (!corners && i == AREA - 1)
				startPosition[i] = AREA - 1;
			if (j == AREA - 3)
				switch1 = i;
			else if (j == AREA - 2)
				switch2 = i;
		}
		if (!decideSwap()) {
			i = startPosition[switch1];
			startPosition[switch1] = startPosition[switch2];
			startPosition[switch2] = i;
		}
		return;
	} */
	for (i = 0; i < AREA; i++) {
		int row, trbl, tlbr;

		row = toRow(i);
		trbl = toTrBl(i, row);
		tlbr = toTlBr(i, row);
		if (!corners && i == 0) {
			if (initial == ROTATE_CCW) {
				startSpacePosition = i;
				startPosition[i] = 0;
			} else
				startPosition[i] = 1;
		} else if (!corners && i == 2 && initial == ROTATE_CCW)
			startPosition[i] = 1;
		else if (!corners && i == (sizeY - 1) * (sizeY - 1)) {
			if (initial != ROTATE_CCW) {
				startSpacePosition = i;
				startPosition[i] = 0;
			} else
				startPosition[i] = (sizeY - 1) * (sizeY - 1) + 1;
		} else if (!corners && i == (sizeY - 1) * (sizeY - 1) + 1 && (initial != ROTATE_CCW))
			startPosition[i] = (sizeY - 1) * (sizeY - 1) + 1;
		else if (!corners && i == AREA - 1)
			startPosition[i] = AREA - 1;
		else if (initial != ROTATE_CCW)
			startPosition[i] =
				toPosition(sizeY - 1 - trbl,
				tlbr, sizeY - 1 - row) + 1;
		else
			startPosition[i] =
				toPosition(sizeY - 1 - tlbr,
				sizeY - 1 - row, trbl) + 1;
	/*printf("i%d, row%d, trbl%d, tlbr%d, top%d\n",
i, row, trbl, tlbr, tileOfPosition[i]);*/
		}
	if (corners) {
		if (initial != ROTATE_CCW) {
			startSpacePosition = AREA - 2 * sizeY + 1;
			startPosition[AREA - 2 * sizeY + 1] = 0;
			if (sizeY > 1) {
				startSpacePosition2 = AREA - 2 * sizeY + 2;
				startPosition[AREA - 2 * sizeY + 2] = AREA - 1;
			}
		} else {
			startSpacePosition = 0;
			startPosition[0] = 0;
			if (sizeY > 1) {
				startSpacePosition2 = 2;
				startPosition[2] = AREA - 1;
			}
		}
	}
	}
}

static void
setFinishPosition() {
	int i;

	for (i = 0; i < AREA - 1; i++)
		finishPosition[i] = i + 1;
	finishSpacePosition = AREA - 1;
	finishPosition[finishSpacePosition] = 0;
	if (corners) {
		finishSpacePosition2 = AREA - 2;
		finishPosition[finishSpacePosition2] = AREA - 1;
	}
}

static char
checkSolved()
{
	int i;

	for (i = 1; i < AREA - ((corners) ? 1 : 0); i++) {
		if (tileOfPosition[i - 1] != i)
			return FALSE;
	}
	return TRUE;
}

static void
setRowMask(int row)
{
	int i, j, start, shift = 0;
	int modUnit, divUnit;

	for (i = 0; i < MINUNITS(); i++)
		rowMask[i] = 0;
	for (j = 0; j <= row; j++) {
		start = j * bits * (sizeX + j - 1);
		shift = 0;
		for (i = 0; i < (sizeX + 2 * j); i++) {
			modUnit = (start + shift) % arch;
			divUnit = (start + shift) / arch;
			rowMask[divUnit] |= intMask << modUnit;
			shift += bits;
		}
	}
}

static char
checkSolvedByUnitRow(int row)
{
	int i;

	setRowMask(row);
	for (i = 0; i < MINUNITS(); i++)
		if ((shrunkPositionOfTile[i] & rowMask[i])
				!= (finishTiles[i] & rowMask[i]))
			return FALSE;
/*printf("rowMask %lld\n", rowMask[0]);
printf("%lld %lld\n", shrunkPositionOfTile[0], finishTiles[0]);
printf("%lld %lld\n", shrunkPositionOfTile[0] & rowMask[0], finishTiles[0] & rowMask[0]);*/
	return TRUE;
}

static char
checkSolvedByUnit()
{
	int i;

	for (i = 0; i < units; i++)
		if (shrunkPositionOfTile[i] != finishTiles[i])
			return FALSE;
	return TRUE;
}

static char
partiallySolveRow(int row)
{
	if (((sizeX == 1 && sizeY - row >= 3) ||
			(sizeX == 2  && sizeY - row >= 3) ||
			(sizeX > 3 && sizeY - row >= 3)) && piecemeal)
		return TRUE;
	return FALSE;
}

static int
scanStartPosition(FILE *fp) {
	int i, num, c;

	for (i = 0; i < AREA; i++) {
		if (fscanf(fp, "%d ", &num) != 1) {
			(void) fprintf(stderr,
				"corrupt start record, expecting an integer for %d\n", i);
			return FALSE;
		}
		startPosition[i] = num;
		if (!num)
			startSpacePosition = i;
		else if (num < 0) {
			startPosition[i] = BLANK2;
			startSpacePosition2 = i;
		}
	}
	return TRUE;
}

static int
scanFinishPosition(FILE *fp) {
	int i, num, c;

	for (i = 0; i < AREA; i++) {
		if (fscanf(fp, "%d ", &num) != 1) {
			(void) fprintf(stderr,
				"corrupt start record, expecting an integer for %d\n", i);
			return FALSE;
		}
		finishPosition[i] = num;
		if (!num)
			finishSpacePosition = i;
		else if (num < 0) {
			finishPosition[i] = BLANK2;
			finishSpacePosition2 = i;
		}
	}
	return TRUE;
}

static void
setTilesToStart() {
	int i, j;

	/* Need one more for start position */
	if (strcmp(startFile, "") != 0) {
		FILE *fp;
		if ((fp = fopen(startFile, "r")) != NULL) {
			scanStartPosition(fp);
		} else {
			fprintf(stderr,
				"cannot open %s\n", startFile);
			exit(1);
		}
	} else {
		setStartPosition();
	}
	for (i = 0; i < AREA; i++) {
		j = startPosition[i];
		tileOfPosition[j] = i;
		positionOfTile[i] = j;
	}
	if (tileOfPosition[BLANK] != startSpacePosition) {
		printf("fix start!!! tileOfPosition0=%d, startSpacePosition=%d\n",
			tileOfPosition[BLANK], startSpacePosition);
	}
	if (corners && tileOfPosition[BLANK2] != startSpacePosition2) {
		printf("fix start!!! tileOfPosition1=%d, startSpacePosition2=%d\n",
			tileOfPosition[BLANK2], startSpacePosition2);
	}
	printf("start:\n");
	printTiles(positionOfTile);
	for (i = 0; i < AREA; i++)
		setStart(i, startPosition[i]);
	if (debug) {
		printf("check start\n");
		/*for (i = 0; i < AREA; i++)
			startPosition[i] = getStart(i);*/
		for (i = 0; i < AREA; i++) {
			j = startPosition[i];
			tileOfPosition[j] = i;
			positionOfTile[i] = j;
		}
		/*printTiles(positionOfTile);*/
	}
	for (j = 0; j < units; j++)
		shrunkPositionOfTile[j] = 0;
	for (i = 0; i < AREA; i++)
		setTile(i, positionOfTile[i]);
	if (sizeY > 1 && checkSolvedByUnit())
		printf("solution FAILED!!! (start)\n");
}

static void
setTilesToFinish() {
	int i, j;

	if (strcmp(finishFile, "") != 0) {
		FILE *fp;
		if ((fp = fopen(finishFile, "r")) != NULL) {
			scanFinishPosition(fp);
		} else {
			fprintf(stderr,
				"cannot open %s\n", finishFile);
			exit(1);
		}
        } else {
		setFinishPosition();
	}
	for (i = 0; i < AREA; i++) {
		j = finishPosition[i];
		tileOfPosition[j] = i;
		positionOfTile[i] = j;
	}
	if (tileOfPosition[BLANK] != finishSpacePosition) {
		printf("fix finish!!! tileOfPosition0=%d, finishSpacePosition=%d\n",
			tileOfPosition[BLANK], finishSpacePosition);
	}
	if (corners && tileOfPosition[BLANK2] != finishSpacePosition2) {
		printf("fix finish!!! tileOfPosition1=%d, finishSpacePosition2=%d\n",
			tileOfPosition[BLANK2], finishSpacePosition2);
	}
	printf("finish:\n");
	printTiles(positionOfTile);
	for (i = 0; i < AREA; i++)
		setFinish(i, finishPosition[i]);
	if (debug) {
		/*for (i = 0; i < AREA; i++)
			finishPosition[i] = getFinish(i);*/
		for (i = 0; i < AREA; i++) {
			j = finishPosition[i];
			tileOfPosition[j] = i;
			positionOfTile[i] = j;
		}
		/*printPositions(tileOfPosition);*/
	}
	for (j = 0; j < units; j++)
		shrunkPositionOfTile[j] = 0;
	for (i = 0; i < AREA; i++)
		setTile(i, positionOfTile[i]);
	if (!checkSolvedByUnit())
		printf("solution FAILED!!! (finish)\n");
}

static void
resetTiles() {
	int i;

	if (nodeLog)
		(void) free((void *) nodeLog);
	if (!(nodeLog = (LONG *) calloc(size * units,
			sizeof (LONG)))) {
		memoryError("nodeLog");
	}

	if (!(hash = (hashtype **) calloc(hashSize,
			sizeof (hashtype *)))) {
		memoryError("hash table");
	}

	if (tileOfPosition)
		(void) free((void *) tileOfPosition);
	if (!(tileOfPosition = (char *) calloc(AREA,
			sizeof (char)))) {
		memoryError("tileOfPosition");
	}

	if (startPosition)
		(void) free((void *) startPosition);
	if (!(startPosition = (char *) calloc(AREA,
			sizeof (char)))) {
		memoryError("startPosition");
	}

	if (finishPosition)
		(void) free((void *) finishPosition);
	if (!(finishPosition = (char *) calloc(AREA,
			sizeof (char)))) {
		memoryError("finishPosition");
	}
	if (positionOfTile)
		(void) free((void *) positionOfTile);
	if (!(positionOfTile = (char *) calloc(AREA,
			sizeof (char)))) {
		memoryError("positionOfTile");
	}

	if (shrunkPositionOfTile)
		(void) free((void *) shrunkPositionOfTile);
	if (!(shrunkPositionOfTile = (LONG *) calloc(units,
			sizeof (LONG)))) {
		memoryError("shrunkPositionOfTile");
	}
	if (rowMask)
		(void) free((void *) rowMask);
	if (!(rowMask = (LONG *) calloc(units,
			sizeof (LONG)))) {
		memoryError("rowMask");
	}

	if (trblMask)
		(void) free((void *) trblMask);
	if (!(trblMask = (LONG *) calloc(units,
			sizeof (LONG)))) {
		memoryError("trblMask");
	}

	if (tlbrMask)
		(void) free((void *) tlbrMask);
	if (!(tlbrMask = (LONG *) calloc(units,
			sizeof (LONG)))) {
		memoryError("tlbrMask");
	}

	if (startTiles)
		(void) free((void *) startTiles);
	if (!(startTiles = (LONG *) calloc(units,
			sizeof (LONG)))) {
		memoryError("startTiles");
	}
	if (finishTiles)
		(void) free((void *) finishTiles);
	if (!(finishTiles = (LONG *) calloc(units,
			sizeof (LONG)))) {
		memoryError("finishTiles");
	}

	if (move)
		(void) free((void *) move);
	if (!(move = (int *) calloc(size, sizeof (int)))) {
		memoryError("move");
	}
	if (backPoss)
		(void) free((void *) backPoss);
	if (!(backPoss = (char *) calloc(size, sizeof (char)))) {
		memoryError("backPoss");
	}
	if (backPath)
		(void) free((void *) backPath);
	if (!(backPath = (int *) calloc(size, sizeof (int)))) {
		memoryError("backPath");
	}

	setTilesToFinish();
	setTilesToStart();
	putCurrent(currNode);
	getCurrent(currNode);
	if (debug) {
		printf("printTiles\n");
		printTiles(tileOfPosition);
		printf("printPositions\n");
		printPositions(positionOfTile);
	}
	move[0] = 0;
	backPoss[0] = -1; /* needed for first pass */
	loop = 0;
	hashNewIndex = 0;
	c = 0;
	for (i = 0; i < bits; i++) {
		intMask |= 1 << i;
	}
	spaceTile[1] = BLANK2;
}

static void
moveCornerTiles(int fromPosition, int orient)
{
	int fromTile = tileOfPosition[fromPosition];
	int i, j;

	positionOfTile[fromTile] = spacePosition[orient];
	positionOfTile[spaceTile[orient]] = fromPosition;

	tileOfPosition[fromPosition] = tileOfPosition[spacePosition[orient]];
	tileOfPosition[spacePosition[orient]] = fromTile;
	for (j = 0; j < units; j++)
		shrunkPositionOfTile[j] = 0;
	for (i = 0; i < AREA; i++)
		setTile(i, tileOfPosition[i]);
}

static void
moveNoCornTiles(int fromPosition)
{
	int fromTile = tileOfPosition[fromPosition];
	int i, j;

	positionOfTile[fromTile] = space2Position;
	positionOfTile[space2Tile] = fromPosition;

	tileOfPosition[fromPosition] = tileOfPosition[space2Position];
	tileOfPosition[space2Position] = fromTile;
	for (j = 0; j < units; j++)
		shrunkPositionOfTile[j] = 0;
	for (i = 0; i < AREA; i++)
		setTile(i, tileOfPosition[i]);
}

static int
moveCornerSpaceDir(int direction, int spaceUpPosition, int spaceDownPosition)
{
	int orient;

	calculateRows(spaceUpPosition, spaceDownPosition);
	switch (direction) {
	case TR:
		if (spaceRow[UP][TRBL] == spaceRow[DOWN][TRBL] &&
				spaceRow[UP][ROW] != sizeY - 1) {
			if (spaceRow[UP][ROW] < frozenRows
					|| spaceRow[DOWN][ROW] < frozenRows)
				return FALSE;
			orient = (spaceUpPosition + 2 >
				spaceDownPosition) ? UP : DOWN;
			moveCornerTiles(tileNFrom(spacePosition[orient],
				1, TRBL, orient, DOWN), !orient);
			return TRUE;
		}
		break;
	case RIGHT:
		if (spaceRow[UP][ROW] == spaceRow[DOWN][ROW] &&
				spaceRow[UP][TRBL] != 0) {
			orient = (spaceUpPosition <
				spaceDownPosition) ? UP : DOWN;
			moveCornerTiles(tileNFrom(spacePosition[orient],
				1, ROW, orient, UP), !orient);
			return TRUE;
		}
		break;
	case BR:
		if (spaceRow[UP][TLBR] == spaceRow[DOWN][TLBR] &&
				spaceRow[UP][TRBL] != 0) {
			orient = (spaceUpPosition <
				spaceDownPosition) ? UP : DOWN;
			moveCornerTiles(tileNFrom(spacePosition[orient],
				1, TLBR, orient, UP), !orient);
			return TRUE;
		}
		break;
	case BL:
		if (spaceRow[UP][TRBL] == spaceRow[DOWN][TRBL] &&
				spaceRow[UP][TLBR] != 0) {
			orient = (spaceUpPosition + 1 <
				spaceDownPosition) ? UP : DOWN;
			moveCornerTiles(tileNFrom(spacePosition[orient],
				1, TRBL, orient, UP), !orient);
			return TRUE;
		}
		break;
	case LEFT:
		if (spaceRow[UP][ROW] == spaceRow[DOWN][ROW] &&
				spaceRow[UP][TLBR] != 0) {
			orient = (spaceUpPosition >
				spaceDownPosition) ? UP : DOWN;
			moveCornerTiles(tileNFrom(spacePosition[orient],
				1, ROW, orient, DOWN), !orient);
			return TRUE;
		}
		break;
	case TL:
		if (spaceRow[UP][TLBR] == spaceRow[DOWN][TLBR] &&
				spaceRow[UP][ROW] != sizeY - 1) {
			if (spaceRow[UP][ROW] < frozenRows
					|| spaceRow[DOWN][ROW] < frozenRows)
				return FALSE;
			orient = (spaceUpPosition >
				spaceDownPosition) ? UP : DOWN;
			moveCornerTiles(tileNFrom(spacePosition[orient],
				1, TLBR, orient, DOWN), !orient);
			return TRUE;
		}
		break;
	default:
		printf("moveCornerSpaceDir: direction %d", direction);
	}
	return FALSE;
}

static int
moveNoCornSpaceDir(int direction, int spacePosition)
{
	int position;

	calculateRows2(spacePosition);
	/*orient = toOrient(space2Row[ROW], space2Row[TRBL], space2Row[TRBL]);
printf("direction %s, spacePosition%d, trbl%d, tlbr%d, row%d, orient%d\n",
dirToString(direction), spacePosition, space2Row[TRBL], space2Row[TLBR], space2Row[ROW], orient);*/
	if ((direction == TR || direction == TL)
			&& space2Row[ROW] < frozenRows)
		return FALSE;
	position = tile1From(spacePosition, direction);
	if (position >= 0) {
		/*printf("newPosition%d\n", position);*/
		moveNoCornTiles(position);
		return TRUE;
	}
	return FALSE;
}

/* FURTHER */
static void
printLastData(int node) {
	if (backPath[node] > node || (node != 0 && backPath[node] == node)) {
		return;
	}
	getCurrent(node);
	if (node != 0) {
		(void) printf("%3d: %s\n", move[node],
			dirToString((int) backPoss[node]));
	}
	printPositions(positionOfTile);
}

/* FURTHER */
static void
printLastHash(int index) {
	hashtype **oldChain = &(chain[index]);
	hashtype *ctemp = *oldChain;
	while (ctemp != NULL) {
		printLastData(ctemp->node);
		ctemp = ctemp->next;
	}
}

static void
printDataMove(int node) {
	if (backPath[node] > node || (node != 0 && backPath[node] == node)) {
		return;
	}
	if (node != 0) {
		printDataMove(backPath[node]);
	}
	getCurrent(node);
	if (node != 0) {
		(void) fprintf(stderr, "%d: %d\n", move[node],
			backPoss[node]);
	}
}

static void
printData(int node) {
	if (backPath[node] > node || (node != 0 && backPath[node] == node)) {
		return;
	}
	if (node != 0) {
		printData(backPath[node]);
	}
	getCurrent(node);
	if (node != 0) {
		if (corners)
			(void) printf("%3d: %s\n", move[node],
				dirToString((int) backPoss[node]));
		else /* assumes empty space top triangle is used for start */
			(void) printf("%3d: %s\n", move[node],
				dirToStringNoCorn((int) backPoss[node], !(move[node] & 1)));
	}
	printPositions(positionOfTile);
}

static int
getnum(char * message) {
	char buff[80];

	(void) printf("%s: ", message);
	return((int) strtol(fgets(buff, 80, stdin), 0, 0));
}

static void
readData(int nodes) {
#ifdef ARCH128
	arch = 128;
#elif defined( ARCH64 )
	arch = 64;
	if (debug)
		(void) printf("%d bit architecture.\n", arch);
#else
	arch = 8 * sizeof( bitmask );
	(void) printf("Assuming %d bit architecture.\n", arch);
#endif
	tiles = AREA - 1 - ((corners) ? 1 : 0);
	while (sizeX < 1)
		sizeX = getnum((char *) "Enter: # of sizeX >");
	while (sizeY < 1)
		sizeY = getnum((char *) "Enter: # of sizeY >");
	if (tiles > ARRAYTWEAKS) {
		(void) printf("Be careful, you need lots of memory.\n");
		inputSize = getnum((char *)
			"Enter: # of nodes to keep in memory >");
		hashSize = getnum((char *)
			"Enter: size of hash >");
	} else {
		if (tiles < NOFULLSOLUTION && nodes == 0)
			inputSize = minSizes[tiles];
		else {
			/* 3 moves must be kept in memory to progress */
			int minMem = 3 * moveSizes[tiles];

			if (nodes == 0)
				inputSize = minMem;
			else
				inputSize = nodes;
			if (inputSize < minMem) {
				(void) printf("Nodes %lld < %d, changing\n",
					inputSize, minMem);
				inputSize = minMem;
			}
			if (inputSize < minSizes[tiles])
				(void) printf(
					"Full path may not be printed\n");
		}
		hashSize = hashSizes[tiles];
	}
	size = inputSize;
	if (debug)
		(void) printf("size %d\n", size);
	bits = MINBITS();
	if (bits == 0) {
		(void) printf("no moves needed\n");
		exit(0);
	}
	units = MINUNITS();
	numInUnit = MAXNUMINUNIT();
	if (debug)
		(void) printf("bits %d, units %d, numInUnit %d\n",
			bits, units, numInUnit);
	bitmask = (1 << bits) - 1;
	freqmask = (int) (~((1 << FREQBITS) - 1));
	if (units > 2)
		(void) printf("Key for hash may not be efficient.\n");
	if (debug > 1) /* hashless check */
		unitMem = (sizeof (char)) * units;
	resetTiles();
}

static int
isNewNode() {
	int unit, node;
	LONG *psPOT, *pnodeLog;
	LONG *pnodeLogFirst = &(nodeLog[newNode * units]);

	for (node = newNode; node >= newBottom; node--) {
		/* check if already done */
		pnodeLog = pnodeLogFirst;
		psPOT = shrunkPositionOfTile;
		for (unit = 0; unit < units; unit++) {
			if (*pnodeLog != *psPOT)
				goto CONTINUE; /* I hate gotos */
			pnodeLog++;
			psPOT++;
		}
		return FALSE;
CONTINUE:	pnodeLogFirst -= unitMem;
	}
	return TRUE;
}

static void
searchBreadthFirst() {
	int localMoveSize = 0, moveSize = 0;
	char m;
	int foundSolution = 0;
	char *ppOT = positionOfTile;
	int moved = FALSE;
	int temp;

    for (;;) {
LOOP:
	/*printf("SPACE%d, ROW %d, TRBL=%d, TLBR=%d\n",
		ppOT[BLANK], spaceRow[ROW], spaceRow[TRBL], spaceRow[TLBR]);*/
	for (m = 0; m < (char) POSSIBILITIES; m++) {
		if (backPoss[currNode] == OPP_DIR(m)) {
			/*printf("not doing %d\n", m);*/
			/* undoing previous move */
			continue; /* move could be shorter, so ignore */
		}
		if (corners)
			moved = moveCornerSpaceDir((int) m, ppOT[BLANK], ppOT[BLANK2]);
		else
			moved = moveNoCornSpaceDir((int) m, ppOT[BLANK]);
		if (moved) {
			if (debug) {
				(void) printf("breadth dir %s, last dir %s\n", 
					dirToString(m), dirToString(backPoss[currNode]));
				printPositions(ppOT);
			}
			if (!(inHash())) {
				/*printf("not in hash\n");*/
				if (debug > 1 && !isNewNode()) {
					/* hashless check */
					(void) printf("got node:%d %lld\n",
						newNode + 1,
						*shrunkPositionOfTile);
				}
				newNode++;
				if (newNode >= size) {
					newNode = 0;
				}
				if ((newNode & freqmask) == newNode) {
					if (newNode == 0)
						(void) printf("loop:%d; ",
							loop + 1);
					(void) printf("node:%d; move:%d; collisions:%lld\n",
						newNode, move[currNode] + 1, c);
				}
				backPoss[newNode] = m;
				backPath[newNode] = currNode;
				move[newNode] = move[currNode] + 1;
				localMoveSize++;
				putCurrent(newNode); /* save node */
				putInHash(hashNewIndex, newNode);
				if (partiallySolveRow(frozenRows) &&
						checkSolvedByUnitRow(frozenRows)) {
					frozenRows += 1;
					printf("freezing row %d at move %d\n", frozenRows, move[newNode]);
					printData(newNode);
					currNode = newNode;
					goto LOOP;
				}
				if (checkSolvedByUnit()) {
					(void) printf("loops: %d, size: %d, nodes: %d; moves: %d\n",
						loop, size, newNode + 1, move[newNode]);
					if (redirect) {
						(void) fprintf(stderr, "corners: %d\n", corners);
						(void) fprintf(stderr, "tiles.x: %d\n", sizeX);
						(void) fprintf(stderr, "tiles.y: %d\n", sizeY);
						(void) fprintf(stderr, "moves: %d\n", move[newNode]);
						(void) fprintf(stderr, "\nstartingPosition:\n");
						printTilesDigit(startPosition);
						(void) fprintf(stderr, "\nmoves direction\n");
						printDataMove(newNode);
					}
					printData(newNode);
					(void) printf("total nodes: %d * %d + %d\n",
						loop, size, newNode + 1);
					(void) printf("total nodes when found solution: %lld\n",
						(long long) loop * size + newNode + 1);
					(void) printf("moveSize: %d\n",
						moveSize);
					(void) printf("collisions: %lld\n",
						c);
					foundSolution = move[newNode];
					(void) printf("total moves: %d\n",
						foundSolution);
					if (mode == MINIMUM_MOVES)
						exit(0);
					/* Do not exit as may find a better solution */
					/* Done when number of moves for mode progresses */
				}
			}
			getCurrent(currNode); /* backout */
		}
	}
	if (newNode != currNode) {
		if (move[currNode] < move[(currNode + 1) % size]) {
			if (mode != FURTHER && foundSolution) {
				(void) printf("total nodes when complete: %lld\n",
					(long long) loop * size + newNode + 1);
				exit(0);
			}
			if (debug > 1) {
				printLastHash(hashNewIndex);
			}
			if (debug > 1) { /* hashless check */
				newBottom = move[(currNode + 1) % size];
			}
			if (localMoveSize > moveSize) {
				moveSize = localMoveSize;
			}
			localMoveSize = 0;
			hashNewIndex = (hashNewIndex + 1) % CHAINS;
			freeHash(hashNewIndex);
		}
		currNode++;
		if (currNode >= size) {
			currNode = 0;
			loop++;
		}
		getCurrent(currNode);
	} else {
		if (mode == FURTHER)
			(void) printf("Farthest point\n");
		else if (!foundSolution)
			(void) printf("No solution\n");
		(void) printf("loops: %d, size: %d, nodes: %d; moves: %d\n",
			loop, size, newNode + 1, move[newNode]);
		if (mode == FURTHER)
			printData(newNode);
		if (size < minSizes[tiles - 1])
			(void) printf("total nodes: %d\n",
				loop * size + newNode + 1);
		else
			(void) printf("total nodes: %d * %d + %d\n",
				loop, size, newNode + 1);
		(void) printf("moveSize: %d\n", moveSize);
		(void) printf("collisions: %lld\n", c);
		(void) printf("total moves: %d\n", move[newNode]);
		if (mode == FURTHER) {
			printLastHash((hashNewIndex + CHAINS - 1) % CHAINS);
		}
		exit(0);
	}
    }
}

static void
usage()
{
	(void) fprintf(stderr,
		"usage: \"triangles [-c] [-d debugLevel] [-i initial] [-s start_file] [-f finish_file] [-m mode] [-n nodesNumber] [-p] [-r] [-x X] [-y Y]\"\n");
	(void) fprintf(stderr, "\tinitial:\t0 mirror (default)\n");
	(void) fprintf(stderr, "\t\t1 offset\n");
	(void) fprintf(stderr, "\t\t2 reverse\n");
	(void) fprintf(stderr, "\t\t3 offset reverse\n");
	(void) fprintf(stderr, "\tstart:\tstart positions (s)\n");
	(void) fprintf(stderr, "\tfinish:\tfinish positions (f)\n");
	(void) fprintf(stderr, "\tmode:\t0 match finish point (default)\n");
	(void) fprintf(stderr, "\t\t1 find furthest point\n");
	(void) fprintf(stderr, "\tpiecemeal:\tallow piecemeal solution (p)\n");
	(void) fprintf(stderr, "\tredirect:\toutput log to stderr (r)\n");
	exit(1);
}

int
main(int argc, char **argv) {
	int nodes = 0;

	argc--;
	argv++;
	while (argc) {
		if (argv[0][0] == '-') {
			switch (argv[0][1]) {
			case '\0':
				usage('a');
				break;
			case 'c':
				corners = TRUE;
				break;
			case 'd':
				if (argc > 1) {
					argc--;
					argv++;
					debug = atoi(argv[0]);
					break;
				} else {
					usage('d');
				}
			case 'i':
				if (argc > 1) {
					argc--;
					argv++;
					initial = atoi(argv[0]);
					if (initial < 0 || initial >= STARTS)
						initial = MIRROR;
					break;
				} else {
					usage('i');
				}
			case 'f':
				argc--;
				argv++;
				strncpy(finishFile, argv[0], FILE_NAME_LENGTH);
				break;
			case 'm':
				if (argc > 1) {
					argc--;
					argv++;
					mode = atoi(argv[0]);
					if (mode < 0 || mode >= MODES)
						mode = MINIMUM_MOVES;
					break;
				} else {
					usage('m');
				}
			case 'n':
				if (argc > 1) {
					argc--;
					argv++;
					nodes = atoi(argv[0]);
					break;
				} else {
					usage('n');
				}
			case 'p':
				piecemeal = TRUE;
				break;
			case 'r':
				redirect = TRUE;
				break;
			case 's':
                                argc--;
                                argv++;
                                strncpy(startFile, argv[0], FILE_NAME_LENGTH);
                                break;
			case 'x':
				if (argc > 1) {
					argc--;
					argv++;
					sizeX = atoi(argv[0]);
					break;
				} else {
					usage('x');
				}
			case 'y':
				if (argc > 1) {
					argc--;
					argv++;
					sizeY = atoi(argv[0]);
					break;
				} else {
					usage('y');
				}
			default:
				usage('b');
			}
		}
		argc--;
		argv++;
	}
	if (sizeX != 1)
		initial = MIRROR;
	readData(nodes);

#if !defined( __MSDOS__ ) && !defined( __CYGWIN__ )
	/* This gets rid of the unwanted buffering in UNIX */
	(void) setlinebuf(stdout);
#endif

	searchBreadthFirst();
#ifdef VMS
	return 1;
#else
	return 0;
#endif
}