2-dimensional array impossible fill-up algorithm!!

[mike_fg]

What would be the algorithm in order to fill-up a 2-dimensional array, when it should be done according to the following rules and only:
1.The 2d-array must be nxn, n>=4
2.Place number 1 in the first row-first column box. Next numbers (up to n²) must be placed 3 positions right,left,up or down from the previous number OR 2 positions up-left,up-right,down-left or down-right from the previous number.
3.The 2d-array of nxn type must be filled up to number n² leaving no box empty!!

An example would be for n=5:
01 19 16 04 20
14 24 08 11 23
17 05 21 18 06
02 10 15 03 09
13 25 07 12 22

I want to make a programm in ANSI-C, based on the above algorithm ...which I don't know!!
I guess it must be recursive or/and involving
back-tracking.

Thanx in advance!!

[Zachm]

A recursive function that does that (you might want consider replacing recursion call stack with stack class to avoid overflow with large arrays).

#define TRUE 1
#define FALSE 0
#define EMPTY 0

int FillCells(int **array,int i, int j,int n, int count)
{
array[i][j] = count;

//Try filling for 4 cells to left /right /up /down.
if (i-3 >= 0 && array[i-3][j] != EMPTY)
{
if (FillCells(array, i-3, j, n, count+1))
return TRUE;
}

if (i+3 < n && array[i+3][j] != EMPTY)
{
if (FillCells(array, i+3, j, n,count+1))
return TRUE;
}

if (j-3 >= 0 && array[i][j-3] != EMPTY)
{
if (FillCells(array, i, j-3, n, count+1))
return TRUE;
}

if (j+3 < n && array[i][j+3] != EMPTY)
{
if (FillCells(array, i, j+3, n,count+1))
return TRUE;
}

//Now try for the diagonal cells
if (i+2 < n && j+2 < n && array[i+2][j+2] != EMPTY)
{
if (FillCells(array, i+2, j+2, n,count+1))
return TRUE;
}

if (i-2 >= 0 && j+2 < n && array[i-2][j+2] != EMPTY)
{
if (FillCells(array, i-2, j+2, n,count+1))
return TRUE;
}

if (i+2 < n && j-2 >= 0 && array[i+2][j-2] != EMPTY)
{
if (FillCells(array, i+2, j-2, n,count+1))
return TRUE;
}

if (i-2 >= 0 && j-2 >= 0 && array[i-2][j-2] != EMPTY)
{
if (FillCells(array, i-2, j-2, n,count+1))
return TRUE;
}

array[i][j] = EMPTY;

return FALSE;
}


The code wasn't checked and might be with errors or mistakes but the idea should be clear. The array must be initialized with zeros before start of run.
n is the size of the array dimension. The depth of the call stack is O(n^2).

call this function with the 1st cell index, e.g. :

FillCells(array, 0 , 0, n, 1);


Good luck !

[mike_fg]

Thnx for the quick reply!!
I've created a programm based on your fill-function but the output when the 2d-array is printed is full of zeros:(

For example, the output of this programm..

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define EMPTY 0

int FillCells(int **, int, int, int, int);

main()
{
int n = 6;
int k,l,i;
int** array;

array =(int**)calloc(n,sizeof(int *));
if(array==NULL) {printf("\nErroR\n"); return;}
for(i = 0; i < n; i++){
*(array+i) =(int*)calloc(n,sizeof(int));
if(*(array+i)==NULL) {printf("\nErroR\n"); return;}}

FillCells(array, 0 , 0, n, 1);

for (k=0 ; k < n ; k++){
for (l=0 ; l < n ; l++)
printf("%3d ", array[k][l]);
printf("\n");}

system("pause");
}

int FillCells(int **array,int i, int j,int n, int count)
{
array[i][j] = count;
int k,l;

//Try filling for 4 cells to left /right /up /down.
if (i-3 >= 0 && array[i-3][j] != EMPTY)
{
if (FillCells(array, i-3, j, n, count+1))
return TRUE;
}

if (i+3 < n && array[i+3][j] != EMPTY)
{
if (FillCells(array, i+3, j, n,count+1))
return TRUE;
}

if (j-3 >= 0 && array[i][j-3] != EMPTY)
{
if (FillCells(array, i, j-3, n, count+1))
return TRUE;
}

if (j+3 < n && array[i][j+3] != EMPTY)
{
if (FillCells(array, i, j+3, n,count+1))
return TRUE;
}

//Now try for the diagonal cells
if (i+2 < n && j+2 < n && array[i+2][j+2] != EMPTY)
{
if (FillCells(array, i+2, j+2, n,count+1))
return TRUE;
}

if (i-2 >= 0 && j+2 < n && array[i-2][j+2] != EMPTY)
{
if (FillCells(array, i-2, j+2, n,count+1))
return TRUE;
}

if (i+2 < n && j-2 >= 0 && array[i+2][j-2] != EMPTY)
{
if (FillCells(array, i+2, j-2, n,count+1))
return TRUE;
}

if (i-2 >= 0 && j-2 >= 0 && array[i-2][j-2] != EMPTY)
{
if (FillCells(array, i-2, j-2, n,count+1))
return TRUE;
}

array[i][j] = EMPTY;


return FALSE;
}

is...

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

[Zachm]

Sorry for a bit buggy code :(. I coded it in a bit of a haste. I had a wrong condition in the function - instead of checking for !=EMPTY, I shouldv'e checked for ==EMPTY. I forgot to add stopping condition when the array was filled (n*n cells were filled).
As for your code, you didn't initialize the array with zeros.

I've fixed your code and now it works better, but still has some problems.
On certain n sizes the function hangs (e.g. n = 10). I promise to check this further when I have the time, it seems like I was overlooking something.


#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define EMPTY 0

int FillCells(int **, int, int, int, int);

int main()
{
int n = 6;
int k,l,i;
int** array;

array =(int**)calloc(n,sizeof(int *));
if(array==NULL) {printf("\nErroR\n"); return 1;}
for(i = 0; i < n; i++){
*(array+i) =(int*)calloc(n,sizeof(int));
if(*(array+i)==NULL) {printf("\nErroR\n"); return 1;}}

for (i = 0; i < n; i++)
for (k = 0; k <n; k++)
array[i][k] = EMPTY;

FillCells(array, 0 , 0, n, 1);

for (k=0 ; k < n ; k++){
for (l=0 ; l < n ; l++)
printf("%3d ", array[k][l]);
printf("\n");}

system("pause");

return 0;
}

int FillCells(int **array,int i, int j,int n, int count)
{
array[i][j] = count;

if (count == n*n)
return TRUE;

//Try filling for 4 cells to left /right /up /down.
if (i-3 >= 0 && array[i-3][j] == EMPTY)
{
if (FillCells(array, i-3, j, n, count+1))
return TRUE;
}

if (i+3 < n && array[i+3][j] == EMPTY)
{
if (FillCells(array, i+3, j, n,count+1))
return TRUE;
}

if (j-3 >= 0 && array[i][j-3] == EMPTY)
{
if (FillCells(array, i, j-3, n, count+1))
return TRUE;
}

if (j+3 < n && array[i][j+3] == EMPTY)
{
if (FillCells(array, i, j+3, n,count+1))
return TRUE;
}

//Now try for the diagonal cells
if (i+2 < n && j+2 < n && array[i+2][j+2] == EMPTY)
{
if (FillCells(array, i+2, j+2, n,count+1))
return TRUE;
}

if (i-2 >= 0 && j+2 < n && array[i-2][j+2] == EMPTY)
{
if (FillCells(array, i-2, j+2, n,count+1))
return TRUE;
}

if (i+2 < n && j-2 >= 0 && array[i+2][j-2] == EMPTY)
{
if (FillCells(array, i+2, j-2, n,count+1))
return TRUE;
}

if (i-2 >= 0 && j-2 >= 0 && array[i-2][j-2] == EMPTY)
{
if (FillCells(array, i-2, j-2, n,count+1))
return TRUE;
}

array[i][j] = EMPTY;

return FALSE;
}

[mike_fg]

Sorry for a bit buggy code :(. I coded it in a bit of a haste. I had a wrong condition in the function - instead of checking for !=EMPTY, I shouldv'e checked for ==EMPTY. I forgot to add stopping condition when the array was filled (n*n cells were filled).
As for your code, you didn't initialize the array with zeros.

I've fixed your code and now it works better, but still has some problems.
On certain n sizes the function hangs (e.g. n = 10). I promise to check this further when I have the time, it seems like I was overlooking something.
No need to be sorry m8, respect!!
It's not like I'm in a hurry, it just seems a very interesting problem for me to solve and to become more familiar with the recursion stuff etc because I'm still in the learning process and I learn a lot from this forum!!

Hope I can help too when I grow more algorithm-mature :D