Bridges

#include <stdio.h>
#include <ctype.h>
#include <assert.h>

#define DEBUG 1

#define MAX_DIM 30 //the biggest possible dimension for a game
#define MAX_ISLANDS 250  //the most possible islands in a game

//=========================================================

#define DB if (DEBUG) printf

#define VERT_SINGLE '|'
#define VERT_DOUBLE '\"'
#define HOR_SINGLE '-'
#define HOR_DOUBLE '='

#define NO_DIRECTION 0
#define UP 1
#define RIGHT 2
#define DOWN 3
#define LEFT 4

#define CONNECTED 1
#define NOT_CONNECTED 0

#define BRIDGE 1
#define NO_BRIDGE 0

#define NO_LINK -1

#define STUPID_BRUTE 1
#define SMART_BRUTE 2
#define LOOPY_BRUTE 3

int max(int a, int b);
long long int power(int base, int index);
char* directionName(int direction);
int oppositeDirection(int direction);
int findIsland(int x, int y, int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int islands);
void inputGame(char map[MAX_DIM][MAX_DIM], int *xDim, int *yDim);
int countIslands(char map[MAX_DIM][MAX_DIM], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int bridgeVal[MAX_ISLANDS], int xDim, int yDim);
void findLinks(int linkDirections[MAX_ISLANDS][MAX_ISLANDS], char map[MAX_DIM][MAX_DIM], int bridges[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int xDim, int yDim, int islands, int *links);
void checkConnections(int connected[MAX_ISLANDS], int bridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int island);
int validSolution(int bridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS]);
int addMoreBridges(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS]);
int fillOutBridges(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS]);
void addBridgesToMap(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS],  int islandX[MAX_ISLANDS],  int islandY[MAX_ISLANDS], char map[MAX_DIM][MAX_DIM], int islands, int linkDirections[MAX_ISLANDS][MAX_ISLANDS]);
void solvePuzzleLoopyBrute(int bridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int xDim, int yDim, char map[MAX_DIM][MAX_DIM]);
void buildOutput(char output[MAX_DIM][MAX_DIM], int linkDirections[MAX_ISLANDS][MAX_ISLANDS], int bridges[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int xDim, int yDim, int islands, int bridgeVal[MAX_ISLANDS]);
void displayOutput(char output[MAX_DIM][MAX_DIM], int xDim, int yDim);

int main(int argc, char** argv){

   int i=0, j=0;

   int xDim = 0, yDim = 0; //the size of the map
   char map[MAX_DIM][MAX_DIM];
   //The layout of the game, as input
   //
   // 2..2
   // ....  xDim = 4, yDim = 3
   // 2..2

   int islands = 0;
   int bridgeVal[MAX_ISLANDS];
   int islandX[MAX_ISLANDS];
   int islandY[MAX_ISLANDS];
   //The grid co-ordinates and numeric value of each island
   //
   //    X Y bridgeVal
   //    -----
   // 0 |0 0 2
   // 1 |3 0 2   islands = 4
   // 2 |0 2 2
   // 3 |3 2 2

   int links = 0;
   int linkDirections[MAX_ISLANDS][MAX_ISLANDS];
   //The direction of adjacency between two islands.  Opposites about the diagonal have opposite directions.
   //
   //    0123
   //    ----  0 = No link
   // 0 |0230  1 = Up
   // 1 |4003  2 = Right
   // 2 |1002  3 = Down
   // 3 |0140  4 = Left

   int bridges[MAX_ISLANDS][MAX_ISLANDS];
   //The answer to the puzzle.  0, 1, 2 indicates the number of bridges between two islands.  Symmetrical about the diagonal.
   //
   //    0123
   //    ----
   // 0 |0110
   // 1 |1001
   // 2 |1001
   // 3 |0110

   char output[MAX_DIM][MAX_DIM];
   //The program's output.
   //
   // 2--2
   // |  |
   // 2--2

   //init
   for (i=0; i<MAX_DIM; i++){
      for (j=0; j<MAX_DIM; j++){
         map[i][j] = 0;
      }
   }
   for (i=0; i<MAX_ISLANDS; i++){
      bridgeVal[i] = 0;
      islandX[i] = 0;
      islandY[i] = 0;
      for (j=0; j<MAX_ISLANDS; j++){
         linkDirections[i][j] = NO_DIRECTION;
         bridges[i][i] = NO_LINK;
      }
   }

   //Read and map out the game
   DB("Inputting game...\n");
   inputGame(map, &xDim, &yDim);

   DB("Counting islands...\n");
   islands = countIslands(map, islandX, islandY, bridgeVal, xDim, yDim);

   DB("Determining adjacencies...\n");
   findLinks(linkDirections, map, bridges, islandX, islandY, xDim, yDim, islands, &links);

   DB("Solving puzzle...\n");
   solvePuzzleLoopyBrute(bridges, islands, bridgeVal, linkDirections, islandX, islandY, xDim, yDim, map);

   DB("Building output...\n");
   buildOutput(output, linkDirections, bridges, islandX, islandY, xDim, yDim, islands, bridgeVal);

   DB("Displaying output...\n");
   displayOutput(output, xDim, yDim);

   return 0;
}

int max(int a, int b){
   return (a>b ? a : b);
}

long long int power(int base, int index){
   int i = 0;
   long long int answer = 1;
   for (i=0; i<index; i++)
      answer *= base;
   return answer;
}

//Should be substantially faster than the above power()
long long int power3(int index){
   int i = 0;
   long long int answer = 1;
   switch(index){
   case  0: return 1;
   case  1: return 3;
   case  2: return 9;
   case  3: return 27;
   case  4: return 81;
   case  5: return 243;
   case  6: return 729;
   case  7: return 2187;
   case  8: return 6561;
   case  9: return 19683;
   case 10: return 59049;
   case 11: return 177147;
   case 12: return 531441;
   case 13: return 1594323;
   case 14: return 4782969;
   case 15: return 14348907;
   case 16: return 43046721;
   case 17: return 129140163;
   case 18: return 387420489;
   case 19: return 1162261467;
   default:
      for (i=0; i<index; i++)
         answer *= 3;
      return answer;
   }
}

char* directionName(int direction){
   switch (direction){
   case UP: return "up";
   case DOWN: return "down";
   case LEFT: return "left";
   case RIGHT: return "right";
   case NO_DIRECTION: return "no direction";
   default: return "invalid direction";
   }
}

int oppositeDirection(int direction){
   switch (direction){
   case UP: return DOWN;
   case DOWN: return UP;
   case LEFT: return RIGHT;
   case RIGHT: return LEFT;
   default: return NO_DIRECTION;
   }
}

int findIsland(int x, int y, int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int islands){
   int i;
   for (i=0; i<islands; i++)
      if (x == islandX[i] && y == islandY[i])
         return i;
   return -1; //if no island found
}

void inputGame(char map[MAX_DIM][MAX_DIM], int *xDim, int *yDim){
   int x = 0, y = 0;
   char c;
   c = getchar();
   while (c != '\n' && c != EOF){
      map[x][y] = c;
      x ++;
      c = getchar();
      if (c == '\n'){
         y ++;
         *yDim = y;
         if (x != 0)
            *xDim = x;
         x = 0;
         c = getchar();
      }
   }
}

int countIslands(char map[MAX_DIM][MAX_DIM], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int bridgeVal[MAX_ISLANDS], int xDim, int yDim){
   int i, j;
   int islands = 0;
   DB("Dimensions: %dx%d\n", xDim, yDim);
   for (j=0; j<=yDim; j++){
      for (i=0; i<=xDim; i++){
         if (isdigit(map[i][j])){
            islandX[islands] = i;
            islandY[islands] = j;
            bridgeVal[islands] = (int) (map[i][j] - '0');
            DB("Island %d: x=%d, y=%d.  Value = %d.\n", islands, i, j, bridgeVal[islands]);
            islands ++;
         }
      }
   }
   DB("%d islands\n", islands);
   return islands;
}

void findLinks(int linkDirections[MAX_ISLANDS][MAX_ISLANDS], char map[MAX_DIM][MAX_DIM], int bridges[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int xDim, int yDim, int islands, int *links){
   int from = 0, to = 0;
   int x = 0, y = 0;
   int n = 0;

   for (from = 0; from<islands; from ++){
      for (to=0; to<islands; to++){
         linkDirections[from][to] = NO_DIRECTION;
      }
      x = islandX[from];
      y = islandY[from];

      // up
      for (n = y-1; n>=0; n--){
         if (map[x][n] == '~'){ // trying to cross another bridge here.  Bad idea.
            n=-1;
         }else if (isdigit(map[x][n])){
            to = findIsland(x, n, islandX, islandY, islands);
            assert (to >= 0); //we know about this island
            //DB("Direction from island %d to island %d = %d, %s (before processing).\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
            assert (
               linkDirections[from][to] == NO_DIRECTION ||
               linkDirections[from][to] == UP
            );
            linkDirections[from][to] = UP;
            linkDirections[to][from] = DOWN;
            bridges[from][to] = 0; //bridges are allowed here
            bridges[to][from] = 0;
            n = 0;
            //DB("Direction from island %d to island %d = %d, %s.\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
            (*links) ++;
         }
      }
      // down
      for (n = y+1; n<=yDim; n++){
         if (map[x][n] == '~'){ // trying to cross another bridge here.  Bad idea.
            n=yDim+1;
         }else if (isdigit(map[x][n])){
            to = findIsland(x, n, islandX, islandY, islands);
            assert (to >= 0); //we know about this island
            //DB("Direction from island %d to island %d = %d, %s (before processing).\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
            assert (
               linkDirections[from][to] == NO_DIRECTION ||
               linkDirections[from][to] == DOWN
            );
            linkDirections[from][to] = DOWN;
            linkDirections[to][from] = UP;
            bridges[from][to] = 0; //bridges are allowed here
            bridges[to][from] = 0;
            n = yDim;
            //DB("Direction from island %d to island %d = %d, %s.\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
            (*links) ++;
         }
      }
      // left
      for (n = x-1; n>=0; n--){
         if (map[n][y] == 's'){ // trying to cross another bridge here.  Bad idea.
            n=-1;
         }else if (isdigit(map[n][y])){
            to = findIsland(n, y, islandX, islandY, islands);
            assert (to >= 0); //we know about this island
            //DB("Direction from island %d to island %d = %d, %s (before processing).\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
            assert (
               linkDirections[from][to] == NO_DIRECTION ||
               linkDirections[from][to] == LEFT
            );
            linkDirections[from][to] = LEFT;
            linkDirections[to][from] = RIGHT;
            bridges[from][to] = 0; //bridges are allowed here
            bridges[to][from] = 0;
            n = 0;
            //DB("Direction from island %d to island %d = %d, %s.\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
            (*links) ++;
         }
      }
      // RIGHT
      for (n = x+1; n<=xDim; n++){
         if (map[n][y] == 's'){ // trying to cross another bridge here.  Bad idea.
            n=xDim+1;
         }else if (isdigit(map[n][y])){
            to = findIsland(n, y, islandX, islandY, islands);
            assert (to >= 0); //we know about this island
            //DB("Direction from island %d to island %d = %d, %s (before processing).\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
            assert (
               linkDirections[from][to] == NO_DIRECTION ||
               linkDirections[from][to] == RIGHT
            );
            linkDirections[from][to] = RIGHT;
            linkDirections[to][from] = LEFT;
            bridges[from][to] = 0; //bridges are allowed here
            bridges[to][from] = 0;
            n = xDim;
            //DB("Direction from island %d to island %d = %d, %s.\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
            (*links) ++;
         }
      }
   }
   (*links) /= 2;
   DB("%d possible links.\n", *links);
}

void checkConnections(int connected[MAX_ISLANDS], int bridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int island){
   DB("Checking connections from island %d\n", island);
   int i = 0;
   connected[island] = CONNECTED;
   for (i=0; i<islands; i++){
      if (bridges[island][i] > 0){
         if (connected[i] == NOT_CONNECTED){
            checkConnections(connected, bridges, islands, i);
         }
      }
   }
}

int validSolution(int bridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS]){
   int i=0, j=0;
   int n=0;
   int islandBridge[islands]; //the number of bridges connected to each island
   int connected[MAX_ISLANDS]; //whether each island is connected to island 0
   int bridgeMap[MAX_DIM][MAX_DIM];

   for (i=0; i<MAX_DIM; i++){
      for (j=0; j<MAX_DIM; j++){
         bridgeMap[i][j] = NO_BRIDGE;
      }
   }

   //the total number of bridges connected to each island must be equal to the number on the island
   for (i=0; i<islands; i++){
      islandBridge[i] = 0; //init
      connected[i] = NOT_CONNECTED;
      for (j=0; j<islands; j++){
         if (bridges[i][j] != NO_LINK){
            islandBridge[i] += bridges[i][j];
            //DB("{%d->%d = %d} ", i, j, bridges[i][j]);
         }
      }
      if (islandBridge[i] != bridgeVal[i]){
         return 0;
      }
   }

   //all the islands must be connected to each other
   checkConnections(connected, bridges, islands, 0);
   for (i=0; i<islands; i++){
      if (connected[i] == NOT_CONNECTED){
         DB("All nodes are not connected.  This is not a solution.\n");
         return 0;
      }
   }


   //bridges are not allowed to cross each other
   for (i=0; i<islands; i++){
      for (j=0; j<islands; j++){
         switch (linkDirections[i][j]){
         case UP:
            assert (islandX[i] == islandX[j]);
            for (n=islandY[i]-1; n > islandY[j]; n--)
               if (bridgeMap[i][j] == BRIDGE)
                  return 0;
               bridgeMap[i][j] = BRIDGE;
            break;
         case DOWN:
            assert (islandX[i] == islandX[j]);
            for (n=islandY[i]+1; n < islandY[j]; n++)
               if (bridgeMap[i][j] == BRIDGE)
                  return 0;
               bridgeMap[i][j] = BRIDGE;
            break;
         case LEFT:
            assert (islandY[i] == islandY[j]);
            for (n=islandX[i]-1; n > islandX[j]; n--)
               if (bridgeMap[i][j] == BRIDGE)
                  return 0;
               bridgeMap[i][j] = BRIDGE;
            break;
         case RIGHT:
            assert (islandY[i] == islandY[j]);
            for (n=islandX[i]+1; n < islandX[j]; n++)
               if (bridgeMap[i][j] == BRIDGE)
                  return 0;
               bridgeMap[i][j] = BRIDGE;
            break;

            default:;
         }
      }
   }
   DB("Solution\n");
   return 1;
}

int addMoreBridges(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS]){
   int bridgesAdded = 0;
   int i=0, j=0;
   int linkCounter = 0;
   int newBridgeVal[islands];
   int newPreparedBridges[islands][islands];
   for (i=0; i<islands; i++){
      newBridgeVal[i] = bridgeVal[i];
      for (j=0; j<islands; j++){
         newPreparedBridges[i][j] = 0;
      }
   }

   //newBridgeVal = bridgeVal - bridges in the original preparedBridges
   for (i=0; i<islands; i++){
      newBridgeVal[i] = bridgeVal[i];
      for (j=0; j<islands; j++){
         assert(preparedBridges[i][j] == preparedBridges[j][i]);
         newBridgeVal[i] -= preparedBridges[i][j];
         assert(newBridgeVal[i] >= 0);
      }
         //DB("BridgeVal: %d --> %d\n", bridgeVal[i], newBridgeVal[i]);
   }
   for (i=0; i<islands; i++){
      if (newBridgeVal[i] > 0){
         //assemble linkCounter, skipping full islands
         linkCounter = 0;
         for (j=0; j<islands; j++){
            if ((linkDirections[i][j] != NO_DIRECTION) && (newBridgeVal[j] > 0)){
               linkCounter++;
            }
         }
      }
      //addMandatoryBridges algorithm, but using newBridgeVal, and adding bridges only to islands that aren't full.
      DB("Island %d: linkCounter = %d, newBridgeVal = %d", i, linkCounter, newBridgeVal[i]);
      if (linkCounter > 0 && linkCounter == (newBridgeVal[i] + 1) / 2){
         DB(" - more mandatory bridges here");
         for (j=0; j<islands; j++){
            if (newBridgeVal[j] > 0){
               if (linkDirections[i][j] != NO_DIRECTION){
                  newPreparedBridges[i][j] = (newBridgeVal[i] / linkCounter);
                  bridgesAdded ++;
               }
            }
         }
      }
      DB("\n");
   }
   DB("\n");
   for (i=0; i<islands; i++){
      for (j=0; j<islands; j++){
         newPreparedBridges[i][j] = newPreparedBridges[j][i] = max(newPreparedBridges[i][j], newPreparedBridges[j][i]);
         assert(newPreparedBridges[i][j] == newPreparedBridges[j][i]);
         if (newPreparedBridges[i][j] > 0){
            DB("Prepared bridge: %d%c%d\n", i,newPreparedBridges[i][j] == 1 ? HOR_SINGLE : HOR_DOUBLE, j);
            assert(linkDirections[i][j] != NO_DIRECTION);
         }
         preparedBridges[i][j] += newPreparedBridges[i][j];
      }
   }
   DB("%d extra bridges added this time\n", bridgesAdded);
   return bridgesAdded;
}

int fillOutBridges(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS]){
   int bridgesAdded = 0;
   int i=0, j=0;
   int n=0;
   int newBridgeVal[islands];
   int linkCounter[islands];
   int bridgeRoom[islands]; //room for more bridges
   int newPreparedBridges[islands][islands];
   for (i=0; i<islands; i++){
      newBridgeVal[i] = 0;
      bridgeRoom[i] = 0;
      for (j=0; j<islands; j++){
         linkCounter[i] = 0;
         newPreparedBridges[i][j] = 0;
      }
   }


   //newBridgeVal = bridgeVal - bridges in the original preparedBridges
   DB("%d islands\n", islands);
   for (i=0; i<islands; i++){
      newBridgeVal[i] = bridgeVal[i];
      if (newBridgeVal[i] > 0){
         DB("Island %d, bridgeVal = %d", i, bridgeVal[i]);
         for (j=0; j<islands; j++){
            assert(preparedBridges[i][j] == preparedBridges[j][i]);
            if (preparedBridges[i][j] > 0) DB(" -%d", preparedBridges[i][j]);
            assert(preparedBridges[i][j] <= newBridgeVal[i]);
            //DB("BridgeVal[%d} change: %d - %d = ", i, newBridgeVal[i], preparedBridges[i][j]);
            newBridgeVal[i] -= preparedBridges[i][j];
            //DB("%d\n", newBridgeVal[i]);
            assert(newBridgeVal[i] >= 0);
         }
         DB("\n");
      }
      assert(newBridgeVal[i] >= 0);
      DB("BridgeVal[%d]: %d --> %d\n", i, bridgeVal[i], newBridgeVal[i]);
   }
   for (i=0; i<islands; i++){
      if (newBridgeVal[i] > 0){
         //assemble linkCounter, skipping full islands
         linkCounter[i] = 0;
         for (j=0; j<islands; j++){
            if ((linkDirections[i][j] != NO_DIRECTION) && (newBridgeVal[j] > 0)){
               linkCounter[i] ++;
               bridgeRoom[i] += newBridgeVal[j];
            }
         }
      }
   }

   //fill out bridges
   for (i=0; i<islands; i++){
      if (newBridgeVal[i] > 0 && newBridgeVal[i] == bridgeRoom[i]){ //all possible bridges can be filled
         DB("Added %d bridges\n", bridgeRoom[i]);
         for (j=0; j<islands; j++){
            if (linkDirections[i][j] != NO_LINK){
               n = newBridgeVal[j];
               newPreparedBridges[i][j] += n;
               newPreparedBridges[j][i] += n;
               newBridgeVal[i] -= n;
               newBridgeVal[j] -= n;
               bridgesAdded ++;
            }
         }
         //assert(newBridgeVal[i] == 0);
      }
   }

   for (i=0; i<islands; i++){
      for (j=0; j<islands; j++){
         newPreparedBridges[i][j] = newPreparedBridges[j][i] = max(newPreparedBridges[i][j], newPreparedBridges[j][i]);
         assert(newPreparedBridges[i][j] == newPreparedBridges[j][i]);
         if (newPreparedBridges[i][j] > 0) DB("Prepared bridge: %d%c%d\n", i,newPreparedBridges[i][j] == 1 ? HOR_SINGLE : HOR_DOUBLE, j);

         if (newPreparedBridges[i][j]>0) DB("Prepared bridges[%d][%d]: %d-->%d\n", i, j, preparedBridges[i][j], preparedBridges[i][j] + newPreparedBridges[i][j]);
         preparedBridges[i][j] += newPreparedBridges[i][j];
      }
   }

   return bridgesAdded;
}

void addBridgesToMap(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS],  int islandX[MAX_ISLANDS],  int islandY[MAX_ISLANDS], char map[MAX_DIM][MAX_DIM], int islands, int linkDirections[MAX_ISLANDS][MAX_ISLANDS]){
   int i=0, j=0;
   int bridgeVal[islands];
   int x=0, y=0;
   int reached = 0;
   for (i=0; i<islands; i++){
      bridgeVal[i] = 0;
      for (j=0; j<islands; j++){
         if (preparedBridges[i][j] > 0 && linkDirections[i][j] != NO_DIRECTION){
            DB("%d,%d(island %d) --> %d,%d(island %d)   %s (%d)\n", islandX[i], islandY[i], i, islandX[j], islandY[j], j, directionName(linkDirections[i][j]), linkDirections[i][j]);
            bridgeVal[i] += preparedBridges[i][j];
            reached = 0;
            x=islandX[i];
            y=islandY[i];
            while (!reached){
               switch (linkDirections[i][j]){
               case UP:
                  y --;
                  reached = (y == islandY[j]);
                  break;
               case DOWN:
                  y ++;
                  reached = (y == islandY[j]);
                  break;
               case LEFT:
                  x --;
                  reached = (x == islandX[j]);
                  break;
               case RIGHT:
                  x ++;
                  reached = (x == islandX[j]);
                  break;
               default:
                  DB("attempting to blacklist bridge with no direction\n");
                  ;
               }
               if (x != islandX[j] || y != islandY[j]){
                  map[x][y] = ((linkDirections[i][j] == LEFT || linkDirections[i][j] == RIGHT) ? '~' : 's'); //bridge part here; no crossing
               }
            }
         }
      }
      map[islandX[i]][islandY[i]] = bridgeVal[i]+'0'; //for debugging purposes
   }
}

void solvePuzzleLoopyBrute(int bridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int xDim, int yDim, char map[MAX_DIM][MAX_DIM]){
   //brief algorithm:
   //performs initial bridgework of Smart Brute, then repeats the process in a modular way to further cut down required permutations.
   int links = 0;
   int solutionFound = 0;
   int potential[3][islands*2];
   int i=0, j=0, k=0;
   int potentials = 0;
   int listed = 0;
   long long int bruteCap = 0;
   long long int bruteLoop = 0;
   int preparedBridges[MAX_ISLANDS][MAX_ISLANDS];
   int newBridgeVal[islands];
   int permutationNoGood = 0; //flags the current permutation as bad

   //init
   for (i=0; i<islands; i++){
      for (j=0; j<islands; j++){
         preparedBridges[i][j] = 0;
      }
   }
   for (i=0; i<=2; i++){
      for (j=0; j<islands*2; j++){
         potential[i][j] = 0;
      }
   }

   //Add bridges until no more can be added automatically
   while (addMoreBridges(preparedBridges, islands, bridgeVal, linkDirections) > 0){
      DB("Bridges added\n");
      addBridgesToMap(preparedBridges, islandX, islandY, map, islands, linkDirections);
      findLinks(linkDirections, map, bridges, islandX, islandY, xDim, yDim, islands, &links);
      for (i=0; i<=xDim; i++){
         for (j=0; j<=yDim; j++){
            DB("%c", map[j][i]);
         }
         DB("\n");
      }
   }
   while (fillOutBridges(preparedBridges, islands, bridgeVal, linkDirections) > 0){
      DB("Bridges filled out\n");
      addBridgesToMap(preparedBridges, islandX, islandY, map, islands, linkDirections);
      findLinks(linkDirections, map, bridges, islandX, islandY, xDim, yDim, islands, &links);
   }

   for (i=0; i<xDim; i++){
      for (j=0; j<yDim; j++){
         DB("%c", map[j][i]);
      }
      DB("\n");
   }

   //newBridgeVal = bridgeVal - bridges in the original preparedBridges
   for (i=0; i<islands; i++){
      newBridgeVal[i] = bridgeVal[i];
      for (j=0; j<islands; j++){
         assert(preparedBridges[i][j] == preparedBridges[j][i]);
         newBridgeVal[i] -= preparedBridges[i][j];
      }
      assert(newBridgeVal[i] >= 0);
      DB("Bridge val[%d] after prepared bridges = %d\n", i, newBridgeVal[i]);
   }

   //assemble list of potential bridges
   for (i=0; i<islands; i++){
      if (newBridgeVal[i] > 0){
         for (j=0; j<islands; j++){
            if (newBridgeVal[j] > 0){
               if (preparedBridges[i][j] == 2){ //if a bridge of 2 already exists, there's no point in including this in the permutations
                  //bridges[i][j] = bridges[j][i] = 2;
                  DB("=== bridge already included\n");
               }else{
                  if (linkDirections[i][j] != NO_DIRECTION){
                     //make sure this isn't already on the list
                     listed = 0;
                     for (k=0; k<potentials; k++){
                        if (potential[0][k] == j && potential[1][k] == i){
                           listed = 1;
                           k = potentials;
                        }
                     }
                     if (!listed){
                        potential[0][potentials] = i;
                        potential[1][potentials] = j;
                        potential[2][potentials] = preparedBridges[i][j];
                        potentials ++;
                     }
                  }
               }
            }
         }
      }
   }
   for (i=0; i<islands; i++){
      for (j=0; j<islands; j++){
         bridges[i][j] = bridges[j][i] = preparedBridges[i][j]; //permutations will overwrite what they need to
      }
   }

   DB("%d potential bridge locations:\n", potentials);
   for (i=0; i<potentials; i++){
      DB("Island %d (%d bridges) to island %d (%d bridges)\n", potential[0][i], newBridgeVal[potential[0][i]], potential[1][i], newBridgeVal[potential[1][i]]);
   }
   //the variable "potentials" is the number of triplets we need to loop through.
   bruteCap = power3(potentials);
   DB("we're counting up to the number %Ld = 3^%d-1\n", bruteCap-1, potentials);
                                                                                                                          //assert(0);
   for (bruteLoop=0; bruteLoop<bruteCap; bruteLoop++){
      DB("%20Ld %f%% |", bruteLoop, (100.0*bruteLoop/(bruteCap-1)));
      permutationNoGood = 0;
      for (i=0; i<potentials; i++){
         //DB ("(%Ld - %Ld) / %Ld\n", bruteLoop % power(3, i+1), bruteLoop % power(3, i), power(3, i));
         bridges[potential[0][i]][potential[1][i]] = ((bruteLoop % power3(i+1)) - (bruteLoop % power3(i))) / power3(i);
         DB("%c", bridges[potential[0][i]][potential[1][i]]+'0');
         if (bridges[potential[0][i]][potential[1][i]] < potential[2][i]){
                                                                                    //printf("* - bad bridge at potential #%d", i);
            DB("\n");
            i=potentials; //exit loop
            permutationNoGood = 1;
         }else{
            bridges[potential[1][i]][potential[0][i]] = bridges[potential[0][i]][potential[1][i]];
         }
      }
                                                                                         if (bruteLoop % 1000000 == 0) printf("\n%20LdM %f%%", bruteLoop/1000000, (100.0*bruteLoop/bruteCap));
      if (!permutationNoGood){
         DB("|\n");
         //check for solution
         if (validSolution(bridges, islands, bridgeVal, linkDirections, islandX, islandY)){
            bruteLoop = bruteCap;
            solutionFound = 1;
         }
      }
   }
   DB("\n");
   if (!solutionFound) printf("***No solution found***\n");
                                                                                         printf("\n");
}

void buildOutput(char output[MAX_DIM][MAX_DIM], int linkDirections[MAX_ISLANDS][MAX_ISLANDS], int bridges[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int xDim, int yDim, int islands, int bridgeVal[MAX_ISLANDS]){
   int i = 0, j = 0;
   int from = 0, to = 0;
   int n = 0;
   int direction = NO_DIRECTION;
   char bridgeChar = 0;
   for (i=0; i<xDim; i++)
      for (j=0; j<=yDim; j++)
         output[i][j] = ' ';
   for (i=0; i<islands; i++)
      output[islandX[i]][islandY[i]] = bridgeVal[i] + '0'; //draw islands
   for (from=0; from<islands; from++){
      for (to=0; to<islands; to++){
         if (bridges[from][to] > 0){
            direction = linkDirections[from][to];
            if (direction == UP || direction == DOWN){
               bridgeChar = (bridges[from][to] == 1 ? VERT_SINGLE : VERT_DOUBLE);
            }else{
               assert(direction == LEFT || direction == RIGHT);
               bridgeChar = (bridges[from][to] == 1 ? HOR_SINGLE : HOR_DOUBLE);
            }
            switch (direction){
            case UP:
               assert (islandX[from] == islandX[to]);
               for (n=islandY[from]-1; n > islandY[to]; n--)
                  output[islandX[from]][n] = bridgeChar;
               break;
            case DOWN:
               assert (islandX[from] == islandX[to]);
               for (n=islandY[from]+1; n < islandY[to]; n++)
                  output[islandX[from]][n] = bridgeChar;
               break;
            case LEFT:
               assert (islandY[from] == islandY[to]);
               for (n=islandX[from]-1; n > islandX[to]; n--)
                  output[n][islandY[from]] = bridgeChar;
               break;
            case RIGHT:
               assert (islandY[from] == islandY[to]);
               for (n=islandX[from]+1; n < islandX[to]; n++)
                  output[n][islandY[from]] = bridgeChar;
               break;

            default:;
            }
         }
      }
   }
}

void displayOutput(char output[MAX_DIM][MAX_DIM], int xDim, int yDim){
   int i, j;
   for (j=0; j<=yDim; j++){
      for (i=0; i<xDim; i++){
         putchar(output[i][j]);
      }
      putchar('\n');
   }
}