The important characteristic is that the cells are all in the same box. Prob += pulp.lpSum( for n in range(1, 10)]) <= 1 Prob += pulp.lpSum( for i, j in distinct_group]) = target # binary choices: rows, columns and values 1-9 # groups that should only have 1 of each number 1-9Ĭol_groups = for j in range(9)]ĭistinct_groups = row_groups + col_groups + box_groups Prob = pulp.LpProblem("Sudoku_Problem_KA") If you want to avoid all the auxillary variables then you would just need to replace a sum-product with the index value as above anywhere you are currently using your integer variables.įull working code for completeness: import pulp You now have both sets of variables - one lot of binary variables, and one lot of integer variables which are linked with equality constraints to behave as required. Pulp += choices = pulp.lpSum(*k for k in range(1,10)]) If you've already developed all the code assuming your choice of variables (9x9 integer variables), you can add the 9x9x9 binary variables, and then constraint your 9x9 integer variables (which would now be auxiliary variables) as follows: for i in range(1, 10): This is quite straightforward - you just to a sum-product of the binary variables for a cell by the index which each varaible represents. (b) a way to easily add constraints of the 'sum' of cages in the 9x9x9 case. So to answer the second half of your question: It may seem like more variables but as far as I know use use of a smaller number of integer variables will not help solution time at all - the way the 'branch-and-bound' algorithm for solving a problem with integer variables will mean it's just as inefficient as having more binary variables (someone more familiar with this may be able to correct me). I would reccomend the use of binary variables - as per the examples you have found. # add constraints that cells in cages must equal 'cage_total'Ĭhoices * n for i, j in cells for n in range(1, 10) # add constraints that only one choice for each 'distinct_group'ĭistinct_group_constraint = for i, j in CAGE_CONSTRAINTS = [ĮDIT - if I try changing to a 9x9x9 problem with binary choices, I get results that don't match my desired cage constraints. If you would like the entire list of cage-constraints to test on, here are a list of cage-constraints from this puzzle. I am looking to (a) find a way to add this stricter constraint that no choices can be duplicated in the 9x9 setup, or (b) a way to easily add constraints of the 'sum' of cages in the 9x9x9 case. Prob += pulp.lpSum(cage_cells_constraint) = target # cells (0,0) and (0,1) must sum to 8Ĭage_constraints =, ])]Ĭage_cells_constraint = for i, j in cells] Here is an example of the 9x9x9 setup for a 'non-killer' sudoku. The issue is, I find it hard to see how to check the sums of 'cages' easily in the 9x9x9 case, whist this is quite simple in 9x9 case. I have seen several examples online, resolving this by reframing this optimisation as a 9x9x9 choice of binary flags, rather than 9x9 optimisation of choices of integers 1-9. Prob += pulp.lpSum(distinct_group_constraint) = 1 It would pass the constraint above, but would not be a valid sudoku row because each value is not unique.īelow is my attempt to add a stricter constraint, it seems not work, since the problem doesn't solve for n in range(1, 10):ĭistinct_group_constraint = n for i, j in distinct_group] The problem is I'm struggling to add a stricter constraint that each value in a row must be different. Code to add additional constraints for columns, boxes and 'cages'. Prob += pulp.lpSum(distinct_group_constraint) = 45 # Seems to work, make every row add up 45ĭistinct_group_constraint = for i, j in distinct_group] # identify puzzle rows that must have only 1 of every value # 9 by 9 grid of 'choices', integers between 1-9 Prob += 0, "Arbitrary Objective Function" Here is my attempt so far, adding a constraint that each row must add up to 45. I am trying to solve killer Sudoku using Python linear optimization library, Pulp.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |