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
11 1818 Banfa 9,065
Expert Mod 8TB
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.
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 9,065
Expert Mod 8TB
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.
thanks for your attention.
You realıy help me about which way i should focus on
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).
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
. There may be a faster non-recursive way to generate the answers.
Banfa 9,065
Expert Mod 8TB
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.
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;
-
}
-
}
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
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;
-
}
Thank you all for every valuable interpretations...
Sign in to post your reply or Sign up for a free account.
Similar topics
by: Koen |
last post by:
Hi all,
I created a little database to manage my e-books.
The program will synchronize a table with the contents of a directory.
Works great.
Because I keep additional info (like keywords) to...
|
by: Tola |
last post by:
In my case of study, my teacher gave me a project, after I analysed
the problem I found that I had to used open the file on the other
machine? Please help?
Thank you in advance.
Tola CHROUK
|
by: Dave Davidson |
last post by:
I just modified my web.config to impersonate a local
Windows account and am getting the error below when
navigating to a page. We have a Development network where
my impersonation works great -...
|
by: Sven-Torben Janus |
last post by:
I'm running an ASP.NET webapplication on a Windows 2000 Server SP4 machine
with .Net Framework 1.0 installed.
The ASP.Net application uses impersonation (windows domain account). This is
needed...
|
by: Jay C. |
last post by:
Jay
3 Jan. 11:38 Optionen anzeigen
Newsgroups: microsoft.public.dotnet.framework.webservices.enhancements
Von: "Jay" <p.brunm...@nusurf.at> - Nachrichten dieses Autors suchen
Datum: 3 Jan...
|
by: Extremest |
last post by:
I know there are ways to make this a lot faster. Any
newsreader does this in seconds. I don't know how they do
it and I am very new to c#. If anyone knows a faster way
please let me know. All...
|
by: nabh4u |
last post by:
hi, i need some help with progamming..i have a program which has to implement gale shapley's algorithm. i have 2 preference lists one is for companies and the other is for persons. i have to match...
|
by: StephQ |
last post by:
I need to implement an algorithm that takes as input a container and
write some output in another container.
The containers involved are usually vectors, but I would like not to
rule out the...
|
by: pedagani |
last post by:
Dear comp.lang.c++,
Could you make this snippet more efficient? As you see I have too many
variables introduced in the code.
//Read set of integers from a file on line by line basis in a STL...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
| |