checking array for duplicates

[riotking]

Hi all,

I've been stuck on this for hours so am brining it here to see if i can get any suggestions..

I have an array that i need to check to see if there are any duplicate values present. I do not need to remove the duplicates, just see if any are present. If there are duplicates, the method should return false; if there are no duplicates, the method should return true. My method keeps returning true. My code is below.

(its not a sudoku solver, but just a solution validator)

 private static boolean isSolution(Sudoku puzzle)
  {
    int count=0;
    boolean solution = false;
   for (Cell[] myPuzzle : puzzle)
     {
     for (int i=0; i<myPuzzle.length; i++)
       {
       for (int j=i+1; j<myPuzzle.length; j++)
         {
         if (myPuzzle[i] == myPuzzle[j])
           count++;
         }
       }
     }
   if (count > 0)
     solution= false;
   else
     solution = true;
   return solution;
  }

any insight would be greatly appreciated.

[pbrockway2]

Use a debugger or insert println() statements to check what is going on: the length of the cell arrays, and the cell values being compared. Basically you want to check that the nested for loops are doig what you think they should.

Also remember that == is not the same thing as equals(). So check exactly what myPuzzle[i] and myPuzzle[j] are. It may be that they are different Cell instances but have been assigned the same numeric value. (In which case they should count as "duplicates" even though they are different.)

[riotking]

ok, i insterted println statements inside the nested loop. now i am thinking the problem may lie in my code for iteration b/c whats printing is :

"Cell@165e55e
Cell@139491b
Cell@165e55e
Cell@1f04ea6" and so on.... not the actual value.


so far, my next() method only has code to iterate through the rows and columns of the puzzle. I am planning on adding the boxes code once i am sure the rows and columns are working properly.

the implementation of iterator has definitely been a little confusing for me.

this is my code:

  public Cell[] next()
  {
    Cell[] result = new Cell[puzzle.length];
     // rows
    if (cursor<puzzle.length)
    {
      Cell[] rowValue = puzzle[cursor];
      cursor++;
      result = rowValue;
    }
    // columns
    else if(cursor<2*puzzle.length)
    {
      for (int i=0; i<puzzle.length; i++)
      {
        for (int j=0; j<puzzle[i].length; j++)
        {
          Cell[] columnValue = new Cell[j];
          cursor++;
          result=columnValue;
 
        }
      }
    }
    return result;
  }

[pbrockway2]

I haven't really looked at the next() - but I think you could do more to understand the isSolution() method you posted earlier.

What is the value of myPuzzle.length for each iteration of the outer for loop? Is this what you expect?

myPuzzle[i]==myPuzzle[j] is always evaluating to false. But what are the values of the two array expressions, myPuzzle[i] and myPuzzle[j], at this point? And what are the (numeric) values of the two cells that are being compared? Is the value of "false" what you expect given the values of the array expressions and the cell contents?

The cryptic "Cell@165e55e" arises because you have not overridden toString() method for the Cell class. (See the API docs).

[riotking]

after i posted that last msg, i realized the problem within my isSolution and fixed it (needed to call myPuzzle[i].getValue(), etc, to get numerical values of the cells). But i am having a difficult time understanding the Iterator and how to get it to loop through the columns. my code to iterate over the rows seems to be correct. i've tried reading more about iterators, but am still just not sure how to get it to iterate over only the columns.

[pbrockway2]

Is next() supposed to return an array of cells representing the (cursor-puzzle.length)-th column?

If so
- create result as an array of the right size
- in a single for loop go through the rows (ie puzzle[???]) and copy the appropriate cell into the right place in the result array
- return the result array

For example, suppose we wanted the 3rd column (when cursor puzzle.length+2). You would go through each row and copy the third element into the return array:

row 0  x x * x x x ...    result =[*]
row 1  x x & x x x ...    result = [* &]
row 2  x x ! x x x ...    result = [* & !]
row 3  x x % x x x ...    result = etc
 

[riotking]

thank you for helping me out here. i am not sure why this is giving me so much trouble.

next() is supposed to return 3 different one-dimensional arrays. one containing the rows, one containing the columns, and one containing the sub-boxes of the puzzle (which i have yet to try tackling). though, currently, it only seems to return an array for the rows.

i feel pretty lost here. I understand what you are saying, and i know which values i need to copy over into the columns array, i just am not exactly sure how to pull out the particular ones i need.

am i getting warmer at all?

 public Cell[] next()
  {
    Cell[] result = new Cell[3*puzzle.length];
     // rows
    if (cursor<puzzle.length)
    {
      Cell[] rowValue = puzzle[cursor];
      cursor++;
      result = rowValue;
    }
 
    // columns
    else if(cursor<2*puzzle.length)
    {
      for (int i=0; i<puzzle.length; i++)
      {
        Cell[] columnValue = puzzle[cursor];
        cursor+=puzzle.length+i;
        result=columnValue;
 
 
      }
    }
    //boxces code here
 
    return result;
  }

[pbrockway2]

What happens when you run your code?

> Cell[] columnValue = puzzle[cursor];

I would suppose that this line yields an ArrayIndexOutOfBounds exception. The puzzle array does not go as far as cursor once cursor exceeds puzzle.length.

Instead of the three lines you have in the for loop, try this:

(1) Get the relevant row not column.

    Cell[] row = puzzle[???];
 

Think about how the index should be expressed given that you want to work through each row in order.

(2) From each row extract one of the elements and place it in the appropriate place in the result array.

result[???a] = row[???b]
 

Once again you have to figure out the array indices. Look at the diagram I posted before. ???a starts at zero and works its way along the result array: it is related to the loop index i.

???b is the element of the row that needs to be added as you buld up the column array. It is constant (ie the same each time around the loop). It is related to the cursor value.

-----

All my comments are presume that I understand what you are trying to do with next(). Your comment that "next() is supposed to return 3 different one-dimensional arrays" doesn't really help because next() is declared to return a single array of cells. What I'm assuming is that next() is supposed to iterate over all 27 "groups". Called repeatedly it will return the nine rows (each as an array), then the 9 columns, then the nine boxes.

-----------------------

At this point you should be able to get the rows and columns part going. And run your isSolution() with some real data. If the runtime behaviour isn't what you expect then post your code and say what happens.