could you help about algorithm

[sircool]

firstly hi,
i am new in this site
i have a problem to develop a algorithm about that


problem is that we should write a problem that can calculate the counts of ways 1 to 9 but we can't use diagonal way for instance we can't go 5 from 1. we can go 2 or 5 from 1

if you help me to develop a algorthm with c++ i would be happy

thanks

[Banfa]

problem is that we should write a problem that can calculate the counts of ways 1 to 9 but we can't use diagonal way for instance we can't go 5 from 1. we can go 2 or 5 from 1

A ssume you mean "we can go 2 or 4 form 1"?

You have not stated the problem well enough, for instance you have not stated that you can not go back to a square once you have visitied it.

Since you have not stated that then I can go back to a square once I have visited it a can visit a a square more than once and therefore there are an infinite number of solutions e.g.

1 4 5 2 3 6 9
1 4 5 2 1 4 5 2 3 6 9
1 4 5 2 1 4 5 2 1 4 5 2 3 6 9
1 4 5 2 1 4 5 2 1 4 5 2 1 4 5 2 3 6 9

and so on

Until you state all the conditions it would be impossible to create a algorithm to solve the problem.

[sircool]

yeah you are true i wrote wrong i am sorry for that
actually i wanted to say we can go 2 or 4 from 1.But we can't go to 5 from 1 because it is diagonal way. The problem is that how many ways are there that go to 9.Starting point is 1. Sure we can't go same point on a way
for instance the following one is false
1236523 ( because we visit the 3 point twice so this one is false)

if you help me again i would be happy.
Note: i post this message and at the same time i try to solve but i can't yet

[Banfa]

I think I would go with a recursive function, pass to the function 2 arrays, 1 indicating which squares we have already been to and 1 indicating the order we went to them.

Any given square knows what it's exit options are so go to any exit option in turn that has not already been visited making sure to mark the current level as visited and add it to the visited order array.

When ever you hit 9 then increment the count of solutions and if required print the route from the order visited array.

[sircool]

thanks for your attention.
You realıy help me about which way i should focus on

[D_C]

First, does 1 have to start in the upper left corner? If not, you may have to call this function nine times, each time with one in a different corner.

You need a 9 entry boolean array to keep track of which entries are occupied. Also, you need to pass which number was just placed. Then, for each number, recursively go up, down, left and right. However, if you will exit a boundary or it's occupied, don't visit it.

If you need to output the solution, you will need a second array to pass with the location of the entries. Of course, you could combine the boolean array with the integer array.

Let 0 mean an entry is unoccupied. Otherwise, 1 - 9 means that 1 occupies the square... - 9 occupies the square. After you recursively visit a square, remember to unoccupy the square (whether you have two arrays or one).

[D_C]

I just implemented my own version of the program, 63 lines of code. Also, you need a third parameter. The first parameter can be the array with values (0 for empty else the number which occupies it), the last number placed, and the index where the last number was placed.

I count forty solutions. Interestingly, the number of solutions from each starting point is

8 0 8
0 8 0
8 0 8

. There may be a faster non-recursive way to generate the answers.

[Banfa]

Actually D_C he does state burried in his first post that you have to go from 1 to 9.

Also I don't see how you get any 0 solutions from any square. For instance starting at 2 you can go

2 3 6 9

No-where does it state that all squares must be visited.

However clearly the insight gained from solving this not quite the same problem is useful and applicable to the actual problem.

[sircool]

finally i managed to write that program thank to you.I will put that code here to help anyone who want to help about that problem.I wrote this problem for 3 *3 matris.It would be developed by using dynamic memory management

#include<stdio.h>
#include<conio.h>
void find(int,int);
long result=0;
int matris[3][3];
int x,y;
main()
{
int a,b;
x=3;y=3;
for(a=0;a<3;a++)
for(b=0;b<3;b++)
matris[a][b]=0;
matris[0][0]=1;
find(0,0);
printf("result is=%d",result);
return 0;
}
//---------------------------------------------------------------------------
void find(int i,int j)
{
if(i==2&&j==2)
{
result++;
return;
}
if(i+1<3&&matris[i+1][j]==0)
{
find(i+1,j);
matris[i+1][j]=0;
return;
}
if(j+1<3&&matris[i][j+1]==0)
{
find(i,j+1);
matris[i][j+1];
return;
}
if(i-1<3&&matris[i-1][j])
{
find(i-1,j);
matris[i-1][j]=0;
return;
}
if(j-1<3&&matris[i][j-1])
{
find(i,j-1);
matris[i][j-1]=0;
return;
}
}

[D_C]

Actually D_C he does state burried in his first post that you have to go from 1 to 9.

Also I don't see how you get any 0 solutions from any square. For instance starting at 2 you can go

2 3 6 9

No-where does it state that all squares must be visited.

However clearly the insight gained from solving this not quite the same problem is useful and applicable to the actual problem.

I think you misunderstood him. He said you have to go from the numbers from 1, 2, ..., 8, 9. I think he meant to say that one only move laterally (Up, left, down, or right). To clarify what he said, you can't move diagonally, like from square #1 to square #5, but you could go from square #2 to square #1 or #5 (or #3).

After further thought, there is definately some rotational, diagonal, and directional symmetry. Each pattern can be rotated four times, flipped over two diagonals, and reversed one way (N = 10-N for all entries). There is some overlap between the operations though. S, R and 9 are the unique types of patterns.

  S       R       9 
3 2 1   3 4 5   7 6 5
4 5 6   2 7 6   8 9 4
9 8 7   1 8 9   1 2 3

It might make an interesting group.

Rotational(R)
3 4 5    1 2 3
2 7 6 -> 8 7 4
1 8 9    9 6 5

Diagonal(R)
3 4 5    9 6 5
2 7 6 -> 8 7 4
1 8 9    1 2 3

Reverse(R)
3 4 5    7 6 5
2 7 6 -> 8 3 4
1 8 9    9 2 1

[D_C]

I completely blanked on answering his question. I did mine in C++. I'm not sure your stopping case is correct. I also use a 1D array. The recursion is similar, especially if you use a 2D array. I'll let you work at the recursive step.

Also note that I past last_number and last index. That way, I know where I am in the matrix, and can test whether I may go up, down, left, or right.
A hint: In the main loop I am guessing where the first element goes. Each recursive case is similar.

static int count = 0;

static void solve(int square[], int last_number, int last_index)
{
    // Stopping case
    if(last_number == 9)
    { // print solution
        count++;
        for(int i = 0; i < 9;)
        {
            cout << square[i++] << " ";
            if((i % 3) == 0)
                cout << endl;
        }
        cout << endl;
        return;
    }
    // Case to move up recursively 
    // Case to move down recursively 
    // Case to move left recursively 
    // Case to move right recursively 
    return;
}

int main()
{
    int square[] = {0,0,0,0,0,0,0,0,0};
    int i;
    for(i = 0; i < 9; i++)
    {
        square[i] = 1; // make a guess
        solve(square,1,i); // see how it works
        square[i] = 0; // undo the guess
    }
    cout << "Number of solutions: " << count << endl;
    system("PAUSE");
    return EXIT_SUCCESS;    
}

[sircool]

Thank you all for every valuable interpretations ...