2
$\begingroup$

I'll explain my problem with an analogy to Sudoku-grids.

Consider a filled Sudoku-grid. If you exchange labels or rearrange rows/columns within a block, you have another valid Sudoku-grid. However the new grid is essentially equivalent, if that makes sense. One might say, under the operations "swap rows", "exchange labels" etc., both grids are in the same orbit. (https://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerating_essentially_different_Sudoku_solutions)

I want to iterate over all grids, but in a way that the algorithm ignores other solutions in the same orbit. However, this question is not about Sudoku grids! My grids have a different structure, which is a bit simpler:

I want to fill a 4x6 table with the integers 1 to 8 (each three times) such that each row contains each integer at most once. There are a few other more complex conditions, but I think it's easier to check them later after a solution has been generated.

Just like in the Sudoku analogy, there are a few operations that generate other essentially equivalent solutions:

1) Rearranging rows: if one row is

1 3 5 6 2 8

the solution with that row replaced by

1 2 3 5 6 8

is of course also valid and consindered essentially equivalent.

2) Swapping rows.

3) Exchanging labels.

E.g. these solutions are essentially equivalent

1 3 5 6 2 8
4 1 5 7 8 2
4 7 6 1 2 3
3 4 5 6 8 7

First row rearranged:
1 2 3 5 6 8
4 1 5 7 8 2
4 7 6 1 2 3
3 4 5 6 8 7

First two rows swapped:
4 1 5 7 8 2
1 3 5 6 2 8
4 7 6 1 2 3
3 4 5 6 8 7

All 1's and 2's exchanged
2 3 5 6 1 8
4 2 5 7 8 1
4 7 6 2 1 3
3 4 5 6 8 7

My question is what an efficient (both runtime and memory) algorithm to generate these solutions might be.

The naive approach would be to store all previous solutions and check whether an equivalent solution has already been found. However, this is expensive in both runtime and memory!

I managed to improve this by calculating a hash of each solution in such a way that equivalent solutions generate the same hash. Then we can store the solutions in a map, so that we need to check fewer solutions and thus reduce the runtime. However, the memory cost is still huge.

If the hash has the property that different solutions yield different hashes, then I would only need to store the hashes and reduce the required memory by a large factor.

Can you think of a more elegant algorithm that does not store hashes nor previous solutions?

EDIT:

I simplified my problem too much without realising that I reduced the number of orbits to 1. (Thanks @Klaus Draeger). In fact the numbers 4,6,8 and 3 were made up as an example. I thought I could adapt the algorithm to the more general case later. Actually, my problem is a bit more complex: The number of rows is variable and rows need not have the same length, so rule 2) only applies to rows of equal length. Also the frequency of the numbers is not necessarily constant (e.g numbers 1,2,3,4 might appear four times and 5,6,7,8 three times or whatever), so rule 3) only applies to labels with the same frequency.

EDIT2:

And this is the more complex condition, that I thought doesn't matter for now. Maybe I'm wrong again...

If, in one row, y appears directly to the right of x (or y is in the first column and x in the last), then in a (unique) different row there must be an x to the right of y (above example does not satisfy this). This means that rule 1) only applies to rotations of rows and not any permutation.

I think this can be dealt with at a later point.

$\endgroup$
  • $\begingroup$ Not sure how much help this is, but this problem sounds equivalent to the one of constructing cellular decompositions of orientable $2$-manifolds - considering the labels as representing vertices and the rows as representing faces, a solution is the enumeration of the vertices on a face's boundary. The input data then specify the number of edges incident with each vertex and face. Are there known algorithms for this problem? $\endgroup$ – Klaus Draeger Sep 9 '15 at 14:56
  • $\begingroup$ @KlausDraeger Funnily enough, this is actually pretty much where I was coming from, if I understand the terminology correctly. Since I didn't know about cellular decompositions or any algorithms for it, I rewrote the problem in terms of rows etc :P The last condition I wrote (if there exists y after x etc) is exactly the property that behind an edge is the same edge from the other side, basically. $\endgroup$ – Alex Sep 9 '15 at 15:09
  • $\begingroup$ Yes, that is what suggested the connection. $\endgroup$ – Klaus Draeger Sep 9 '15 at 15:17
  • 2
    $\begingroup$ Please edit the question to be what it should have been from the start. Don't use EDIT, and don't write stuff like "my question is X. EDIT: oh wait, my question isn't quite X, it's actually Y" -- that's painful to read. Also, you need to decide what your exact question is. Writing things like "I also have an extra condition Z, but I think you might be able to ignore it, I'm not sure" is no good -- if you don't know what question you want to ask, how are we supposed to know what to answer? Thank you! $\endgroup$ – D.W. Jun 6 '16 at 3:01
  • $\begingroup$ Just hit us with the original problem; there's probably no need to dumb it down. $\endgroup$ – Raphael Sep 4 '16 at 7:54
1
$\begingroup$

All solutions are equivalent modulo the equivalence you have given.

Suppose $(a_{i,j})_{1\le i\le 4,1\le j\le 6}$ is some solution. Each row misses two labels, and these pairs of labels form a partition of $\{1,\dots,8\}$ (otherwise some label would occur too often). But then we can choose an exchange of labels modulo which row $1$ misses $7,8$; row $2$ misses $5,6$; row $3$ misses $3,4$; and row $4$ misses $1,2$.

Each row can then be reordered to arrive at the solution

$A=\begin{pmatrix}1&2&3&4&5&6\\1&2&3&4&7&8\\1&2&5&6&7&8\\3&4&5&6&7&8\end{pmatrix}$

Since every solution is equivalent to $A$, by transitivity, they are all equivalent.

$\endgroup$
  • $\begingroup$ Thanks! But I'm sorry, I simplified the problem too much. Can you have a look at the edit? $\endgroup$ – Alex Sep 9 '15 at 14:25
  • 1
    $\begingroup$ That does make things more interesting. I'll see what I can do. $\endgroup$ – Klaus Draeger Sep 9 '15 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.