使用ortools添加有序约束的N-Queens问题

Question

我试着用这个网站的代码进行一些练习。https://developers.google.com/optimization/cp/queens

现在，我想添加约束，使皇后的位置不上升(或降序)在某些连续列之上。例如，设置board_size = 5。

(1)满意解

Q___

_q__

___

Q___

___

三列以上没有升序(或降序)。

(2)降序

Q___

___

Q___

___

_q__

从column1到column3有一个降序。(queen1 > queen2 >皇后3)

我添加了以下代码，但这不是工作。

for i in range(2, board_size):

  model.Add(queens[i - 2] <= queens[i - 1] <= queens[i])

如何更改代码以获得正确的约束，使皇后的位置不上升(或降序)在某些列之上？

更新:这是我的问题代码。

class SolutionPrinter(cp_model.CpSolverSolutionCallback):
  """Print intermediate solutions."""

  def __init__(self, variables):
    cp_model.CpSolverSolutionCallback.__init__(self)
    self.__variables = variables
    self.__solution_count = 0

  def OnSolutionCallback(self):
    self.__solution_count += 1
    for v in self.__variables:
      print('%s = %i' % (v, self.Value(v)), end = ' ')
    print()

  def SolutionCount(self):
    return self.__solution_count

  board_size = 5
  model = cp_model.CpModel()
  # Creates the variables.
  # The array index is the column, and the value is the row.
  queens = [model.NewIntVar(0, board_size - 1, 'x%i' % i)
            for i in range(board_size)]
  # Creates the constraints.
  # The following sets the constraint that all queens are in different rows.
  model.AddAllDifferent(queens)

  # Note: all queens must be in different columns because the indices of queens are all different.

  # The following sets the constraint that no two queens can be on the same diagonal.
  for i in range(board_size):
    # Note: is not used in the inner loop.
    diag1 = []
    diag2 = []
    for j in range(board_size):
      # Create variable array for queens(j) + j.
      q1 = model.NewIntVar(0, 2 * board_size, 'diag1_%i' % i)
      diag1.append(q1)
      model.Add(q1 == queens[j] + j)
      # Create variable array for queens(j) - j.
      q2 = model.NewIntVar(-board_size, board_size, 'diag2_%i' % i)
      diag2.append(q2)
      model.Add(q2 == queens[j] - j)
    model.AddAllDifferent(diag1)
    model.AddAllDifferent(diag2)
  
  for i in range(2, board_size):
    model.Add(queens[i - 2] <= queens[i - 1])
    model.Add(queens[i - 1] <= queens[i])
  
  ### Solve model.
  solver = cp_model.CpSolver()
  solution_printer = SolutionPrinter(queens)
  status = solver.SearchForAllSolutions(model, solution_printer)
  print()
  print('Solutions found : %i' % solution_printer.SolutionCount())      

但这表明

找到

解决方案:0

。

Answer 1

增加两个不等式。

model.Add(queens[i - 2] <= queens[i - 1])
model.Add(queens[i - 1] <= queens[i])

Answer 2

你试过使用通灵吗？

伪码

# Declare our intermediate boolean variable.
b = [model.NewBoolVar('b') for i in range(board_size-2)]

# Implement b[i] == (queens[i] < queens[i+1]).
for i in range(board_size-2):
  model.Add(queens[i] < queens[i+1]).OnlyEnforceIf(b[i])
  model.Add(queens[i] > queens[i+1]).OnlyEnforceIf(b[i].Not())

  # Create our two half-reified constraints.
  # First, b[i] implies (queens[i+1] > queens[i+2]).
  model.Add(queens[i+1] > queens[i+2]).OnlyEnforceIf(b[i])
  # Second, not(b[i]) implies queens[i+1] < queens[i+2].
  model.Add(queens[i+1] < queens[i+2]).OnlyEnforceIf(b[i].Not())