LinuxQuestions.org
Visit Jeremy's Blog.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 11-05-2012, 04:13 PM   #1
carlosk711
Member
 
Registered: Sep 2012
Posts: 52

Rep: Reputation: Disabled
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

Last edited by carlosk711; 11-05-2012 at 04:14 PM.
 
Old 11-05-2012, 04:43 PM   #2
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,139

Rep: Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127
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.
 
Old 11-05-2012, 04:59 PM   #3
carlosk711
Member
 
Registered: Sep 2012
Posts: 52

Original Poster
Rep: Reputation: Disabled
it was a long gone previous assignment, just practicing
 
Old 11-05-2012, 05:34 PM   #4
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,139

Rep: Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127
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.

Last edited by johnsfine; 11-05-2012 at 05:55 PM.
 
2 members found this post helpful.
Old 11-06-2012, 08:01 PM   #5
carlosk711
Member
 
Registered: Sep 2012
Posts: 52

Original Poster
Rep: Reputation: Disabled
Thank you, it did not compile the first time, what were you writing in? I used c++
 
Old 11-07-2012, 07:35 AM   #6
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,139

Rep: Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127
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.
 
  


Reply

Tags
array, c++, linux


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[SOLVED] Implementing a chat program and thus involving majority of networking concepts. TheIndependentAquarius Programming 9 11-23-2011 06:18 AM
The majority of Linux users also use Windows BrokeBody Linux - General 4 06-09-2008 07:20 AM
Sorry, I'm in the majority... AlaskanWolf General 20 12-06-2007 09:37 AM
Where are the majority...... trickykid General 45 01-10-2002 04:33 PM


All times are GMT -5. The time now is 09:14 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration