what is wrong with this code ? hi-q

[Niklaus]

Hi,
Can someone point out what is wrong with this code ? How can i make
it better optimize it. When run it gives me seg fault in linux. But
windows it works fine(runs for a long time).

Do we have something like stack size growing enormously and then
saying you can't access ,so a segfault ?

It would be helpful if someone can run the code and give me the
output. It takes a long time on my PC.

Please give me comments about how to code better . This is just a hi-q
problem solved using brute force approach.

Here is the code.
------------BEGIN--------------------
#include<stdio.h>
#define SIZE 7
int a[SIZE][SIZE];
#define NOTVALID -1
#define HOLE 8
#define COIN 9
#define TRUE 1
#define FALSE 0

void
print_array (void)
{
int i, j;
for (i = 0; i < SIZE; i++)
{
printf ("\n");
for (j = 0; j < SIZE; j++)
printf (" %2c",
(a[i][j] == NOTVALID ? 32 : (a[i][j] == HOLE ? 48 : 49)));
}
printf ("\n#########################\n");
}

void
initialize (void)
{
int i, j;
for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
a[i][j] = NOTVALID;

for (i = 2; i < 5; i++)
for (j = 0; j < SIZE; j++)
a[i][j] = COIN;
for (i = 0; i < SIZE; i++)
for (j = 2; j < 5; j++)
a[i][j] = COIN;
a[3][3] = HOLE;
}

int
within_l (int m, int n)
{
if (m < 0 || m > (SIZE - 1) || n < 0 || n > (SIZE - 1))
return FALSE;
if (a[m][n] == NOTVALID)
return FALSE;
return TRUE;
}

/* if i,j is a hole */
int
validposition1 (int i, int j)
{
if (within_l (i - 2, j) && (a[i - 1][j] == COIN) && a[i-2][j] ==
COIN )
return TRUE;
return FALSE;
}

int
validposition2 (int i, int j)
{
if (within_l (i + 2, j) && (a[i + 1][j] == COIN) && a[i+2][j] ==
COIN )
return TRUE;
return FALSE;
}

int
validposition3 (int i, int j)
{
if (within_l (i, j - 2) && (a[i][j - 1] == COIN) && a[i][j-2] ==
COIN )
return TRUE;
return FALSE;
}

int
validposition4 (int i, int j)
{
if (within_l (i, j + 2) && (a[i][j + 1] == COIN) && a[i][j+2] ==
COIN )
return TRUE;
return FALSE;
}

int isonlythat(void)
{
int i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
if(a[i][j] == COIN && (i!=3 ||j!=3))
return FALSE;
if(a[3][3] == HOLE)
return FALSE;
return TRUE;
}

void
hiq (int p, int q, int count)
{
int flag = 0, i, j, tmp;
// print_array();
if (validposition1 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p - 1][q] = HOLE;
a[p - 2][q] = HOLE;
hiq (p - 2, q, count + 1);
hiq (p - 1, q, count + 1);
a[p][q] = HOLE;
a[p - 1][q] = COIN;
a[p - 2][q] = COIN;
}

if (validposition2 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p + 1][q] = HOLE;
a[p + 2][q] = HOLE;
hiq (p + 2, q, count + 1);
hiq (p + 1, q, count + 1);
a[p][q] = HOLE;
a[p + 1][q] = COIN;
a[p + 2][q] = COIN;
}

if (validposition3 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p][q - 1] = HOLE;
a[p][q - 2] = HOLE;
hiq (p, q - 2, count + 1);
hiq (p, q - 1, count + 1);
a[p][q] = HOLE;
a[p][q - 1] = COIN;
a[p][q - 2] = COIN;
}

if (validposition4 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p][q + 1] = HOLE;
a[p + 2][q + 2] = HOLE;
hiq (p, q + 2, count + 1);
hiq (p, q + 1, count + 1);
a[p][q] = HOLE;
a[p][q + 1] = COIN;
a[p][q + 2] = COIN;
}
if (flag == 0)
{
tmp = 0;

for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
if (a[i][j] == HOLE)
{
if (validposition1 (i, j) || validposition2 (i, j)
|| validposition3 (i, j) || validposition4 (i, j))
{
tmp = 1;
hiq (i, j, count + 1);
}
}

if (tmp == 0 )
{
if(isonlythat())
print_array ();
else
return;
}
else
return;
}

}

int
main ()
{
initialize ();
print_array ();
hiq (3, 3, 0);
return 0;
}

---------------------END--------------------

[Darrell Grainger]

On Wed, 2 Jun 2004, Niklaus wrote:

Hi,
Can someone point out what is wrong with this code ? How can i make
it better optimize it. When run it gives me seg fault in linux. But
windows it works fine(runs for a long time).
I hear this a lot from students. They learn to program C over the summer
between highschool and university. They trying using code they created on
Windows on our Solaris or Linux machines and it seg faults.

Most the time the code has undefined behaviour. On the Windows machine it
works. On the Unix machine it does not. Undefined behaviour means that
anything can happen. Other times the code is actually corrupting memory.
The Windows machine is happy to let you write to memory you shouldn't be.
The Linux machine will seg fault.
Do we have something like stack size growing enormously and then
saying you can't access ,so a segfault ?
First, an implementation doesn't necessarily have a stack. Even if it did,
the behaviour would be dependant on the OS and compiler. If a stack
overflow does happen it is more likely that the overflowing data is
corrupting program code. Once execution reaches the corrupted program code
you get a seg fault.
It would be helpful if someone can run the code and give me the
output. It takes a long time on my PC.
You might want to hang out in a newsgroup that uses your compiler and OS
or in comp.programming. Learning how to debug these problems would be
good. An old proverb goes:

Give a man a fish and he is fed for a day.
Teach a man to fish and he is fed for life.

Don't ask people to debug your code for you; ask people to teach you how
to debug your code.
Please give me comments about how to code better . This is just a hi-q
problem solved using brute force approach.

Here is the code.
------------BEGIN--------------------
#include<stdio.h>
#define SIZE 7
int a[SIZE][SIZE];
Global variables make debugging harder. You should try to design without
using global variables.
#define NOTVALID -1
#define HOLE 8
#define COIN 9
#define TRUE 1
#define FALSE 0

void
print_array (void)
{
int i, j;
for (i = 0; i < SIZE; i++)
{
printf ("\n");
for (j = 0; j < SIZE; j++)
printf (" %2c",
(a[i][j] == NOTVALID ? 32 : (a[i][j] == HOLE ? 48 : 49)));
}
This is called 'magic numbers'. I've been coding long enough to know that
you are assuming an ASCII system. The 32 will print a space, the 48 will
print a zero and the 49 will print a one. Try using:

(a[i][j] == NOTVALID ? ' ' : (a[i][j] == HOLE ? '0' : '1'))

This is just good coding practice. It will not fix your seg fault problem.
printf ("\n#########################\n");
}
The for loops did not access an array out of bounds so this code seems
fine to me.
void
initialize (void)
{
int i, j;
for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
a[i][j] = NOTVALID;
These are all valid ranges for the array a so no seg fault here.
for (i = 2; i < 5; i++)
for (j = 0; j < SIZE; j++)
a[i][j] = COIN;
A little whitespace would be nice. Why the magic numbers for the outer
loop? If I scroll back up I can see that the array has the range of 0 to
6. Thus setting i from 2 to 4 is fine. What if I change the value of SIZE
to something smaller then 5? This could be a problem.

Additionally, if you know you are going to be changing the values of
a[2][0] to a[4][SIZE-1], why initialize them with NOTVALID? I'd write it
as one double for loop or something that initialized the first bit as
NOTVALID, drops to the second double for loop but has the second loop
start where the last left off, i.e.

for(i = 0; i < 2; i++)
for(j = 0; j < SIZE; j++)
a[i][j] = NOTVALID;

for( ; i < 5; i++)
for(j = 0; j < SIZE; j++)
a[i][j] = COIN;

Mind you, if you are looking to improve performance, initialize is
probably call once. Look to improving code that is called many times.
for (i = 0; i < SIZE; i++)
for (j = 2; j < 5; j++)
a[i][j] = COIN;
a[3][3] = HOLE;
}

int
within_l (int m, int n)
{
if (m < 0 || m > (SIZE - 1) || n < 0 || n > (SIZE - 1))
return FALSE;
Good check. Guarantees you will not access outside the array bounds.
if (a[m][n] == NOTVALID)
return FALSE;
return TRUE;
}

/* if i,j is a hole */
int
validposition1 (int i, int j)
{
if (within_l (i - 2, j) && (a[i - 1][j] == COIN) && a[i-2][j] ==
COIN )
return TRUE;
return FALSE;
}
What if i == 0? Then you will be accessing a[-1][j]. Or if i == 1 and
a[0][j] == COIN it will evaluate a[i-2][j] or a[-1][j]. This is a
potential spot for a seg fault. If debugging, this is a good spot for a
breakpoint and variable watch of i. With no guards, you can also call this
function with bad values of j and get a seg fault.
int
validposition2 (int i, int j)
{
if (within_l (i + 2, j) && (a[i + 1][j] == COIN) && a[i+2][j] ==
COIN )
return TRUE;
return FALSE;
}
Same sort of thing as the previous function but this time you want to look
for i+1 and i+2 greater than SIZE-1.
int
validposition3 (int i, int j)
{
if (within_l (i, j - 2) && (a[i][j - 1] == COIN) && a[i][j-2] ==
COIN )
return TRUE;
return FALSE;
}
More of the same thing.
int
validposition4 (int i, int j)
{
if (within_l (i, j + 2) && (a[i][j + 1] == COIN) && a[i][j+2] ==
COIN )
return TRUE;
return FALSE;
}
More of the same thing.
int isonlythat(void)
{
int i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
if(a[i][j] == COIN && (i!=3 ||j!=3))
return FALSE;
if(a[3][3] == HOLE)
return FALSE;

return TRUE;
}

void
hiq (int p, int q, int count)
{
int flag = 0, i, j, tmp;
// print_array();
if (validposition1 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p - 1][q] = HOLE;
a[p - 2][q] = HOLE;
What values does p take on? This is potential for array out of bounds.
hiq (p - 2, q, count + 1);
hiq (p - 1, q, count + 1);
a[p][q] = HOLE;
a[p - 1][q] = COIN;
a[p - 2][q] = COIN;
}

if (validposition2 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p + 1][q] = HOLE;
a[p + 2][q] = HOLE;
hiq (p + 2, q, count + 1);
hiq (p + 1, q, count + 1);
a[p][q] = HOLE;
a[p + 1][q] = COIN;
a[p + 2][q] = COIN;
}

if (validposition3 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p][q - 1] = HOLE;
a[p][q - 2] = HOLE;
hiq (p, q - 2, count + 1);
hiq (p, q - 1, count + 1);
a[p][q] = HOLE;
a[p][q - 1] = COIN;
a[p][q - 2] = COIN;
}

if (validposition4 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p][q + 1] = HOLE;
a[p + 2][q + 2] = HOLE;
hiq (p, q + 2, count + 1);
hiq (p, q + 1, count + 1);
a[p][q] = HOLE;
a[p][q + 1] = COIN;
a[p][q + 2] = COIN;
}
All this index-1, index-2, index+1 and index+2 instances are places for an
array out of bounds. Step through your code and see where they go out of
bounds.
if (flag == 0)
{
tmp = 0;

for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
if (a[i][j] == HOLE)
{
if (validposition1 (i, j) || validposition2 (i, j)
|| validposition3 (i, j) || validposition4 (i, j))
{
tmp = 1;
hiq (i, j, count + 1);
}
}

if (tmp == 0 )
{
if(isonlythat())
print_array ();
else
return;
}
else
return;
}

}

int
main ()
{
initialize ();
print_array ();
hiq (3, 3, 0);
return 0;
}

---------------------END--------------------

--
Send e-mail to: darrell at cs dot toronto dot edu
Don't send e-mail to vi************@whitehouse.gov

[I. Appel]

> On Wed, 2 Jun 2004, Niklaus wrote:

int
within_l (int m, int n)
{
if (m < 0 || m > (SIZE - 1) || n < 0 || n > (SIZE - 1))
return FALSE;

Good check. Guarantees you will not access outside the array bounds.

if (within_l (i - 2, j) && (a[i - 1][j] == COIN) && a[i-2][j] ==
COIN )
return TRUE;
return FALSE;
}

What if i == 0? Then you will be accessing a[-1][j]. Or if i == 1 and
a[0][j] == COIN it will evaluate a[i-2][j] or a[-1][j]. This is a
potential spot for a seg fault. If debugging, this is a good spot for a
breakpoint and variable watch of i. With no guards, you can also call this
function with bad values of j and get a seg fault.

That stuff is checked in within_l, so seg fault is somewhere else.
The only thing I dislike in this function is parens around first
comparation,
while there none around second one.

Ivan.

[Barry Schwarz]

On 2 Jun 2004 04:37:56 -0700, ni*****@gamebox.net (Niklaus) wrote:

Hi,
Can someone point out what is wrong with this code ? How can i make
it better optimize it. When run it gives me seg fault in linux. But
windows it works fine(runs for a long time).
Give us a fighting chance. Tell us where it fails.

Do we have something like stack size growing enormously and then
saying you can't access ,so a segfault ?
Since hiq is called recursively, this is possible.

It would be helpful if someone can run the code and give me the
output. It takes a long time on my PC.

Please give me comments about how to code better . This is just a hi-q
problem solved using brute force approach.

Here is the code.
------------BEGIN--------------------
#include<stdio.h>
#define SIZE 7
int a[SIZE][SIZE];
#define NOTVALID -1
#define HOLE 8
#define COIN 9
#define TRUE 1
#define FALSE 0

void
print_array (void)
{
int i, j;
for (i = 0; i < SIZE; i++)
{
printf ("\n");
for (j = 0; j < SIZE; j++)
printf (" %2c",
(a[i][j] == NOTVALID ? 32 : (a[i][j] == HOLE ? 48 : 49)));
What are 32, 48, and 49? They are not valid characters on my system.
If you mean blank, 0, and 1, then use the appropriate character
constants ' ', '0', and '1'.
}
printf ("\n#########################\n");
}

void
initialize (void)
{
int i, j;
for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
a[i][j] = NOTVALID;

for (i = 2; i < 5; i++)
for (j = 0; j < SIZE; j++)
a[i][j] = COIN;
for (i = 0; i < SIZE; i++)
for (j = 2; j < 5; j++)
a[i][j] = COIN;
a[3][3] = HOLE;
}

int
within_l (int m, int n)
{
if (m < 0 || m > (SIZE - 1) || n < 0 || n > (SIZE - 1))
return FALSE;
if (a[m][n] == NOTVALID)
return FALSE;
return TRUE;
}

/* if i,j is a hole */
int
validposition1 (int i, int j)
{
if (within_l (i - 2, j) && (a[i - 1][j] == COIN) && a[i-2][j] ==
COIN )
return TRUE;
return FALSE;
}

int
validposition2 (int i, int j)
{
if (within_l (i + 2, j) && (a[i + 1][j] == COIN) && a[i+2][j] ==
COIN )
return TRUE;
return FALSE;
}

int
validposition3 (int i, int j)
{
if (within_l (i, j - 2) && (a[i][j - 1] == COIN) && a[i][j-2] ==
COIN )
return TRUE;
return FALSE;
}

int
validposition4 (int i, int j)
{
if (within_l (i, j + 2) && (a[i][j + 1] == COIN) && a[i][j+2] ==
COIN )
return TRUE;
return FALSE;
}

int isonlythat(void)
{
int i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
if(a[i][j] == COIN && (i!=3 ||j!=3))
return FALSE;
You code uses both tabs and spaces for indenting, sometimes both on
the same line. This really screws it up for people trying to help.
Posted message should use only spaces. And while you are at it, learn
to indent consistently.


if(a[3][3] == HOLE)
return FALSE;
return TRUE;
}

void
hiq (int p, int q, int count)
In my test, I uncommented the call to print_array and saw hiq being
called with (3,3,0), (1,3,1), (2,3,2), (4,3,3), 6,3,4), (3,3,5),
(3,1,6), (1,3,7), (3,3,8), and (5,3,9). At this point, print_array
generated
1 1 1
1 1 1
1 1 1 0 1 1 1
1 0 0 1 0 1 1
1 1 1 1 1 1 1
1 0 1 0
1 0 1

It is obvious that the last 0 on line 6 is wrong. Maybe this will
help you spot the error.

The next set of calls were (2,3,10), (0,3,11), (1,3,12), (3,3,13),
(2,3,14), (2,1,15), (0,3,16), (2,3,17), (2,5,18), (2,2,19), and
(0,2,20). At this point, print_array produced
0 1 1
0 0 1
1 0 1 1 0 1 1
1 0 0 0 0 1 1
1 1 1 1 1 0 1
1 0 1 0
1 0 1

The next call was (0,4,21) and print_array produced
1 0 1
0 0 1
1 0 1 1 0 1 1
1 0 0 0 0 1 1
1 1 1 1 1 0 1
1 0 1 0
1 0 1

This is an illegal move in the game. The top row should be 1 0 0.
Maybe this will help you some.
{
int flag = 0, i, j, tmp;
// print_array();
if (validposition1 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p - 1][q] = HOLE;
a[p - 2][q] = HOLE;
hiq (p - 2, q, count + 1);
hiq (p - 1, q, count + 1);
a[p][q] = HOLE;
a[p - 1][q] = COIN;
a[p - 2][q] = COIN;
}

if (validposition2 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p + 1][q] = HOLE;
a[p + 2][q] = HOLE;
hiq (p + 2, q, count + 1);
hiq (p + 1, q, count + 1);
a[p][q] = HOLE;
a[p + 1][q] = COIN;
a[p + 2][q] = COIN;
}

if (validposition3 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p][q - 1] = HOLE;
a[p][q - 2] = HOLE;
hiq (p, q - 2, count + 1);
hiq (p, q - 1, count + 1);
a[p][q] = HOLE;
a[p][q - 1] = COIN;
a[p][q - 2] = COIN;
}

if (validposition4 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p][q + 1] = HOLE;
a[p + 2][q + 2] = HOLE;
hiq (p, q + 2, count + 1);
hiq (p, q + 1, count + 1);
a[p][q] = HOLE;
a[p][q + 1] = COIN;
a[p][q + 2] = COIN;
}
if (flag == 0)
{
tmp = 0;

for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
if (a[i][j] == HOLE)
{
if (validposition1 (i, j) || validposition2 (i, j)
|| validposition3 (i, j) || validposition4 (i, j))
{
tmp = 1;
hiq (i, j, count + 1);
}
}

if (tmp == 0 )
{
if(isonlythat())
print_array ();
else
return;
}
else
return;
}

}

int
main ()
{
initialize ();
print_array ();
hiq (3, 3, 0);
return 0;
}

---------------------END--------------------

<<Remove the del for email>>

[Niklaus]

Hi,
Thank you for the help. I made a small typo . The actual code is
below. It only had an error .
Well the limits are being checked in within_l. I have made the
modifications.

Even i *feel*(i may be wrong) that because of a lot of backtracking
the stack size setup by OS for the program is small so we have
segfault ?

--------------BEGIN----------------
#include<stdio.h>
#define SIZE 7
int a[SIZE][SIZE];
#define NOTVALID -1
#define HOLE 8
#define COIN 9
#define TRUE 1
#define FALSE 0

void
print_array (void)
{
int i, j;
for (i = 0; i < SIZE; i++)
{
printf ("\n");
for (j = 0; j < SIZE; j++)
printf (" %2c",
(a[i][j] == NOTVALID ? ' ' : (a[i][j] == HOLE ? '0' : '1')));
}
printf ("\n#########################\n");
}

void
initialize (void)
{
int i, j;
for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
a[i][j] = NOTVALID;

for (i = 2; i < 5; i++)
for (j = 0; j < SIZE; j++)
a[i][j] = COIN;
for (i = 0; i < SIZE; i++)
for (j = 2; j < 5; j++)
a[i][j] = COIN;
a[3][3] = HOLE;
}

int
within_l (int m, int n)
{
if (m < 0 || m > (SIZE - 1) || n < 0 || n > (SIZE - 1))
return FALSE;

if (a[m][n] == NOTVALID)
return FALSE;

return TRUE;
}

/* if i,j is a hole */
int
validposition1 (int i, int j)
{
if (within_l (i - 2, j) && (a[i - 1][j] == COIN) && a[i-2][j] ==
COIN )
return TRUE;
return FALSE;
}

int
validposition2 (int i, int j)
{
if (within_l (i + 2, j) && (a[i + 1][j] == COIN) && a[i+2][j] ==
COIN )
return TRUE;
return FALSE;
}

int
validposition3 (int i, int j)
{
if (within_l (i, j - 2) && (a[i][j - 1] == COIN) && a[i][j-2] ==
COIN )
return TRUE;
return FALSE;
}

int
validposition4 (int i, int j)
{
if (within_l (i, j + 2) && (a[i][j + 1] == COIN) && a[i][j+2] ==
COIN )
return TRUE;
return FALSE;
}

int isonlythat(void)
{
int i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
if(a[i][j] == COIN && (i!=3 ||j!=3))
return FALSE;
if(a[3][3] == HOLE)
return FALSE;
return TRUE;
}

void
hiq (int p, int q, int count)
{
int flag = 0, i, j, tmp;
// printf("%d %d\n",p,q);
// print_array();

if (validposition1 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p - 1][q] = HOLE;
a[p - 2][q] = HOLE;
hiq (p - 2, q, count + 1);
hiq (p - 1, q, count + 1);
a[p][q] = HOLE;
a[p - 1][q] = COIN;
a[p - 2][q] = COIN;
}

if (validposition2 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p + 1][q] = HOLE;
a[p + 2][q] = HOLE;
hiq (p + 2, q, count + 1);
hiq (p + 1, q, count + 1);
a[p][q] = HOLE;
a[p + 1][q] = COIN;
a[p + 2][q] = COIN;
}

if (validposition3 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p][q - 1] = HOLE;
a[p][q - 2] = HOLE;
hiq (p, q - 2, count + 1);
hiq (p, q - 1, count + 1);
a[p][q] = HOLE;
a[p][q - 1] = COIN;
a[p][q - 2] = COIN;
}

if (validposition4 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p][q + 1] = HOLE;
a[p][q + 2] = HOLE;
hiq (p, q + 2, count + 1);
hiq (p, q + 1, count + 1);
a[p][q] = HOLE;
a[p][q + 1] = COIN;
a[p][q + 2] = COIN;
}
if (flag == 0)
{
tmp = 0;

for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
if (a[i][j] == HOLE)
{
if (validposition1 (i, j) || validposition2 (i, j)
|| validposition3 (i, j) || validposition4 (i, j))
{
tmp = 1;
hiq (i, j, count + 1);
}
}

if (tmp == 0 )
{
if(isonlythat())
print_array ();
else
return;
}
else
return;
}

}

int
main ()
{
initialize ();
print_array ();
hiq (3, 3, 0);
return 0;
}

----------------END--------------------

[Fred L. Kleinschmidt]

Niklaus wrote:

Hi,
Thank you for the help. I made a small typo . The actual code is
below. It only had an error .
Well the limits are being checked in within_l. I have made the
modifications.

Even i *feel*(i may be wrong) that because of a lot of backtracking
the stack size setup by OS for the program is small so we have
segfault ?

--------------BEGIN----------------
#include<stdio.h>
#define SIZE 7
int a[SIZE][SIZE];
#define NOTVALID -1
#define HOLE 8
#define COIN 9
#define TRUE 1
#define FALSE 0

void
print_array (void)
{
int i, j;
for (i = 0; i < SIZE; i++)
{
printf ("\n");
for (j = 0; j < SIZE; j++)
printf (" %2c",
(a[i][j] == NOTVALID ? ' ' : (a[i][j] == HOLE ? '0' : '1')));
}
printf ("\n#########################\n");
}

void
initialize (void)
{
int i, j;
for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
a[i][j] = NOTVALID;

for (i = 2; i < 5; i++)
for (j = 0; j < SIZE; j++)
a[i][j] = COIN;
for (i = 0; i < SIZE; i++)
for (j = 2; j < 5; j++)
a[i][j] = COIN;
a[3][3] = HOLE;
}

int
within_l (int m, int n)
{
if (m < 0 || m > (SIZE - 1) || n < 0 || n > (SIZE - 1))
return FALSE;

if (a[m][n] == NOTVALID)
return FALSE;

return TRUE;
}

/* if i,j is a hole */
int
validposition1 (int i, int j)
{
if (within_l (i - 2, j) && (a[i - 1][j] == COIN) && a[i-2][j] ==
COIN )
return TRUE;
return FALSE;
}

int
validposition2 (int i, int j)
{
if (within_l (i + 2, j) && (a[i + 1][j] == COIN) && a[i+2][j] ==
COIN )
return TRUE;
return FALSE;
}

int
validposition3 (int i, int j)
{
if (within_l (i, j - 2) && (a[i][j - 1] == COIN) && a[i][j-2] ==
COIN )
return TRUE;
return FALSE;
}

int
validposition4 (int i, int j)
{
if (within_l (i, j + 2) && (a[i][j + 1] == COIN) && a[i][j+2] ==
COIN )
return TRUE;
return FALSE;
}

int isonlythat(void)
{
int i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
if(a[i][j] == COIN && (i!=3 ||j!=3))
return FALSE;

if(a[3][3] == HOLE)
return FALSE;

return TRUE;
}

void
hiq (int p, int q, int count)
{
int flag = 0, i, j, tmp;
// printf("%d %d\n",p,q);
// print_array();

if (validposition1 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p - 1][q] = HOLE;
a[p - 2][q] = HOLE;
hiq (p - 2, q, count + 1);
hiq (p - 1, q, count + 1);
a[p][q] = HOLE;
a[p - 1][q] = COIN;
a[p - 2][q] = COIN;
}

if (validposition2 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p + 1][q] = HOLE;
a[p + 2][q] = HOLE;
hiq (p + 2, q, count + 1);
hiq (p + 1, q, count + 1);
a[p][q] = HOLE;
a[p + 1][q] = COIN;
a[p + 2][q] = COIN;
}

if (validposition3 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p][q - 1] = HOLE;
a[p][q - 2] = HOLE;
hiq (p, q - 2, count + 1);
hiq (p, q - 1, count + 1);
a[p][q] = HOLE;
a[p][q - 1] = COIN;
a[p][q - 2] = COIN;
}

if (validposition4 (p, q))
{
flag = 1;
a[p][q] = COIN;
a[p][q + 1] = HOLE;
a[p][q + 2] = HOLE;
hiq (p, q + 2, count + 1);
hiq (p, q + 1, count + 1);
a[p][q] = HOLE;
a[p][q + 1] = COIN;
a[p][q + 2] = COIN;
}

if (flag == 0)
{
tmp = 0;

for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
if (a[i][j] == HOLE)
{
if (validposition1 (i, j) || validposition2 (i, j)
|| validposition3 (i, j) || validposition4 (i, j))
{
tmp = 1;
hiq (i, j, count + 1);
}
}

if (tmp == 0 )
{
if(isonlythat())
print_array ();
else
return;
}
else
return;
}

}

int
main ()
{
initialize ();
print_array ();
hiq (3, 3, 0);
return 0;
}

----------------END--------------------

You don't say what this prograsm is supposed to be doing. But the
problem might be that function hiq() seems to have the possibility of
infinite recursion.

--
Fred L. Kleinschmidt
Boeing Associate Technical Fellow
Technical Architect, Common User Interface Services
M/S 2R-94 [phone]

[Old Wolf]

ni*****@gamebox.net (Niklaus) wrote:

Can someone point out what is wrong with this code ? How can i make
it better optimize it. When run it gives me seg fault in linux. But
windows it works fine(runs for a long time).

Do we have something like stack size growing enormously and then
saying you can't access ,so a segfault ?

Firstly, it looks to me as if there is no undefined behaviour anywhere
(despite what others have said). About the worst I could say is that
"validposition1" would check outside the array bounds if you call it
with, say (-1, 0), but you never do this.

However, at least one of the four validposition functions could
always be TRUE, and in the hiq() function you call hiq() again
if one of those functions was true. Most likely, you are running
out of stack. You could confirm this by adding code to display
the current value of "count" every time hiq() starts, and you
should find that it is always the same or similar value each time
the program crashes.

To fix this problem you should design your program to not recurse
so deeply (or even to not use recursion at all). If you used
malloc to allocate new memory, then a) you could detect when
you ran out of memory, and b) you would be less likely to run out
(typically, malloc can use up to all of the PC's memory, whereas
there might only be a fixed-size area that is allowed for stack space).

As a stopgap measure, you could malloc your local variables and the
next calls' function parameters all in one go, so that you have
hiq(int *); and no local variables, this would probably allow you
to go to 4* the depth that you were before (but could not be
considered good programming style!)