LinuxQuestions.org

LinuxQuestions.org (/questions/)
-   Programming (http://www.linuxquestions.org/questions/programming-9/)
-   -   I have a majority of this program done, using C++ (http://www.linuxquestions.org/questions/programming-9/i-have-a-majority-of-this-program-done-using-c-4175435778/)

carlosk711 11-05-2012 03:13 PM

I have a majority of this program done, using C++
 
So I can't seem to figure out the logic here.
I'm trying to create a program that reads out integers 1-4 in a 2D array. Each row and column cannot repeat an integer. So I currently have it so the rows are unique. Can someone help me make the columns follow the same format?

Here is the code:
Code:

#include <cstdlib>
#include <time.h>
using namespace std;
int main ()
{
    int A[4][4];
    srand (time(NULL) );
    int j = 0;
    while (j < 4)
    {
    int count = 0;
    while (count <4)
        {
        int k = (rand() % 4) + 1;
        bool Placed = false;
        for (int i = 0; (i < count); i++)
            {
            if (A[j][i] == k)
                {
                Placed = true;
                }
            }
        if (!Placed)
            {
            A[j][count] = k;
            count ++;
            }
        }
    for (int i=0; i<4; i++)
        {
        cout << A[j][i] << " ";
        }
    cout << endl;
    j++;
}
    return 0;
}

This makes the rows read out 1-4 without repeating but not the columns. Can someone fix this? Thanks?
CURRENT OUTPUT(wrong):
2 4 3 1
2 3 1 4
1 4 2 3
1 3 2 4

SAMPLE OUTPUT(right):

4312
3124
1243
2431

johnsfine 11-05-2012 03:43 PM

First, consider the following change to your program, which sometimes works and sometimes hangs:
Code:

#include <cstdlib>
#include <iostream>
#include <time.h>
using namespace std;
int main ()
{
    int A[4][4];
    srand (time(NULL) );
    int j = 0;
    while (j < 4)
    {
    int count = 0;
    while (count <4)
        {
        int k = (rand() % 4) + 1;
        bool Placed = false;
        for (int i = 0; (i < count); i++)
            {
            if (A[j][i] == k)
                {
                Placed = true;
                }
            }
        for (int i = 0; (i < j); i++)
            {
            if (A[i][count] == k)
                {
                Placed = true;
                }
            }

        if (!Placed)
            {
            A[j][count] = k;
            count ++;
            }
        }
    for (int i=0; i<4; i++)
        {
        cout << A[j][i] << " ";
        }
    cout << endl;
    j++;
}
    return 0;
}

I added the code in red to do the extra that you asked for: Check that the chosen value is unique in its column (as well as unique in its row) before placing it.

On some runs it works. But on some runs it infinite loops. It might have chosen the first three values of the second line such that the fourth value of the second line is impossible, or it might have chosen the first two values of the third line such that the third value of the third line is impossible.

If you understand why that hangs, then you should get some idea why your original program needs something better than a simple addition to reliably get the answer.

Hopefully that gives you some idea how to proceed. This sounds like homework, so I don't want to give you a complete answer.

carlosk711 11-05-2012 03:59 PM

it was a long gone previous assignment, just practicing

johnsfine 11-05-2012 04:34 PM

OK, I'll trust your claim that it is not current homework, and show you the generic recursive brute force approach to a wide range of similar problems.

This approach is a randomized guess and check. It is used when the programmer understands only the basic constraints of the problem and not the implications of those constraints. In larger problems the run time might be hopelessly long, because it is doing a depth first search of the possibilities. But for a lot of problems, the fact that a CPU is incredibly fast means a "brute force" (stupid) search is fine.

Code:

#include <cstdlib>
#include <iostream>
#include <time.h>
using namespace std;
bool ok( int A[4][4], int r, int c, int k )
{
    for (int i = 0; (i < c); i++)
        if ( A[r][i] == k )
            return false;
    for (int i = 0; (i < r); i++)
        if ( A[i][c] == k )
            return false;
    return true;
}
bool fill( int A[4][4], int r, int c )
{
    int x = rand() % 4;
    for ( int i=x; i<x+4; ++i )
    {
        int k = (i%4)+1;
        if ( ok( A, r, c, k ) )
        {
            A[r][c] = k;
            if ( c<3 )
            {
                if ( fill( A, r, c+1 ) )
                    return true;
            }
            else if ( r<3 )
            {
                if ( fill( A, r+1, 0 ) )
                    return true;
            }
            else
                return true;
        }
    }
    return false;
}
int main ()
{
    int A[4][4];
    srand (time(NULL) );
    fill(A,0,0);
    for (int r=0; r<4; ++r)
    {
        for (int c=0; c<4; ++c)
        {
            cout << A[r][c] << " ";
        }
        cout << endl;
    }
    return 0;
}

The ok(A, r, C, k) function checks the constraint: Whether it is OK based on previous choices to place value k at position A[r][c]. It checks both the portion of row r to the left of c and the portion of column c above r.

The fill(A, r, c) function is the heart of the program. It assumes that all rows above r have already been filled and all columns of row r to the left of c have already been filled. Then it tries to fill the rest of the matrix recursively. If it succeeds it returns true. If it fails it returns false. A return of false implies some earlier guess made the solution impossible.

fill() selects a random starting guess, then tries each of the four possibilities from that starting guess (if it tries 3 first, it will try 4, 1, and 2 in that sequence next). For each guess, if it can place that value, it does so and then recursively tests to see if the whole rest of the solution is possible after placing that value. If so, it can return true. If not, it continues to the next guess. If all four guesses fail, it returns false indicating some outer layer in the recursion must change its guess.

main() should be obvious.

It should also be obvious how to use the recursive guess and check structure for a wide range of different problems.

If you have a much better understanding of the subtleties of the specific problem, you can find a much less "brute force" program, possibly something less far removed from your original. Sometimes as a programmer, you just need to be good at programming and solve the problem as I did here, without trying for any insight into the problem. Other times, you need to also be a topic expert. In this case that would mean understanding why certain guesses paint you into a corner such that no answer is valid for the rest. Then find a way to get a solution reliably without back tracking. In this particular problem, I don't think much of a lesson would be learned by understanding the problem better. "Brute force" is a better lesson to learn this time.

In this problem, the entire search space is four to the sixteenth power, which means it would take only a few seconds to search the entire space. But there are many solutions and it stops when it finds one, which cuts the search time to a fraction, and at each level of the recursion most of the bad choices can be detected without going deeper, which combinatorialy cuts out almost all of the search space. So the actual "brute force" search turns out to be pretty trivial.

carlosk711 11-06-2012 07:01 PM

Thank you, it did not compile the first time, what were you writing in? I used c++

johnsfine 11-07-2012 06:35 AM

What was the error when you tried compiling it?
I used g++ version 3.4.6 on a 64 bit Centos system. Later version of Gnu C++ might be pickier about something I was careless of.

But your posted code didn't compile for me (because stdlib doesn't define cout, which is the reason I added iostream) so I expect you are using some other obsolete non standard C++ compiler.


All times are GMT -5. The time now is 07:29 PM.