CODEWITHSUNDEEP
pythonor-tools
mabo tang
mabo tang

Reputation: 11

N-Queens problem with adding the ordered constraint by using ortools

I try to use the code of this website for some practice. https://developers.google.com/optimization/cp/queens

Now I want to add the constraints that make the position of queens NOT be ascending(or descending) order above some continuous columns. For example, set board_size = 5.

(1) satisfied solution

Q _ _ _ _

_ _ Q _ _

_ _ _ _ Q

_ Q _ _ _

_ _ _ Q _

There is no ascending(or descending) order above three continuous columns.

(2) descending order

Q _ _ _ _

_ _ _ Q _

_ Q _ _ _

_ _ _ _ Q

_ _ Q _ _

There is an descending order from column1 to column3. (queen1 > queen2 > queen 3)

I add the following code, but it's not work.

for i in range(2, board_size):

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

How can I change the code to get the correct constraint make the position of queens NOT be ascending(or descending) order above some columns?

UPDATED: Here is my code for the problem.

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())

But it shows

Solutions found : 0

.

Upvotes: 1

Views: 278

Answers (2)

Mizux
Mizux

Reputation: 9271

did you try to use channeling ?

Pseudo-code

# 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())

Upvotes: 0

Laurent Perron
Laurent Perron

Reputation: 11014

Add two inequalities.

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

Upvotes: 1

Related Questions