A Number Link Game with Code
The Game : Consider an n × n array of squares. Some of the squares are empty, some are solid, and some non-solid squares are marked by integers 1, 2, 3, … Each integer occupies exactly two different squares on the board. The task of the player is to connect the two occurrences of each integer on the board by a simple path using horizontal and vertical movements alone. No two different paths are allowed to intersect one another. No path may include any solid square (solid squares are forbidden to appear on any path). Finally, all non-solid squares must be filled by the paths.
The Algorithm : To prepare a valid random puzzle with a given board size n × n, we first generate random simple mutually non-intersecting paths on the board. If a few isolated squares remain outside all the generated paths, mark these isolated squares as solid (forbidden). We then supply the endpoints of the paths and the list of the solid squares as the puzzle.
Thus we first generate a solution, and then work out the puzzle from the solution. The paths and the solid squares partition the n × n board. We use a union-find data structure to generate this partition. The data structure deals with the subsets of the set of n^2 squares on the board.
PseudoCode:
- Locate squares (i, j) and (k, l) randomly on the board such that:
(a) (i, j) and (k, l) are neighbors of one another, and
(b) neither (i, j) nor (k, l) belongs to any path generated so far. If no such pair of squares is found on the entire board, return FAILURE /* Here, (i, j) and (k, l) are the first two squares on the new path to be constructed. */ - Make a union of the two union-find trees containing (i, j) and (k, l).
- Repeat so long as the current path can be extended:
Rename (i, j) = (k, l).
Locate a random neighboring square (k, l) of (i, j) such that:
(a) (k, l) does not belong to any path generated so far (including the current one)
(b) the only neighbor (k, l) has on the partially constructed current path is (i, j). - If no such neighbor (k, l) can be found, the path cannot be extended further, so break the loop
- Otherwise, make the union of the two union-find trees to which (i, j) and (k, l) belong.
- Set the endpoint flags of the two squares that are at the beginning and at the end of the new path.
- Return SUCCESS
::CODE::
<div dir="ltr" style="text-align: left;" trbidi="on">
/* Description: Code printing valid tables for the game of flow.
Creator: Vaibhav Agarwal (vaiagarwal96@iitkgp.ac.in) */
#include<stdio .h="">
#include<stdlib .h="">
#include<time .h="">
struct _node
{
struct _node *parent;
int rank;
int path_number;
int endpoint;
};
typedef struct _node node;
/* Name: initboard()
Input: 2D-array of pointers, size of array row/column
Output: --void--
Description: Takes a table of pointers and initializes it. */
void initboard(node ***arr, int n)
{
int i, j;
for (i=0;i<n for="" i="" j="0;j<n;j++){" malloc="" node="" np-="" np="(node" sizeof="">rank = 0;
np->parent = NULL;
np->path_number = 0;
np->endpoint = 0;
arr[i][j] = np;
}
}
}
/***********************/
/* Name: findset()
Input: a node
Output: the set pointer of the set the node belongs to
Description: Takes a node and returns the set pointer. */
node *findset(node *n)
{
if (n->parent != NULL)
n = n->parent;
return n;
}
/************************/
/* Name: setunion()
Input: nodes x and y
Output: --void--
Description: merges the two sets containing x and y.
*/
void setunion(node *x, node *y)
{
x = findset(x);
y = findset(y);
if (x->rank > y->rank)
y->parent = x;
else{
x->parent = y;
if(x->rank == y->rank)
y->rank++;
}
}
/**************************/
/* Name: neighbour()
Input: size of array row/column, 2D-array of pointers
Output: returns the incripted values of k1 and k2 or -1 if fails.
Description: Finds the valid starting points of the flow. */
int neighbour(int n, node ***arr)
{
int i1, i2, j1, j2, ct = 0, flag = 0, a, b,k2;
int k = rand()%(n*n);
while (ct < (n*n)){
k %= (n*n);
i1 = k/n;
j1 = k%n;
if (arr[i1][j1]->path_number==0)
{
int kk = rand()%4;
int cc = 0;
switch (kk)
{
case 0: i2= i1-1;
j2= j1-0;
if(i2>=0 && i2<n arr="" i2="" if="" j2="" n="">path_number==0){
flag=1;
break;
}
}
cc++;
case 1: i2= i1-0;
j2= j1-1;
if(j2>=0 && i2<n arr="" i2="" if="" j2="" n="">path_number==0){
flag=1;
break;
}
}
cc++;
case 2: i2= i1+1;
j2= j1-0;
if(i2<n arr="" i2="" if="" j2="" n="">path_number==0){
flag=1;
break;
}
}
cc++;
case 3: i2= i1-0;
j2= j1+1;
if(i2<n arr="" i2="" if="" j2="" n="">path_number==0){
flag=1;
break;
}
}
cc++;
case 4: if(cc==4)
break;
i2= i1-1;
j2= j1-0;
if(i2>=0 && i2<n arr="" i2="" if="" j2="" n="">path_number==0){
flag=1;
break;
}
}
cc++;
case 5: if(cc==4)
break;
i2= i1-0;
j2= j1-1;
if(j2>=0 && i2<n arr="" i2="" if="" j2="" n="">path_number==0){
flag=1;
break;
}
}
cc++;
case 6: if(cc==4)
break;
i2= i1+1;
j2= j1-0;
if(i2<n arr="" i2="" if="" j2="" n="">path_number==0){
flag=1;
break;
}
}
cc++;
case 7: if(cc==4)
break;
i2= i1-0;
j2= j1+1;
if(i2<n arr="" i2="" if="" j2="" n="">path_number==0){
flag=1;
break;
}
}
cc++;
}
}
if(flag==1)
break;
ct++;
k++;
}
if(ct<n -1="" 0="" 1="" 2d-array="" 4="" and="" are="" arr="" array="" checkneigh="" checks="" column="" ct="0;" description:="" else="" fails.="" find="" i="" if="" ii="k1/n;" input:="" int="" j="k2%n;" jj="k1%n;" k1="" k2="" k="" more="" n="" name:="" neighbouring="" neighbours="" node="" of="" output:="" pointers="" return="" returns="" row="" same="" set.="" size="" than="" the="" there="" true="" vaues="">0 && findset(arr[i-1][j])==findset(arr[ii][jj]))
ct++;
if(i<n-1 arr="" ct="" findset="" i="" if="" ii="" j="" jj="">0 && findset(arr[i][j-1])==findset(arr[ii][jj]))
ct++;
if(j<n-1 arr="" ct="" findset="" i="" if="" ii="" j="" jj="">1)
return 0;
else
return 1;
}
/****************************/
/* Name: valid_next()
Input: starting k, size of array row/column, 2D-array of pointers
Output: returns the value of k2 or -1 if fails.
Description: Finds the next valid points of the flow.
*/
int valid_next(int k, int n, node ***arr)
{
int i1, i2, j1, j2, a, b, kk, stat,ct=0;
int flag=0;
i1= k/n;
j1= k%n;
kk= rand()%4;
switch(kk)
{
case 0: i2= i1-1;
j2= j1-0;
if(i2>=0 && i2<n arr="" i2="" if="" j2="" n="">path_number==0){
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat){
flag=1;
break;
}
}
}
ct++;
case 1: i2= i1-0;
j2= j1-1;
if(j2>=0 && i2<n arr="" i2="" if="" j2="" n="">path_number==0){
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat){
flag=1;
break;
}
}
}
ct++;
case 2: i2= i1+1;
j2= j1-0;
if(i2<n arr="" i2="" if="" j2="" n="">path_number==0){
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat){
flag=1;
break;
}
}
}
ct++;
case 3: i2= i1-0;
j2= j1+1;
if(i2<n arr="" i2="" if="" j2="" n="">path_number==0){
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat){
flag=1;
break;
}
}
}
ct++;
case 4: if(ct==4)
break;
i2= i1-1;
j2= j1-0;
if(i2>=0 && i2<n arr="" i2="" if="" j2="" n="">path_number==0){
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat){
flag=1;
break;
}
}
}
ct++;
case 5: if(ct==4)
break;
i2= i1-0;
j2= j1-1;
if(j2>=0 && i2<n arr="" i2="" if="" j2="" n="">path_number==0){
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat){
flag=1;
break;
}
}
}
ct++;
case 6: if(ct==4)
break;
i2= i1+1;
j2= j1-0;
if(i2<n arr="" i2="" if="" j2="" n="">path_number==0){
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat){
flag=1;
break;
}
}
}
ct++;
case 7: if(ct==4)
break;
i2= i1-0;
j2= j1+1;
if(i2<n arr="" i2="" if="" j2="" n="">path_number==0){
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat){
flag=1;
break;
}
}
}
ct++;
}
//printf("flag- %d\n",flag);
if(flag==0)
return -1;
if(flag){
//printf("value sent- %d\n", i2*n + j2);
return (i2*n)+j2;
}
}
/********************/
/* Name: addpath()
Input: 2D-array of pointers, size of array row/column, path number
Output: returns 1 if a new path can be (or, is) added, 0 if not.
Description: Creates a new flow path.
*/
int addpath(node ***arr, int n, int ptno)
{
int a,b,k1,k2;
int i1,j1,i2,j2;
k2= neighbour( n, arr);
if(k2==-1) //no valid pair found to start with
return 0;
k1= k2/(n*n);
k2= k2%(n*n);
//printf("%d %d\n",k1,k2);
i1= k1/n;
j1= k1%n;
i2= k2/n;
j2= k2%n;
//printf("%d %d\n",i1,j1);
//printf("%d %d\n",i2,j2);
//found i1,j1 and i2,j2
arr[i1][j1]->endpoint= 1;
arr[i2][j2]->path_number= ptno;
arr[i1][j1]->path_number= ptno;
node *n1, *n2;
n1= arr[i1][j1];
n2= arr[i2][j2];
n1= findset(n1);
n2= findset(n2);
setunion(n1, n2);
while(1){
i1= i2;
j1= j2;
k1= (i1*n)+j1;
/******/
k2= valid_next(k1,n,arr);
//printf("k2- %d\n",k2);
if(k2==-1){
arr[i1][j1]->endpoint= 1;
break;
}
i2=k2/n;
j2=k2%n;
//printf("%d %d\n",i2,j2);
arr[i2][j2]->path_number= ptno;
node *n1, *n2;
n1= arr[i1][j1];
n2= arr[i2][j2];
n1= findset(n1);
n2= findset(n2);
setunion(n1,n2);
}
return 1;
}
/************************/
/* Name: printtable()
Input: 2D-array of pointers, size of array row/column
Output: --void--
Description: Prints the question table and the corresponding solution table.
*/
void printtable(node ***arr, int n)
{
int i,j;
printf("Table to be solved:\n");
for(i=0;i<n arr="" for="" i="" if="" j="">endpoint ==1){
if(arr[i][j]->path_number/10==0)
printf("| %d |",arr[i][j]->path_number);
else
printf("| %d|",arr[i][j]->path_number);
}
else if(arr[i][j]->path_number==0)
printf("| X |");
else
printf("| |");
}
printf("\n");
}
printf("\n\nThe solution to the above table:\n");
for(i=0;i<n arr="" for="" i="" if="" j="">path_number != 0){
if(arr[i][j]->path_number/10==0)
printf("| %d |",arr[i][j]->path_number);
else
printf("| %d|",arr[i][j]->path_number);
}
else
printf("| X |");
}
printf("\n");
}
}
/******************/
/* Name: main()
Input: --void--
Output: returns 1
Description: The driver function.
*/
int main(void)
{
srand((unsigned int) time (NULL));
int i, j;
int ct = 1;
// Size of board
int n = 7;
node*** pointers= (node ***)malloc(n*sizeof(node **));
for (i=0; i</n></n></n></n></n></n></n></n></n></n></n-1></n-1></n></n></n></n></n></n></n></n></n></n></time></stdlib></stdio></div>
No comments