1
$\begingroup$

I am trying to solve a basic puzzle by using Google OR-Tools, this is my first try with OR-Tools and I am trying to learn. I completed almost everything and was ready to conclude the program until I came across this problem.

For information my game_board is a dictionary including entire board, with already given values and not given values that are set to IntVar.

I have several values in each cell as following:

  • Variable, cell is set as IntVar which were initially 0 in board, so it will be determined to be filled or not, values are 0 for empty, 1 for filled)
  • 8, the cell is free connection, indicating this is just a virtual cell added to represent the game in a matrix so cell above this, is connected to cell below it directly
  • 9, the cell is a solid block, so it separates its above and below cells.

What I do is, I iterate over the board and I am try to fill water according to gravity (and some other rules), so I assigned A cell should be equal to the cell below it if there is no block between them. However I forgot that, cell below can be full and the cell above can be empty, however with the constraint set above they can only be equal.

I used the part below the set the constraint mentioned above and I have 2 problems at this point.

if (row+1 <= max(row_variable_indices)) and (game_board[(row+1,column)] == 8):
  if (game_board[(row+1,column)] == -1):
    model.Add(game_board[(row,column)] == game_board[(row+1,column)])
  else:
    model.Add(game_board[(row,column)] == game_board[(row+2,column)])
  1. I overcame this by other methods, but still wanted to ask how can I differentiate IntVar from something else. I can not differentiate IntVar as checking IntVar == Int or IntVar != Int since thety both return True for any given Int. So I checked if cell is equal to 8 first, if cell is 8 then cell is either a free connection or a variable, and then I checked if cell is -1 as -1 is not used in the board anywhere, it would only choose the variables.

  2. My main problem is I need to change this constraint to A cell should be equal to the cell below it if there is no block between them and the cell below is assigned to 0. I tried doing it .OnlyEnforceIf() by something like following, but it didn't work and gave following error. How can I solve this. I understand I need to use BoolVar however I am not sure how to set a BoolVar for this condition (and for every other cell I have) because if I can not say if a variable A is set to value x, I can not set the bool based on if A is set to x either

model.Add(game_board[(row,column)] == game_board[(row+1,column)]).OnlyEnforceIf(game_board[(row+1,column)] == 1)

Note I actually tried it on some dummy matrix as following:

model.Add(x[(0,0)]==5).OnlyEnforceIf(x[(0,1)]==6)

/usr/local/lib/python3.6/dist-packages/ortools/sat/python/cp_model.py in OnlyEnforceIf(self, boolvar)
    607                     self.__constraint.enforcement_literal.append(b.Index())
    608         else:
--> 609             self.__constraint.enforcement_literal.append(boolvar.Index())
    610         return self
    611 

AttributeError: 'BoundedLinearExpression' object has no attribute 'Index'

Edited to add that, I can not change (or I don't know if I can) my IntVar variables to BoolVar variables and check this filling problem, because I also use sum() somewhere else counting the filled cells of that row/column by adding up the all IntVar variables of that row/column. I don't think it works in BoolVar as they don't have a value to be summed up unlike integer value of IntVar which is summable.

$\endgroup$
1
$\begingroup$

Okay I solved the main problem (2) after researching and playing around a bit with BoolVar. So unlike I thought, I don't have to assign BoolVar myself based on other things. Instead I could use its two cases True and False to check and bind the two cases I have. I made the modification below:

if (row+1 <= max(row_variable_indices)) and (game_board[(row+1,column)] == 8):
  a = model.NewBoolVar('a')
  if (game_board[(row+1,column)] == -1):
    model.Add(game_board[(row+1,column)] == 0).OnlyEnforceIf(a)
    model.Add(game_board[(row,column)] == game_board[(row+1,column)]).OnlyEnforceIf(a)

    model.Add(game_board[(row+1,column)] == 1).OnlyEnforceIf(a.Not())

  else:
    model.Add(game_board[(row+2,column)] == 0).OnlyEnforceIf(a)
    model.Add(game_board[(row,column)] == game_board[(row+2,column)]).OnlyEnforceIf(a)

    model.Add(game_board[(row+2,column)] == 1).OnlyEnforceIf(a.Not())

It assigns the cell below as 1 if and only if BoolVar == False. Assigns the cell below 0 if and only if BoolVar == True, and in this case assigns the top to bottom.

Don't forget to add BoolVar == False case, even if this case doesn't specify any relation between the top and bottom; If this is not set the bottom can be 0 with BoolVar == False and in this case top wouldn't be assigned to bottom and the violation of the required constraint (the top is equal to bottom if bottom is 0) may occur.

$\endgroup$

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.