/* This is a program that shows that it is *not* possible to solve the "36 CUBE" puzzle from Thinkfun.  
   The puzzle tries to put a collection of 36 pieces of 6 different sizes and 6 different colors into a 
   6x6 grid where each grid location holds one of 6 possible sizes.  A solution has exactly one of each 
   color in every row and column.  The program tries every possible combination until it determines that
   there is no possible way to continue building on the combination.  While it seems that the combinatorics
   would make computer verification impossible, most possible solutions are recognizes as impossible quite
   early in their exploration.  

   The routine search(n,last) is called with 0 as the first argument and last as the number of squares on which
   we seek to find a legal solution.  If last=36, then we are trying to solve the entire puzzle.  The program
   shows that we can find solutions on the first 34 squares (last=34), but not the entire puzzle (last=36).  

*/

#include <stdio.h>



int layout[6][6] = {0, 4, 3, 1, 2, 5,   /* the grid where we put the pieces is a 6x6 where each location allows */
		    1, 2, 5, 0, 4, 3,   /* a single size piece.  These are the sizes associated with the grid */
		    4, 5, 2, 3, 1, 0,   /* locations.  0 means the smallest piece, while 5 is the largest piece */
		    3, 0, 4, 2, 5, 1, 
		    5, 3, 1, 4, 0, 2,
		    2, 1, 0, 5, 3, 4};

char *col[6] = { "red", "yel", "grn", "blu", "ong", "prp" };  
/* we denote the colors by the numbers 0,1,2,3,4,5.  It makes no difference how we order the colors so we
   don't need to worry if this is the "right" order  */


int used[6][6];  /* used[i][j] is a boolean (true/false).  
		    if used[i][j] is true then the ith size jth color piece is already on the board */
int board[6][6]; /* board[i][j] is the color (0-5) that is in the ith row and jth column of the board
		    we use -1 when nothing is there, though if we didn't do this the algorithm would 
		    perform identically */


static int
search(int n, int last) {  /* n is the square we are searching currently.  returns boolean for success  */
  int i,sz,j,r,c;

    if (n == last) {  // if we get to the last position print out the current configuration. 
    for (i=0; i < 6; i++) {
      for (j=0; j < 6; j++) if (board[i][j] >= 0) 
	printf("%s\t",col[board[i][j]]);
      printf("\n");
    }
    return(1);
  }  

  c = n%6;  /* r and c are the row and column corresponding to n.  as n increases we sweep through the
	       rows on the  board in increasing order */
  r = n/6;


  sz = layout[r][c];                              /* sz is the size of the piece that goes in the rth row and cth columun. */
  for (i=0; i < 6; i++) {                         /* try all possible colors */
    if (used[sz][i]) continue;                    /* if the ith color already used for size sz, this color is impossible */
    for (j=0; j < c; j++) if (board[r][j] == i) break;  
    if (j < c) continue;                         /* if ith color already appears in row r, ith color impossible */
    for (j=0; j < r; j++) if (board[j][c] == i) break;
    if (j < r) continue;                         /* if ith color already appears in column c, ith color impossible */
    used[sz][i] = 1;                             /* mark piece of size sz and color i as used */
    board[r][c] = i;                             /* place the ith color on the board */
    if (search(n+1,last)) return(1);             /* note recursive call --- perform this same search on the next board location */
    used[sz][i] = 0;                             /* when finished with search mark the sz,i piece as unused */
    board[r][c] = -1;                            /* mark the board location as empty */
  }
  return(0);
}

main(int argc, char **argv) {
  int i,j,res,num;


  num = atoi(argv[1]);  /* num is the number of positions in the grid we will solve for */
  for (i=0; i < 6; i++) for (j=0; j < 6; j++) {  /* initialize the board to be empty and all pieces to be unused */
    used[i][j] = 0;
    board[i][j] = -1;
  }
  res = search(0,num);  /* find solution for the first num positions.  */
  if (res == 0) printf("couldn't find any solution\n");
}