# SudokuSet

• 07-25-2010, 09:43 PM
Lil_Aziz1
SudokuSet
I'm thinking about completely changing my sudoku solver. The program logically solves the sudoku puzzle; consequently, the method contains(), remove(), and get() methods are used innumerable times (mostly contains()). After reading up on Sets, I decided I wanted the sudoku grid to be a HashSet<Integer>[][] instead of an ArrayList<Integer>[][] because of the efficiency of contains() and remove(); however, there is a problem with using HashSets: there is no get(int index) method. I frequently need to get the only element in the ArrayList or iterate over all the elements.

I decided to make a class called SudokuSet that extends HashSet that will be implemented instead of just HashSet. I made two different implementations and I was wondering if anyone could tell me which one is the most efficient. If neither of em are efficient, can you tell me a better concept? Here are the two implementations:

Code:

```package sudokuUpdateToSets; import java.util.HashSet; /**  * @param <E> Generic because a 3D list of SudokuSet will be needed.  *                E.g: SudokuSet<SudokuSet<SudokuSet<Integer>>>  */ public class SudokuSet<E> extends HashSet<E> {                 private E[] list;         private int size;                 public SudokuSet() {                 super(10,1);                 list = (E[]) new Object[9];                 size = 0;         }         @Override         public boolean remove(Object o) {                 if (contains(o)) {                         updateList();                         size--;                 }                 return super.remove(o);         }         @Override         public boolean add(E o)  {                 list[size++] = o;                 return super.add(o);         }                 public E get(int index) {                 return list[index];         }                 private void updateList() {                 list = (E[]) this.toArray();         } }```
Code:

```package sudokuUpdateToSets; import java.util.ArrayList; import java.util.HashSet; public class SudokuSet1<E> extends HashSet<E> {                 private ArrayList<E> hiddenList;                 public SudokuSet1() {                 super(10,1);                 hiddenList = new ArrayList<E>();         }         @Override         public boolean add(E o)  {                 hiddenList.add(o);                 return super.add(o);         }         @Override         public boolean remove(Object o) {                 hiddenList.remove(o);                 return super.remove(o);         }                 public E get(int index) {                 return hiddenList.get(index);         } }```
• 07-25-2010, 10:08 PM
Norm
Quote:

I decided I wanted the sudoku grid to be a HashSet<Integer>[][] instead of an ArrayList<Integer>[][]
Can you explain this decision?
If you need a get(index) method, then HashSet won't work.
• 07-25-2010, 10:12 PM
Lil_Aziz1
Because I would like the method contains() to be O(1). Remove and get as well if possible.

Oh sorry. I meant I want to implement SudokuSet<Integer>[][].
• 07-25-2010, 10:20 PM
Norm
Quote:

I would like the method contains() to be O(1). Remove and get as well if possible.
Sorry, O(1) has no meaning for me.
And what does "Remove and get as well" mean?

I was looking for something like this:
I chose HashSet over ArrayList because HashSet allows me to .... and ArrayList does not.
Or HashSet is more efficient when I ... and ArrayList is too slow.
• 07-25-2010, 10:29 PM
Fubarable
• 07-25-2010, 10:38 PM
Lil_Aziz1
Um okay I'm sorry if I'm not explicit enough for you.

HashSet is more efficient when it comes to the method contains() and remove().

I don't know about LinkedHashSets. Only reason I would use LinkedHashSet is when I want the order of a list to be retained, but HashSet already does that for me when it comes to Integer.
• 07-25-2010, 10:41 PM
Norm
HashMap has a get() method. Have the key be the index's value.
• 07-25-2010, 10:47 PM
Lil_Aziz1
Wouldn't I have to relocate all values if I remove an element from the Map? Let's say I have the following HashMap:

{0=2, 1=4, 2=7, 3=9}

and I do something like
Code:

`map.remove(0)`
The list now looks like:
{1=4, 2=7, 3=9}

Pretty perceptive idea. Didn't think about using a Map and having the keys as indexes. It uses less space and I would only have to override the remove() method.

EDIT: I edited my first implementation of SudokuSet, but I'm getting a yellow line under
Code:

```list = (E[]) this.toArray(); //and list = (E[]) new Object[9];```
How can I fix that? I probably won't use this implementation, but I would still like to know how to fix this.
• 07-25-2010, 11:03 PM
Norm
What did you change in the edit?
What is the type of the list variable? What is the compiler error when you compile it?
• 07-25-2010, 11:18 PM
Lil_Aziz1
I made it so the method this.toArray(); is called less frequently. The type of the list variable can be either Integer or itself, SudokuSet.

Yellow line means it's not recommended. It is not a compilation error. Here is what appears when I hover over the text in yellow lines:

Type safety: Unchecked cast from Object[] to E[]

Also, my initial question is still unanswered. :( Which SudokuSet should I implement? Or should I make a third implementation that extends HashMap and overrides the remove() method.
• 07-25-2010, 11:26 PM
Norm
The decision is based on what are the program requirements.
Where do you need the efficiency or functionality?
How often is get() used with it requiring a toArray() call. Perhaps you could have a changed flag and if the contents hasn't changed reuse the generated array.
• 07-25-2010, 11:32 PM
Lil_Aziz1
The most prevalent method is contains(). Next is get() and lastly remove(). You could say remove() is infinitesimal compared to the number of times contains() is used.

Changed flag? I think I did that in my first implementation.
• 07-26-2010, 12:18 AM
Norm