Enumerating self-avoiding walks

[chocho]

Hi! I need help with a problem concerning the number of self-avoding walks on sqquare lattice. Generally a self-avoiding walk is path that does not self-intersect, i.e. it does not pass through a point where it was before. It has a staring point. We intoduce a 7x7 array and set the starting point to be the center - the (3,3) cooridnate of the array. We can move in four different directions - up, down, left and right. I want to find the number of self-avoding walks with lenght 3. The program should cout 36=4*3*3, however it couts 16.

I think I know what the problem is but I am not sure: We know that a self-avoiding walks does not pass through a place where it has already been. I think the program makes the other self-avoding walks not to pass through a point where one self-avoding walk has already been. This reduces their number. I would be extremely grateful to anyone who could help me with this problem.

  #include<iostream>
#include<cmath>

using namespace std;




// creating the lattice
bool lattice[7][7]=

    {1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1
     } ;


int Num=0; // Variable counting the walks
int Lenght=0; // Variable keeping track of the length
int way (int x, int y)
{

//Reasons for saying a self-avoiding walk is invalid
    if(Lenght > 3 || x < 0 || y < 0 || x > 6|| y > 6 || lattice[x][y] != 1)
        return 0;
  // Preventing a walk going to the same place twice      
    lattice[x][y] = 0;



    Lenght++;
    if(Lenght == 3)
    {
        Num++;
        Lenght = 0;
    }
    //Going in the four possible directions
    return way(x+1, y) ||
        way(x, y+1) ||
           way(x-1, y) ||
           way(x, y-1);

}

int main()
{//Starting from the middle of the array
    way(3,3);
    cout<<Num<<endl;
    return 0;
}

[TheIdeasMan]

Duplicate:

http://www.cplusplus.com/forum/general/215595/

Please remove your other post, otherwise it could be reported, and your account could be disabled. It's a time waster for us.

I am not so keen on the recursive design of your code, that will be absolute hell when the numbers are larger. Does the base case on line 28 prevent other options being considered, or valid paths not to be counted?

If this is for project Euler or similar, brute force is not the way to go - there will be a clever way of doing it.

[chocho]

Ok. I deleted the other post. Sorry for the unconvenience it may have caused you. I got so,e help and managed to fix the recursion and as you said, it gets really slow for big numbers. It calculates easily to about 17. It is interesting that this is calculated to about 79.