Union Intersection difference

[SudokuMonster]

@dobrichev Anything in Cell or Grid that would achieve an intersection of VisibleCells or VisibleCellIndexes which then still retains the same properties as VisibleCells or VisibleCellIndexes?

[dobrichev]

CellsSet intersection = new CellsSet(Grid::visibleCellsSet[cellIndex1]); //copy constructor
intersection.retainAll(Grid::visibleCellsSet[cellIndex2]); //exclude non-common cells
//intersection.retainAll(Grid::visibleCellsSet[cellIndex3]); //exclude more non-common cells
for(int visibleFromAllCellsCellIndex : intersection) {
  //use visibleFromAllCellsCellIndex
}

It is a bit dirty but corresponds to the used data model and java conventions.
Don't rely on the return value of retainAll(), it is constantly false disregarding the specifications.

[SudokuMonster]

Thanks,
I attempted before your reply the following which works:

// Potential WZ cell found
Cell wzCell = Grid.getCell(wzCellIndex);
CellSet inter1 = new CellSet(wxyzCell.getVisibleCells());
inter1.retainAll(wzCell.getVisibleCells());
for (Cell xzCell : inter1) {
	int xzCellIndex = xzCell.getIndex();
	if (!(xzCell.getX() == wzCell.getX() && xzCell.getY() == wzCell.getY())) {
		BitSet xzValues = grid.getCellPotentialValues(xzCellIndex);
		inter.or(xzValues);
		.
		.
		.

[dobrichev]

The Cell object fields are reduced to a single integer from 0 to 80 inclusive which represents the cell position within the grid. You can simply compare the cellIndex or the whole cell object.

[SudokuMonster]

I made a heavy-handed attempt at re-writing WXYZwing.java which should be now in the newTechniques branch and is much better than the one by sunny shine. It can work as a template for VWXYZ wing too which I'm happy to proceed with. Bigger wings are possible but would degrade speed significantly as each one would have more & more inner loops. They would be best reported through an ALS-xz technique which is either on the to-do list or possibly in sunny-shine's next update

[dobrichev]

@SudokuMonster Congratulations for the good work!

[SudokuMonster]

I'. going now to see if I can increase the efficiency of the wing algorithm preventing the same set of cells appearing again in batch mode. I already have a few solution(s) but it would be quicker if there is a way to get Cell.getVisibleCellIndexes() with the result showing only VisibleCellIndexes > CellIndex.

I will attempt a few things!!!!

[SudokuMonster]

I've improved efficiency by 5% through reducing duplication of same technique cells in both wxyz and vwxyz. I Added forwardVisibleCellIndex and forwardVisibleCellsSet to Grid.java

[dobrichev]

The purpose of CellSet is to provide a more efficient way for storing and accessing unordered sets of cells, keeping the java-style coding. This has its negatives - inefficient code, limitations, etc.
One way to improve this is to allow direct access to the underlying BitSet and perform direct loops on it, or provide getter to it. The classical loop over bits looks like

for (int value = values.nextSetBit(0); value != -1; value = values.nextSetBit(value + 1)) {...}

What you need is to start not from 0 but from other known value.
Another way is to provide secondary iterator that does the same. It could be java-style but still ineffective and I am against this approach.
What you did is alternative approach, and if it works, let put them in work.
Possibly a bit more efficient and clearer would be doing explicit iterations, kind of

for(int i1 = 0; i1 < max; i1++) {
  for(int i2 = i1 + 1; i2 < max; i2++) {
    ...
  }
}

but in its current form CellSet doesn't allow this.

The more general question is whether heavily working with indexes on sparse sets is effective or not. In C/C++ I would use bitmaps instead of arrays of indexes in most of the code.

[SudokuMonster]

I'm confessing that my solutions attempt using what is available without groundbreaking solutions.

Like this

CellSet noYZ = new CellSet(new int[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80});
noYZ.removeAll(wxyzCell.getVisibleCells());
noYZ.removeAll(wzCell.getVisibleCells());
noYZ.removeAll(xzCell.getVisibleCells());	
CellSet yzCellRange = new CellSet(new int[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80});
yzCellRange.removeAll(noYZ);
yzCellRange.remove(wxyzCell);
yzCellRange.remove(wzCell);
yzCellRange.remove(xzCell);

which effectively allows me (without checking) that yzCell is exactly how I want it to be

My perceived efficiency improvement is in comparison to how I programmed it to start with. The current state may still be improved using better methods

[dobrichev]

In your example the two constructors are very slow - they dynamically create array of integers, then a loop over the array sets all provided bits one by one.

Using a predefined constant holding all 81 bits would accelerate the process, but cloning it (in order to modify) also takes resources - I don't know why, but cloning BitSet does take resources. The copy constructor in fact clones the given constant parameter but I didn't make precise measurements how faster it is compared to the cloning.

Better is to add a CellSet constructor that takes one or two integers as parameters. It can build the underlying BitSet from scratch using the builtin BitSet method set(int fromIndex, int toIndex).

Even better is to start from empty CellSet (requires new constructor, so far intentionally not implemented) and work with negate operations - instead of clearing, perform setting of the bits, and eventually negate the final result (requires new method negate which is also easy to implement based on builtin flip(from, to).

Seems that your sequence is logically equivalent to

CellSet yzCellRange = new CellSet(wxyzCell.getVisibleCells());
yzCellRange.addAll(wzCell.getVisibleCells());
yzCellRange.addAll(xzCell.getVisibleCells());
yzCellRange.add(wxyzCell);
yzCellRange.add(wzCell);
yzCellRange.add(xzCell);

In C++ using the lookups and structures defined in fsss2.h and t_128.h I would use such sequence

bm128 yzCellRange(constraints::visibleCells[wxyzCellIndex]); //accumulate needed cells here
yzCellRange |= constraints::visibleCells[wzCellIndex];
yzCellRange |= constraints::visibleCells[xzCellIndex];
yzCellRange.setBit(wxyzCellIndex); //unnecessary if it is seen by one of the other two cells
yzCellRange.setBit(wzCellIndex); //unnecessary if it is seen by one of the other two cells
yzCellRange.setBit(xzCellIndex); //unnecessary if it is seen by one of the other two cells
yzCellRange &= (bm128)constraints::mask81); //leave only bits in range 0..80

and would know that any of the operations takes few CPU ticks - sometimes less than one, several address calculations will be done, several memory reads, and zero memory writes.

Also, looking at your first rows of code in VWXYZWing.java, you need a method Cell.sees(Cell other) for !yzCell.sees(xzCell) which using existing methods can be coded as

!yzCell.getVisibleCells().contains(xzCell)

instead of

!(yzCell.getX() == xzCell.getX() || yzCell.getY() == xzCell.getY() || yzCell.getB() == xzCell.getB())

[SudokuMonster]

yzCellRange.addAll(xzCell.getVisibleCells());
yzCellRange.add(wxyzCell);

I didn't know that these existed! It is much easier to do them this way

you need a method Cell.sees(Cell other) for !yzCell.sees(xzCell)

makes sense. I'll look into that

[SudokuMonster]

@dobrichev I have now paused adding techniques. I will update Master with the current clunky additions. Work would then if there is time on enhancements

[dobrichev]

Close the issue?