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 ...
@kylie991
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]

@kylie991
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]

@kylie991
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]

@kylie991
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]

@kylie991
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.

[kylie991]

thanks so much I am still confused as ever... I have spent hours tryign to work it out. Whenever I make an error in the grammar the compiler gets stuck saying that float list (from function display file) is not being used....

The above doesnt seem to work for me as what I have to do is read the char array file.. we have a txt file we need to open....The task is to determine if the the file has duplicates in.
a) columns
b) rows
c) minigrids

and if there are duplicates in either one of the above we have to say for eg.
column 8 has duplicates

I can get the program to check the WHOLE array for duplicates. but I cannot get it to check each row or each column.. I am stuck on how to separate it...... as the data is stored in array char data [9][9]

And everytime I try to separate it I get that stupid error saying that float list is not being used or something..........

[donbock]

@kylie991
OK, let's focus on that. First of all, are you sure this is an Error message? It sounds a lot more like a Warning to me.

Please search your source code for the word "list". It only occurs once in the code you've posted here; but there may be other instances in your actual source code.

The only place I see "list" is in function loadFile; where the line

float list = 0;

occurs. The warning message appears to be correct -- a value is written into "list" but nobody ever seems to read that variable. What do you intend to be the purpose of "list"?

[kylie991]

Oh I can remove that one - i dont need it anymore... Hopefully that will help me with my troubleshooting.
Thanks for your patience everyone. Will let you know if I get anywhere with it :)

[whodgson]

I can get the program to check the WHOLE array for duplicates. but I cannot get it to check each row or each column.. I am stuck on how to separate it...... as the data is stored in array char data [9][9]

I am focusing on the OP`s above comment.
If you have a 2 dimensional array of 9 rows and 9 columns (int array[i][j] where i=9 and j=9 ) and you were to scan it, the 2 loops they would look like:
for(int i=0;i<9;i++)//for rows
for(int j=0;j<9;j++)//for columns
{
//the instructions would go here
}
i would keep track of the rows and j would keep track of the columns.
The table would look like this:
00 01 02 03 04 05 06 07 08 //where i is = 0 and j =0 to 8
10 11 12 13 14 15 16 17 18 //where i is = 1 and j = 0 to 8
20 21 22 23 24 25 26 27 28 // where i is = 2 and j = 0 to 8
....... and so on for the rest of the table down to:
80 81 82 83 84 85 86 87 88
To iterate through row#2 your loop would look like:
for(i=1,j=0;i<2,j<9;j++)//i does not change from 1 but j iterates from 0 to 8
To iterate through column 5 your loop would look like:
for(i=0,j=4;i<9,j<5;i++)//j does not change from 4 but i iterates from 0 to 8
Hope this helps.

[JosAH]

Are you all going to ignore my reply #12 and write crappy loops without thinking?

kind regards,

Jos

[kylie991]

Hi Jos
I had a read of your sudoku program and it looks great. I just wouldnt know how to implement the bool functions with my program. As I have to set it to read a file and then check the actual file for duplicates.......

Can you help cus yours looks like a great idea.. but since I am fairly new to c++ I wouldnt know how to make it work by opening a file..

[JosAH]

@kylie991
You have your board itself and an arrray of bit flags for the rows and the same for the columns and the same for the subsquares:

int board[9][9];
unsigned short rows[9];
unsigned short cols[9];
unsigned short squares[9];
 

If you want to store a value > 0, say 'val' at position i (row) and j (column) you have to do the following simple checks:

board[i][j] == 0
 

i.e. if there is a value at that position already the expression above will be false and you can't store a value there; otherwise:

int isSet(unsigned short flags[], int i, int val) {
   return flags[i]&(1<<val) != 0;
}
 

The above little function checks whether the 'val'th bit is set in flags[i], so you can test if a value 'val' is already used in row i as follows:

isSet(rows, i, val)
 

The above will be != 0 if value 'val' is already used in row i. The same goes for the columns and the subsquares. Setting a bit (that was zero) in an array is easy:

void set(unsigned short flags, int i, int val) {
   flags[i]|= 1<<val;
 

You can use the code in the Sudoku article as a cheat sheet and glue the above all together.

kind regards,

Jos

[donbock]

I don't understand this new-fangled C++ ">>" twaddle, but the fact that the OP declared the suduko board as a 2D char array makes me wonder if it contains characters '1' through '9' rather than integers 1 to 9. The equations cited above by JosAH presupposes integer values. It is a simple matter to convert characters to integers.

[JosAH]

@donbock
I don't see any "new-fangled C++ >> twaddle" but let's settle the definitions:

- the board is a char board[9][9] and contains the characters '0' ... '9'.

this definition changes the two little functions a bit:

int isSet(unsigned short flags[], int i, char val) { 
   return flags[i]&(1<<val-'0') != 0; 
} 
 
void set(unsigned short flags[], int i, char val) { 
   flags[i]|= 1<<val-'0'; 
}
 

kind regards,

Jos

[donbock]

@JosAH
The OP uses the following function to load the 2D suduko array:

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; 
} 

There is a lot of new-fangled C++ twaddle here that an unrepentent C curmudgeon like me only vaguely understands, but I was specifically referring to line 16. There is no blatant conversion here, so I suppose the array is loaded with characters from a text file. (Only the OP knows what the file format is.)

As you pointed out, converting from single-digit characters to integers is trivial.

If it were me, I'd do the conversion to integer in the loadFile function and modify the printFile function accordingly. That way the persistent data (in the 2D array) is in the most intuitive format [integer]. [On the other hand, what's intuitive to me might be obscure to everybody else.]

[JosAH]

@donbock
Ah, that piece of code ... I simply discarded it as non-interesting twaddle ;-)

@donbock
Yep, but the OP wants chars in that array so we'd better stick to that convention if we don't want to raise levels of confusion. The two core functions were indeed trivial to change.

kind regards,

Jos

[kylie991]

suppose the array is loaded with characters from a text file. (Only the OP knows what the file format is.)

yes it is coming from a text file :) It might confuse me if we try to change it to integers. Sorry I was away for a few days so have missed your help. Am goign to work on this tonight.. I appreciate EVERYONE's HELP :) Now Jos I think I might read your code to see if that will help. Because what I have is kind of working for now but is a lot longer than it probably can be... :)

Would anyone know how I can check the minigrids.. arghh its doing my head in..

[JosAH]

@kylie991
Read my (Java) code: the mini squares are indexed by the numbers 0 ... 9 as well, just like the rows and columns; a bit of index fiddling with the row and column numbers easily finds the index number of a mini square.

kind regards,

Jos

[donbock]

@kylie991
In general, you iterate through the three types of sets (rows, columns, minigrids). Within each type of set you iterate through nine sets (for rows, its the 9 rows; etc.). Within each set you iterate through nine cells.

Suppose you have a cell lookup function with inputs type-of-set, set-within-that-type, and cell-within-that-set; and that returned the row and column of the cell. Then one check-for-duplicates function could be used for all three types of sets.

How do you implement such a lookup function? Step 1: assign an index value to each type-of-set (0:2). Step 2: assign an index value to each set within each type-of-set (0:8). Step 3: assign an index value to each cell within each set (0:8). Step 4: Examine each of the 27 sets to see how row and column vary as you step through the cells of that set. Use the results of that examination to define your lookup algorithms (you need a different algorithm for each type-of-set). Step 5: only after you have a clear idea what has to happen do you start writing code.

Even if you don't write a single global lookup function, the steps described above will help you.

[kylie991]

thanks Donbock I understand that part. I have even written out the sudoku grid and worked out the rows and columns I need per mini grid.. its just the code that is getting me.. I have to do the same for the minigrid as I did for the others.... I have to work out how to get it to check the squares...

[JosAH]

@kylie991
As I wrote: use my code as a cheat sheet;

kind regards,

Jos

[kylie991]

:) I saw the squares calcultion.. its just a matter of checking for duplicates and getting the program to tell the computer which column/row has the duplicate..

I'm still stuck.. arghhh...... so tired.....

i am assuming you were referring to (3*(i/3)+j/3][val].. and thanks so much :) :)

[JosAH]

@kylie991
So if you have nine unsigned shorts (that store 9 bits each) for the rows, columns and the squares, you have this:

unsigned short rows[9];
unsigned short cols[9];
unsigned short squares[9];
 
int isSet(unsigned short flags[], int n, char val) {  
   return flags[n]&(1<<val-'0') != 0;  
}  
 
void set(unsigned short flags[], int n, char val) {  
   flags[n]|= 1<<val-'0';  
} 
 
void reset(unsigned short flags[], int n, char val) {
   flags[n]&= ~(1<<val-'0');
}
 

If you want to check a row i for a value val, do this: isSet(rows, i, val);
For a column j you do this: isSet(columns, j, val); and for a square at location (i,j) you do this: isSet(squares, (3*(i/3)+j/3, val).

The same values are used for the other small functions.

kind regards,

Jos

[donbock]

@kylie991
You're making me guess: are you having trouble writing code that computes the row and column values for each successive cell of a minigrid?

Let's get oriented. Suppose columns count 0:8 as you move from left to right; and rows count 0:8 as you move down. Let's plan on moving through the minigrid by rows: left to right, "carraige return", etc. Finally, we will label the top-right cell as the reference cell of the minigrid -- the coordinates of the reference cell are (R,C).

Here is a list of the cells in any and all minigrids:

Index    Row    Column    Index/3    Index%3
  0      R+0      C+0        0          0
  1      R+0      C+1        0          1
  2      R+0      C+2        0          2
  3      R+1      C+0        1          0
  4      R+1      C+1        1          1
  5      R+1      C+2        1          2
  6      R+2      C+0        2          0
  7      R+2      C+1        2          1
  8      R+2      C+2        2          2

That is, the coordinates for every cell in a minigrid are (R + Index/3), (C + Index%3), where R and C are different for each minigrid.

Notice that this could just as easily have been (R + Index%3), (C + Index/3) if we traversed the minigrid by columns.

JosAH has given you clues for how to compute R and C from the minigrid number.

[kylie991]

I can see what you are trying to say.. and I can mostly read your code however I think it is a bit beyond what we have learnt... I am trying to make it work even if it is a bit slow.... remember I am reading from a char data file [9] [9].

this is how long and messy I am right now with my minigrid checker.. and it isnt even doing it right... I know I have got it wrong in parts but I am at least trying to check the first minigrid and I cant even get that...

the equation is doing my head in...

int checkMini(char data[NROWS][NCOLS])
{
for (int column=0; column<NCOLS; column++)
{
for (int row=0; row<NROWS; row++)
{
const char thisCell = data[row][column];

for (int checkRow=row+1; checkRow<(NROWS/3); checkRow++)
{
for (int checkCol=column+1; checkCol<(NCOLS/3); checkCol++)
{
//compare this cell to the grid
cout << "this is row data " << row << " and this is column " << column << endl;
cout << "this is the duplicate value " << data[row][column] << endl;
row ++;
column++;
if (thisCell == data[checkRow][checkCol] )
//if (squares[3*(i/3)+j/3][val])
{
//if (squares[3*(row/3)]+[column/3]) //'val' is already present in this square
cout << "Minigrid starting at row " << row << " column " << column << " is incorrect " << endl;
return 1;
}
}
}
}
}
cout << "All minigrids are correct " << endl;
}

[donbock]

Stop writing code! Describe in words how to check the minigrids. You have to understand the algorithm you wish to use before you write the first line of source code.

[kylie991]

ok.. I am getting myself confused....

I understand I need to check the following..
for minigrid 1
00 01 02 10 11 12 20 21 22
minigrid 2
03 04 05 13 14 15 23 24 25 and so on....

So I know that I need to come up with an array or something that can check each minigrid....

[kylie991]

i worked out the grids !! yaaaaaaay thanks everyone for ur help !!

[JosAH]

@kylie991
How did you solve it? Did you use any of the existing code either in the examples here or in the existing Java code?

kind regards,

Jos

[kylie991]

ah no it is a very very long code. But what you guys mentioned did help my understanding. I just have to be careful that I dont start using codes that I have not learnt yet. We only started learning vectors last night!! They supposedly are going to replace arrays for the rest of our course this semester.. And we only really started on classes too.

It definately needs a lot of work but it was the only way that made any sense to me... I still need to add in some more functions to check if there are any errors in the txt file.. such as missing characters to be replaced with '1' or when the letter "A" is in a file and again need to replace it with a '1'.. but I havent even looked at that just yet... ...

[Ralfclark2009]

Hi Kylie,

Can you paste the minigrid and the extra functions you used as well?

I am really stuck in this part. The rest of my code sort of matches your code, but my program is not working at all... your help will be really appreciated.