/*** Implementation of a Las Vegas algorithm for creating random n x n    ***
 *** boards for the numberlink game. At the core of the algorithm is      ***
 *** a Monte Carlo algorithm that may produce boards with some unfilled   ***
 *** squares, but these bad instances occur with very small probability.  ***
 *** We repeat the Monte Carlo algorithm multiple times until we get a    ***
 *** board without any unfilled squares. In contrast with the commonly    ***
 *** available implementations, this implementation gives an infinite     ***
 *** supply of boards to the player. I hope that the boards generated by  ***
 *** this algorithm are decent and interesting, and does not need human   ***
 *** monitoring. The difficulty level increases with the increase in the  ***
 *** size (n) of the board. The maximum supported board size is 64 x 64.  ***
 *** Uniqueness of the solutions is not guaranteed, although more often   ***
 *** than not this algorithm produces boards with unique solutions.       ***/

/*** Author: Abhijit Das (http://cse.iitkgp.ac.in/~abhij/)                ***
 *** Last modified on: 27-Aug-2017                                        ***/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 20
#define MIN_SIZE 4
#define MAX_COLOR 1000
#define N 10
#define FAILURE 0
#define SUCCESS 1

typedef int board[MAX_SIZE][MAX_SIZE]; /* A 2-d array of assigned colors */

/* Initialize each square to be empty (uncolored) */
void initboard ( board B, int n )
{
   int i, j;

   for (i=0; i<n; ++i) for (j=0; j<n; ++j) B[i][j] = 0;
}

/* Function to return the number of colored neighbors of square (k,l) */
int numcolnbrs ( board B, int n, int k, int l )
{
   int cnt = 0;

   if (k == 0) ++cnt; else if (B[k-1][l]) ++cnt;
   if (k == n-1) ++cnt; else if (B[k+1][l]) ++cnt;
   if (l == 0) ++cnt; else if (B[k][l-1]) ++cnt;
   if (l == n-1) ++cnt; else if (B[k][l+1]) ++cnt;

   return cnt;
}

/* Function to return whether a square (k,l) has at most one neighbor with
   the color c. Used during path creation and puzzle printing. */
int onlyonenbr ( board B, int n, int k, int l, int c )
{
   int cnt = 0;

   if (k != 0) { if (B[k-1][l] == c) ++cnt; }
   if (k != n-1) { if (B[k+1][l] == c) ++cnt; }
   if (l != 0) { if (B[k][l-1] == c) ++cnt; }
   if (l != n-1) { if (B[k][l+1] == c) ++cnt; }
   return (cnt <= 1) ? SUCCESS : FAILURE;
}

/* Function to return whether the presence of a square (k,l) in a path leads
   to one or more isolated uncolored squares */
int noisosqr ( board B, int n, int k, int l, int c, int lastnode )
{
   if (lastnode) {  /* if (k,l) is the last node added to the path */
      if ((k != 0) && (B[k-1][l] == 0) && (numcolnbrs(B,n,k-1,l) == 4) && (onlyonenbr(B,n,k-1,l,c) == FAILURE)) return FAILURE;
      if ((k != n-1) && (B[k+1][l] == 0) && (numcolnbrs(B,n,k+1,l) == 4) && (onlyonenbr(B,n,k+1,l,c) == FAILURE)) return FAILURE;
      if ((l != 0) && (B[k][l-1] == 0) && (numcolnbrs(B,n,k,l-1) == 4) && (onlyonenbr(B,n,k,l-1,c) == FAILURE)) return FAILURE;
      if ((l != n-1) && (B[k][l+1] == 0) && (numcolnbrs(B,n,k,l+1) == 4) && (onlyonenbr(B,n,k,l+1,c) == FAILURE)) return FAILURE;
   } else {        /* if (k,l) is the second last node added to the path */
      if ((k != 0) && (B[k-1][l] == 0) && (numcolnbrs(B,n,k-1,l) == 4)) return FAILURE;
      if ((k != n-1) && (B[k+1][l] == 0) && (numcolnbrs(B,n,k+1,l) == 4)) return FAILURE;
      if ((l != 0) && (B[k][l-1] == 0) && (numcolnbrs(B,n,k,l-1) == 4)) return FAILURE;
      if ((l != n-1) && (B[k][l+1] == 0) && (numcolnbrs(B,n,k,l+1) == 4)) return FAILURE;
   }

   return SUCCESS;
}

/* Function to return whether the board contains two adjacent isolated uncolored squares */
int noisosqr2 ( board B, int n, int k, int l )
{
   int i, j, i1, j1, i2, j2;

   i1 = k-2; if (i1 < 0) i1 = 0;
   i2 = k+2; if (i2 >= n) i2 = n-1;
   j1 = l-2; if (j1 < 0) j1 = 0;
   j2 = l+2; if (j2 >= n) j2 = n-1;
   for (i=i1; i<=i2; ++i) for (j=j1; j<=j2-1; ++j) {
      if ((B[i][j] == 0) && (B[i][j+1] == 0) &&
         (numcolnbrs(B,n,i,j)==3) && (numcolnbrs(B,n,i,j+1)==3)) {
         return FAILURE;
      }
   }

   for (i=i1; i<=i2-1; ++i) for (j=j1; j<=j2; ++j) {
      if ((B[i][j] == 0) && (B[i+1][j] == 0) &&
         (numcolnbrs(B,n,i,j)==3) && (numcolnbrs(B,n,i+1,j)==3)) {
         return FAILURE;
      }
   }

   return SUCCESS;
}

/* Function to locate a random uncolored neighbor (k,l) of (i,j). If a
   positive color c is specified, an additional constraint needed during path
   extension is enforced. The function also insures that the choice of
   the neighbor (k,l) does not leave some isolated uncolored squares.*/
int findemptynbr ( board B, int n, int i, int j, int *k, int *l, int c, int stage )
{
   int u, v, i1, j1;

   u = rand() % 4;           /* Start the search from a random direction */
   for (v=0; v<4; ++v) {     /* Search all the four neighbors */
      if (++u == 4) u = 0;   /* Set next direction */
      i1 = i; j1 = j;
      switch (u) {
         case 0: if (i == 0) continue; i1 = i - 1; break;       /* North */
         case 1: if (j == n-1) continue; j1 = j + 1; break;     /* East */
         case 2: if (j == 0) continue; j1 = j - 1; break;       /* West */
         case 3: if (i == n-1) continue; i1 = i + 1; break;     /* South */
      }
      if (B[i1][j1] == 0) {  /* An uncolored neighbor is found */
         if (c) {            /* Check additional constraint during path extension */
            if (onlyonenbr(B,n,i1,j1,c) == FAILURE) continue;
         }

         B[i1][j1] = c;

         /* Check whether the inclusion of (i1,j1) causes any isolated uncolored square */
         if ((noisosqr(B,n,i,j,c,0) == FAILURE) || (noisosqr(B,n,i1,j1,c,1) == FAILURE)) {
            B[i1][j1] = 0;
            continue;
         }

         /* Check whether the inclusion of (i1,j1) causes any pair of adjacent isolated uncolored squares in state 1 only */
         if ((stage == 1) && (noisosqr2(B,n,i1,j1) == FAILURE)) {
            B[i1][j1] = 0;
            continue;
         }

         /* Everything is fine here, so (i1,j1) is a good square found for path extension */
         *k = i1; *l = j1;
         return SUCCESS;
      }
   }

   /* All of the four neighbors are found incapable of extending the path */
   *k = *l = 0;
   return FAILURE;
}

/* Attempt to add a random path to the board. Return SUCCESS or FAILURE. */
int addpath ( board B, int n, int *c, int *covered, int mpl, int stage )
{
   int i, j, k, l, s, t, pathlen, starti, startj;

   ++(*c); /* Use the next color for the new path */

   /* First try to locate uncolored neighboring squares (i,j) and (k,l) */

   s = rand() % (n * n);     /* Start searching from a random square */
   for (t=0; t<n*n; ++t) {   /* Row-major wrap-around search of the entire board */
      if (++s == n*n) s = 0; /* Convert s to (i,j) */
      i = s / n; j = s % n;
      if (B[i][j] == 0) { /* if (i,j) is uncolored */
         B[i][j] = *c;
         if (noisosqr(B,n,i,j,*c,1) == FAILURE) {
            /* If starting a new path at (i,j) gives an isolated uncolored square, discard */
            B[i][j] = 0;
            continue;
         } else if ((stage == 1) && (noisosqr2(B,n,i,j) == FAILURE)) {
            /* If starting a new path at (i,j) gives two adjacent isolated uncolored squares, discard */
            B[i][j] = 0;
            continue;
         } else if (findemptynbr(B,n,i,j,&k,&l,*c,stage) == FAILURE) { /* Try to locate a suitable neighbor */
            B[i][j] = 0;
            continue;
         } else { /* A path may start with the squares (i,j) and (k,l) */
            break;
         }
      }
   }

   if (t == n*n) { --(*c); return FAILURE; }

   pathlen = 2; *covered += 2;
   printf("    Path No %2d: (%d,%d) (%d,%d)", *c, i, j, k, l);

   /* Remember for Stage 2 */
   starti = i; startj = j;

   /* Stage 1: Move forward */
   while (1) {
      i = k; j = l;

      /* If the length of the current path has already reached the allowed
         limit, terminate the path. Otherwise, try to locate an uncolored
         neighbor (k,l) of the last square (i,j) added to the path, such
         that (i,j) is the only neighbor of (k,l) on the partially constructed
         path, and the choice of (k,l) to augment the path does not leave
         any isolated uncolored square. */
      if ((pathlen >= mpl) || (findemptynbr(B,n,i,j,&k,&l,*c,stage) == FAILURE)) {
         break;
      }

      printf(" (%d,%d)", k, l);  /* extend the current path by adding (k,l) */
      ++pathlen; ++(*covered);
   }

   /* Stage 2: Move backward from the starting point */

   k = starti; l = startj;

   while (1) {
      i = k; j = l;

      /* If the length of the current path has already reached the allowed
         limit, terminate the path. Otherwise, try to locate an uncolored
         neighbor (k,l) of the last square (i,j) added to the path, such
         that (i,j) is the only neighbor of (k,l) on the partially constructed
         path, and the choice of (k,l) to augment the path does not leave
         any isolated uncolored square. */
      if ((pathlen >= mpl) || (findemptynbr(B,n,i,j,&k,&l,*c,stage) == FAILURE)) {
         printf("\n");
         return SUCCESS;
      }

      printf(" (%d,%d)", k, l);  /* extend the current path by adding (k,l) */
      ++pathlen; ++(*covered);
   }
}

void printboard ( board B, int n, int c )
{
   int i, j, k, t;
   int perm[MAX_COLOR+1];

   /* Since paths generated in the earlier invocations of addpath() have a
      tendency to be longer than those generated in the later invocations,
      the original path numbers may offer non-trivial clues to the player.
      Randomly renaming the paths removes these clues. */
   printf("\n+++ Renaming paths...\n");
   for (k=1; k<=c; ++k) perm[k] = k;
   for (k=1; k<=c; ++k) {
      i = 1 + rand() % c; j = 1 + rand() % c;
      t = perm[i]; perm[i] = perm[j]; perm[j] = t;
   }
   for (k=1; k<=c; ++k) printf("    Path %2d renamed as Path %2d\n", k, perm[k]);

   printf("\n+++ The puzzle\n");
   for (i=0; i<n; ++i) {
      printf("    +"); for (j=0; j<n; ++j) printf("----+"); printf("\n");
      printf("    |");
      for (j=0; j<n; ++j) {
         if (B[i][j] == 0) printf("XXXX|");
         else if (onlyonenbr(B,n,i,j,B[i][j]) == SUCCESS) printf("%3d |", perm[B[i][j]]);
         else printf("    |");
      }
      printf("\n");
   }
   printf("    +"); for (j=0; j<n; ++j) printf("----+"); printf("\n");

   printf("\n+++ The solution\n");
   for (i=0; i<n; ++i) {
      printf("    +"); for (j=0; j<n; ++j) printf("----+"); printf("\n");
      printf("    |");
      for (j=0; j<n; ++j) {
         if (B[i][j] == 0) printf("XXXX|");
         else printf("%3d |", perm[B[i][j]]);
      }
      printf("\n");
   }
   printf("    +"); for (j=0; j<n; ++j) printf("----+"); printf("\n");
}

int main ( int argc, char *argv[] )
{
   int n, color, oldcovered, covered, badboard, attno = 0, maxpathlen;
   board B;

   n = (argc > 1) ? atoi(argv[1]) : N;
   if ((n < MIN_SIZE) || (n > MAX_SIZE)) {
      fprintf(stderr, "*** Board size must be in the range %d-%d\n", MIN_SIZE, MAX_SIZE);
      exit(1);
   }

   srand((unsigned int)time(NULL));

   if (n <= 5) maxpathlen = (n * n) / 2;
   else if (n <= 7) maxpathlen = (n * n) / 3;
   else if (n <= 10) maxpathlen = (n * n) / 4;
   else if (n <= 15) maxpathlen = (n * n) / 5;
   else maxpathlen = (n * n) / 6;

   /* Las Vegas loop based on the Monte Carlo algorithm based on addpath().
      Although many precautions are taken to avoid uncolored isolated squares,
      their complete elimination is not guaranteed by an interation of the loop.
      So we repeat until a board with no uncolored isolated squares is
      available. */
   do {
      color = covered = badboard = 0; ++attno;

      printf("\n+++ Initializing board...\n");
      initboard(B,n);

      printf("\n+++ Attempting to add new paths...\n");
      printf("+++ Stage 1\n");
      while (1) {
         oldcovered = covered;
         if (addpath(B,n,&color,&covered,maxpathlen,1) == FAILURE) break;
         if (covered - oldcovered == 2) badboard = 1;
      }
      if (covered < n*n) {
         printf("+++ Stage 2\n");
         while (1) {
            oldcovered = covered;
            if (addpath(B,n,&color,&covered,maxpathlen,2) == FAILURE) break;
            if (covered - oldcovered == 2) badboard = 1;
         }
      }
      printf("Attempt number = %d, covered = %d, badboard = %d\n", attno, covered, badboard);
   } while ((badboard) || (covered < n*n));

   printboard(B,n,color);

   exit(0);
}

/*** End of numberlinkBoardGeneratorv2.c ***/