N-Queens Symmetry Breaking Google OR Tools

Question

One example for Google or-tools is the n-queens problem solver. It says below that the implementation can be improved by adding constraints on the violation of symmetry to the constraint resolver.

Looking around the internet, I found symmetry constraint limitations for the n-queens problem , but I can't figure out how to convert them into restrictions on the python code that implements them for life.

---

EDIT: it was a bad question, let it be updated ...

What have i tried?

Here is the installation from the first link above:

from ortools.constraint_solver import pywrapcp N = 8 solver = pywrapcp.Solver("n-queens") # Creates the variables. # The array index is the column, and the value is the row. queens = [solver.IntVar(0, N - 1, "x%i" % i) for i in range(N)] # Creates the constraints. # All rows must be different. solver.Add(solver.AllDifferent(queens)) # All columns must be different because the indices of queens are all different. # No two queens can be on the same diagonal. solver.Add(solver.AllDifferent([queens[i] + i for i in range(N)])) solver.Add(solver.AllDifferent([queens[i] - i for i in range(N)])) # TODO: add symmetry breaking constraints db = solver.Phase(queens, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) solver.NewSearch(db) num_solutions = 0 while solver.NextSolution(): num_solutions += 1 solver.EndSearch() print() print("Solutions found:", num_solutions) print("Time:", solver.WallTime(), "ms") 

I know that I can successfully implement simple restrictions. If I wanted the solution to always have a queen in the first column in the first row, I could implement this as follows:

 solver.Add(queens[0] == 0) 

The variable queens[0] represents the location of the queen in the first column, and this restriction is only satisfied when the first column has a queen in the first row. This, of course, is not what I want to do, because it is possible that the solution does not contain any corner cells.

Limitations on symmetry breaking for the n-queens problem are given below. They are pulled directly from the link in the second paragraph.

I understand how these limitations work. The idea is that you can apply this function to every cell on the n-queens board to convert the state to an equivalent state. One of these states will be the canonical representation of this state. This is used as a method to reduce future processing by eliminating duplicate ratings.

If I just realized this after I did this, I would do exactly what I described above, transform the state with every possible symmetry breaking function, by computing some kind of status hash (for example, a row of the selected row in each column) and select the one that is the lowest for each proposed solution. Skip future processing on the ones we saw before.

My problem is that I don’t know how to convert these conversions to constraints for a constraint programming solution for google or-tools.

Let's look at the simplest, d1(r[i] = j) => r[j] = i , the reflection of the main diagonal. I know that the transformation needs to be applied to all cells, and then compared with the current state in order to prevent its expansion. I don’t understand enough about python to understand which expression works here for the conversion, and I just cannot understand how to create a constraint that compares the transformation with the current state for this particular solver.

 state = [queens[i].Value() for i in range(N)] symX = [state[N - (i + 1)] for i in range(N)] symY = [N - (state[i] + 1) for i in range(N)] symD1 = [state.index(i) for i in range(N)] symD2 = [N - (state.index(N-(i+1)) + 1) for i in range(N)] symR90 = [N - (state.index(i) + 1) for i in range(N)] symR180 = [N - (state[N-(i+1)] + 1) for i in range(N)] symR270 = [state.index(N-(i+1)) for i in range(N)] 

Answer 1

You should use the well-known symmetry relationships between the solutions you are looking for to determine the constraints that will eliminate the equivalent solutions.

• For each solution with queens[0] >= N/2 , then there is another vertically mirrored solution with queens[0] <= N/2 . Therefore, we can look for a solution with a lower value of queens[0] and add the following restriction:

   solver.Add(queens[0] < (N+1)//2) # Handle both even and odd values of N 

• Then a solution satisfying the condition queens[0] < queens[N-1] has an equivalent horizontal-mirror solution satisfying the condition queens[0] > queens[N-1] . You can tell the solver to look for only those solutions where the queen in the leftmost column is below the queen in the rightmost column:

   solver.Add(queens[0] < queens[N-1]) 

I could not easily formulate a restriction reflecting rotational symmetry, but I believe that this is possible.

Answer 2

I tried using a custom DecisionBuilder to crop the search tree using symmetries as new constraints, but I could not get it to work.

Instead, I had to use SearchMonitor, which captures the event of each solution and checks whether this solution is the symmetry of the previous one.

Here I add SearchMonitor code, a capture of the solution that overrides the AcceptSolution function, and the gen_symetries function to calculate and verify all possible symmetries.

  class SearchMonitor(pywrapcp.SearchMonitor): def __init__(self, solver, q): pywrapcp.SearchMonitor.__init__(self, solver) self.q = q self.all_solutions = [] self.unique_solutions = [] self.n = len(self.q) def AcceptSolution(self): qval = [self.q[i].Value() for i in range(self.n)] self.all_solutions.append(qval) symmetries = [vv in self.unique_solutions for vv in gen_symmetries(self.n, qval)] if sum(symmetries) == 0: self.unique_solutions.append(qval) return False def gen_symmetries(n, solution): symmetries = [] #x(r[i]=j) → r[n−i+1]=j x = list(range(n)) for index in range(n): x[n - 1 - index] = solution[index] symmetries.append(x) #y(r[i]=j) → r[i]=n−j+1 y = list(range(n)) for index in range(n): y[index] = (n - 1 - solution[index]) symmetries.append(y) #d1(r[i]=j) → r[j]=i d1 = list(range(n)) for index in range(n): d1[solution[index]] = index symmetries.append(d1) # d2(r[i]=j) → r[n−j+1]=n−i+1 d2 = list(range(n)) for index in range(n): d2[n - 1 - solution[index]] = (n - 1 - index) symmetries.append(d2) # r90(r[i]=j) → r[j] = n−i+1 r90 = list(range(n)) for index in range(n): r90[solution[index]] = (n - 1 - index) symmetries.append(r90) # r180(r[i]=j) → r[n−i+1]=n−j+1 r180 = list(range(n)) for index in range(n): r180[n - 1 - index] = (n - 1 - solution[index]) symmetries.append(r180) # r270(r[i]=j) → r[n−j+1]=i r270 = list(range(n)) for index in range(n): r270[n - 1 - solution[index]] = index symmetries.append(r270) return symmetries 

Later, you just need to add a monitor to your solver like this.

 monitor = SearchMonitor(solver, queens) solver.Solve(db, monitor) solver.NewSearch(db) 

And finally, just print all the unique solutions.

 print("Unique Solutions:", len(monitor.unique_solutions), monitor.unique_solutions) 

You can see the full working example in essence.

https://gist.github.com/carlgira/7a4e6cf0f7b7412762171015917bccb4