check 2 D array columns then rows for duplicates

[kylie991]

Hi I am stuck on checking if a 2D array has duplicates.

I have to write a function to check if a column has duplicates and then another function to check if the rows have duplicates from a file.

How would I go about this... I have the array reading a file correctly is it just the check for duplicates that I am stuck on... :)

[donbock]

What is your definition of a "duplicate" ?
> Two cells that have the same value?
> Identical rows?
> Identical columns?
... or something else?

[kylie991]

a row that contains more than the same character once...

eg.

123456789 has no duplicates
123456799 has a duplicate

I am stuck on how to check a 2D array for duplicates. But I need to write one function to check the columns for any duplicates and another function to check the rows. If I get help to do at least one of them then I will work on the other myself..

below is my program currently.

int loadFile(char data[9][9]) 
{ 
 ifstream infile; 
   string filename; 
   float list = 0; 
   cout << "Enter file name " << endl; 
   cin >> filename; 
   infile.open(filename.c_str()); 
   if (infile.fail()) 
   { 
      cout << "File not found " << endl; 
      return EXIT_FAILURE; 
   } 
   for(int i=0;i<9;i++) 
     for(int j=0;j<9;j++) 
       infile >> data[i][j]; 
   return EXIT_SUCCESS; 
} 
  
int displayFile(char data[9][9]) 
{ 
    for(int i=0;i<9;i++) 
     { 
     for(int j=0;j<9;j++) 
       cout << data[i][j] << " "; 
     cout << endl; 
     } 
}

[donbock]

A "duplicate" is ...

a row that contains more than the same character once...

eg.

123456789 has no duplicates
123456799 has a duplicate

I am stuck on how to check a 2D array for duplicates. But I need to write one function to check the columns for any duplicates and another function to check the rows.

So you want to be able to check each row and each column for duplicate entries.

Consider your example rows. Start with the first character ("1") and compare it to each character to its right. If no matches, then take the second character ("2") and compare it to each character to its right. And so on. That's a general solution.

However, the specifics of your problem might allow for a simplification. If the permissible values in the array are restricted to a small range (for example, 1 to 9) then you can check off each permissible value as you scan the row or column. You have a duplicate if any permissible value has more than one check mark.

[kylie991]

thanks for that.. I understand that is what I have to do but when I try to write the function I must be getting the coding wrong.. because it wont work.... I was thinking of creating a temp variable but that wont work either as I need to know if there is a duplicate in the whole row eg.

123426 // 2 is in that row twice but if I had a temp to check the array it wouldnt pick it up unless it was right after it...??

for now we can assume the column max is 9 and row max is 9 (in total 81 characters)...

I think what I am confused about is how to check it...

How woud I write the function for check cols... Am I kind of on the right track??? Do I need to implement a copy of the array???

int checkCols(char data[9][9]) //not complete
{
float checkCols = 0;
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{

if (data[i][j] == checkCols) // i know this is wrong but I know I need to compare this with something once I have the code above sorted.

}
cout << endl;
}
}

[donbock]

I suggest you take a look at Arrays Revealed.

For example, this function definition isn't right:

int checkCols(char data[9][9]) {...}

[kylie991]

what do you mean?? Do you mean I should have int checkCols(char data[8][8])??

I'm confused...

I am just finding this really hard because anytime I try to sort this array it goes back to the top of my program and says that float list; is not being used....

#include <iostream> 
#include <string> 
#include <fstream> 
  
using namespace std; 
  
void printMenu();
int loadFile(char data[9][9]);
int displayFile(char data[9][9]);
//int checkCols(char data[9][9]);
void bubbleSort(char data [9][9]);
void ShowArray(char data [9][9]);
  
int main() 
{ 
 
 char choice = '*';
     while (choice != 'Q')
      
     
     
     {
         char data[9][9];
         printMenu();
         cin >> choice; 
         switch (toupper(choice))
         {
                case 'L' :  loadFile(data); 
                           break;
                case 'D' : displayFile(data); 
                           break;
                case 'R' :  // complete this
                case 'C' :  bubbleSort(data);
                            ShowArray(data);
                           break;
                case 'M' :  // complete this
                case 'Q' : break;
                default :  cout << "Invalid option " << endl; cin.ignore(100,'\n');
         }

     }     
         
    return 0;
 

 
 system("pause");
} 

void printMenu()
{
     cout << "\n\tSudoku Checker " << endl << endl;
     cout << "\t L\t Load file " << endl;
     cout << "\t D\t Display " << endl;
     cout << "\t C \t Check columns " << endl;
     cout << "\t R \t Check rows " << endl;
     cout << "\t M \t Check minigrids" << endl;
     cout << "\t Q\t Quit " << endl;
     cout << " Rows and columns are labelled from 0 to 8 " << endl;
     cout << endl;
}
int loadFile(char data[9][9]) 
{ 
 ifstream infile; 
   string filename; 
   float list = 0; 
   cout << "Enter file name " << endl; 
   cin >> filename; 
   infile.open(filename.c_str()); 
   if (infile.fail()) 
   { 
      cout << "File not found " << endl; 
      return EXIT_FAILURE; 
   } 
   for(int i=0;i<9;i++) 
     for(int j=0;j<9;j++) 
       infile >> data[i][j]; 
   return EXIT_SUCCESS; 
} 
  
int displayFile(char data[9][9]) 
{ 
    for(int i=0;i<9;i++) 
     { 
     for(int j=0;j<9;j++) 
       cout << data[i][j] << " "; 
     cout << endl; 
     } 
}

[kylie991]

can someone pls help?? I am stuck :(

[donbock]

what do you mean?? Do you mean I should have int checkCols(char data[8][8])??

Follow the link provided in message #4.

[kylie991]

I did read it but it hasnt helped. I do understand the concept of arrays it is the finding duplicate files that is confusing me... the task is...
* each column is checked for duplicate values. If a column contains a duplicate value then the message "column "c " is incorrect " is displayed. If all columns are correct then the message "All columns are correct " is displayed.

[whodgson]

They are recommending that you read the array reference again while thinking about what you read in the context of your problem.
You clearly need to compare each element in the row or column with something
such as the first element in the row or column. If no match is recorded compare each element in the row or coumn with the second element...and so on.
If a match is found some method of breaking out of the loop and identifying where the match was found ( i.e. which row or coumn) is needed

[JosAH]

can someone pls help?? I am stuck :(

For Sudoku you can do better: keep 9 boolean variables, 9 per row, 9 per column and 9 per subsquare. These 9 booleans are stored in some form of an array as well. If you put, say, a four in the sixth row somewhere, set the fourth boolean variable of that row to 1 if it was zero. If it was set to 1 before you can't set a four in that row anymore because there already was a four in that row.

I wrote a simple Sudoku solver once (see the Java articles for a little article about it) and it is one of the fastest solvers I've seen.

Those nine boolean variables can be simple bit flags, i.e. one short int per row, column and sub square are all you need. The rest is just some bit fiddling.

kind regards,

Jos

[donbock]

I did read it but it hasnt helped.

The essay at the other end of the link should help you with passing a 2D array to a function.

[kylie991]

I must be stupid.. I cant work it out.. I do realise I need to create another array to compare but I dont know how to do it.....

[donbock]

thanks for that.. I understand that is what I have to do but when I try to write the function I must be getting the coding wrong.. because it won't work.... I was thinking of creating a temp variable but that won't work either as I need to know if there is a duplicate in the whole row eg.
<snip>
How would I write the function for check cols... Am I kind of on the right track??? Do I need to implement a copy of the array???

int checkCols(char data[9][9]) //not complete
{ 
    float checkCols = 0;
    for(int i=0;i<9;i++) 
    { 
        for(int j=0;j<9;j++) 
        {
            if (data[i][j] == checkCols) // i know this is wrong but I know I need to compare this with something once I have the code above sorted.
        }
        cout << endl; 
    } 
}

Let's assume that the format of the 2D data array is data[row][column].
I used your convention for passing the 2D array to checkCols -- I'm not convinced that is the right way to do it.

#define NROWS 9        // Number of rows.
#define NCOLS 9        // Number of columns.

// Return 0 if duplicate found in any column; otherwise return nonzero.
int checkCols(char data[NROWS][NCOLS])
{
    // Check each column in turn ...
    for (int column=0; column<NCOLS; column++)
    {
        // Start from the top of the column and move downwards to the second-to-last cell ...
        for (int row=0; row<(NROWS-1); row++)
        {
            // Temp variable may improve performance by hoisting row*column.
            const char thisCell = data[row][column];
            // Compare this cell to every cell below it in the same column.
            for (int checkRow=row+1; checkRow<NROWS; checkRow++)
            {
                if (thisCell == data[checkRow][column])
                {
                    // Found a duplicate; return an error.
                    return 0;
                }
            }
        }
    }
    // Got through all the columns without a match; return success.
    return 1;
}

It shouldn't be too hard to transform this into a function for checking rows.

This is not the most efficient algorithm: it performs 35 comparisons per column if there are no duplicates. The algorithm suggested in reply #12 can do the job in 9 comparisons per column.

Notice how I replaced naked 9's with NROWS and NCOLS. This is much preferred -- it protects you from a typo where you hit '8' instead of '9'; but just as important, it documents which dimension is rows and which is columns.