Opened 7 years ago

Closed 6 years ago

# Do not count 4 times the same solution (up to rotations) in QuantuminoSolver

Reported by: Owned by: slabbe major sage-6.10 combinatorics vdelecroix Sébastien Labbé Vincent Delecroix N/A d72c8d9 d72c8d936da1c57fd7fd4971b65ee73c66eae7ea

### Description

The following computation takes a lot of time:

```sage: from sage.games.quantumino import QuantuminoSolver
sage: QuantuminoSolver(0).number_of_solutions()  # long time (several days)
```

A solution is a tiling of a 5x8x2 box. Since a 5x8x2 box has four orientation preserving isometries that preserves it, each solution up to rotation is counted four times in the computation above.

It is possible to avoid to compute 4 times the same solution. This ticket does this by choosing a piece and considering 4 times less positions for that piece.

This ticket was created from a split into two parts of #18987.

### comment:1 Changed 7 years ago by slabbe

• Branch set to u/slabbe/19107
• Commit set to 25ed836ab3fd20461bdfa509fdbb8e764c3458f7

Initials commits from the split that occured in #18987 (they do not depend on #18987).

New commits:

 ​5833a1e `Trac #19107: count solutions up to rotations` ​25ed836 `Trac #19107: Add a transparent gray box to QuantuminoState.show3d`

### comment:2 Changed 7 years ago by slabbe

• Status changed from new to needs_review

Salut Vincent, I am adding you in cc here since you started the review of that code at #18987.

### comment:3 follow-up: ↓ 5 Changed 7 years ago by vdelecroix

Salut,

```H = [h for h in G if all(i==j for (i,j) in h.matrix().nonzero_positions())]
```

You are iterating through the whole group to get the subgroup of diagonal matrices... but you know already what they are!

You can remove this line

```assert MatrixGroup(H).cardinality() == len(H)
```

To build the cosets, you would better use something smarter

```G_set = set(G)
cosets = []
while G_set:
g = G_set.pop()
left_coset = sorted(h*g for h in H)
right_coset = sorted(g*h for h in H)
assert left_coset == right_coset  # must be a normal subgroup
G_set.difference_update(left_coset)
cosets.append(left_coset)
```

There are some trailing whitespaces in ` _rows_modpi`

... more to come

### comment:4 Changed 7 years ago by vdelecroix

• Status changed from needs_review to needs_work

### comment:5 in reply to: ↑ 3 Changed 7 years ago by slabbe

```H = [h for h in G if all(i==j for (i,j) in h.matrix().nonzero_positions())]
```

The code below would be nice but leads to this bug: #19270.

```from sage.misc.misc_c import prod
it = itertools.product((1,-1), repeat=n)
if orientation_preserving:
H = [diagonal_matrix(L) for L in it if prod(L) == 1]
else:
H = [diagonal_matrix(L) for L in it]
H = G.subgroup(H)
```

If you can find a way of creating `G` and `H` so that `g * h` works and returns an hashable object for all g in G and h in H, tell me.

### comment:6 Changed 7 years ago by git

• Commit changed from 25ed836ab3fd20461bdfa509fdbb8e764c3458f7 to 23d109a75bd0c024af9fb6eb8865b85e0f66ada1

Branch pushed to git repo; I updated commit sha1. New commits:

 ​e5c36d5 `Trac #19107: Fixing reviewers comments (#3)` ​23d109a `Trac #19107: Using normal matrices instead of MatrixGroup elements`

### comment:7 Changed 7 years ago by slabbe

• Status changed from needs_work to needs_review

Okay, so I decided to use matrices + `.set_immutable()` instead of `MatrixGroup` elements.

Needs review!

### comment:8 Changed 7 years ago by vdelecroix

• Authors set to Sébastien Labbé
• Reviewers set to Vincent Delecroix
• Status changed from needs_review to needs_work

Merge conflict in src/sage/combinat/tiling.py

### comment:9 follow-up: ↓ 10 Changed 7 years ago by slabbe

Because of #19260 I guess...

### comment:10 in reply to: ↑ 9 ; follow-up: ↓ 12 Changed 7 years ago by vdelecroix

Because of #19260 I guess...

If it is then the merge will be very easy.

### comment:11 Changed 7 years ago by git

• Commit changed from 23d109a75bd0c024af9fb6eb8865b85e0f66ada1 to a1d44650afb5b9e0d9bb96f75b6641a3a1a5ce4d

Branch pushed to git repo; I updated commit sha1. New commits:

 ​a1d4465 `Fix conflicts of #19107 with sage-6.10.beta1`

### comment:12 in reply to: ↑ 10 Changed 7 years ago by slabbe

• Status changed from needs_work to needs_review

If it is then the merge will be very easy.

Indeed (I was expecting something worse), now needs review.

### comment:13 Changed 6 years ago by vdelecroix

• Milestone changed from sage-6.9 to sage-6.10
• Status changed from needs_review to needs_info

minor comment: The names `XYZ_iterator` is a bit heavy. With Python 3 more stuff is actually returning iterator (like `range`, `zip`) without explicit names. What about `isometric_copies` and `translated_copies`. In that case `canonical_isometric_copies` would better returns an iterator as well.

otherwise it looks good to me.

### comment:14 Changed 6 years ago by git

• Commit changed from a1d44650afb5b9e0d9bb96f75b6641a3a1a5ce4d to 3ef5d3a2e1e7edda2032fbfc66e2644e0c2ce231

Branch pushed to git repo; I updated commit sha1. New commits:

 ​df92a40 `Merge #19107 into sage-6.10.beta6` ​3ef5d3a `Trac #19107: rename methods XYZ_iterator -> XYZ`

needs review?

### comment:16 Changed 6 years ago by slabbe

• Status changed from needs_info to needs_review

I renamed the methods. I kept `canonical_isometric_copies` returning a set since it needs to avoid duplicates. And also returning `iter(set(it))` is bad if the user then creates a set out of it...

### comment:17 in reply to: ↑ 15 Changed 6 years ago by slabbe

needs review?

you're too fast:)

### comment:18 Changed 6 years ago by slabbe

I am still wondering if `modpi` is the good name for what I mean. Maybe `upto_box_isometries` would be better?

### comment:19 follow-up: ↓ 21 Changed 6 years ago by vdelecroix

• in any case you should be clearer in the documentation that its meaning somehow depends on the other argument `orientation_preserving`
• `up_to_box_isometries` is better than `upto_box_isometries`
• the prefix `mod` makes it clear that you are considering a quotient

### comment:20 Changed 6 years ago by git

• Commit changed from 3ef5d3a2e1e7edda2032fbfc66e2644e0c2ce231 to d72c8d936da1c57fd7fd4971b65ee73c66eae7ea

Branch pushed to git repo; I updated commit sha1. New commits:

 ​d72c8d9 `Trac #19107: renamed modpi -> mod_box_isometries`

### comment:21 in reply to: ↑ 19 Changed 6 years ago by slabbe

• in any case you should be clearer in the documentation that its meaning somehow depends on the other argument `orientation_preserving`

The documentation of both `orientation_preserving` and `mod_box_isometries` are now written in terms of the group of isometries of the n-cube. The first restrict to a subgroup whereas the second is quotient by a subgroup. And they are compatible. Tell me if it is better now.

Needs review.

### comment:22 Changed 6 years ago by vdelecroix

• Status changed from needs_review to positive_review

Good for me.