Introduction

This article is the 4th article to solve the practice problem of the reference text "Problem solving series by Python: How to make an optimization model using a data analysis library" about mathematical optimization.

The first article is below. Please see here first.

Solving mathematical optimization model exercises with Google's OR-Tools (1) The easiest mass filling problem https://qiita.com/ttlabo/private/7e8c93f387814f99931f

Solve the number place (sudoku)

This is the third exercise in the reference text. Let's try the following problems at once.

: speech_balloon: Problem

`ruby:7.3.problem`


Number place in the figure below(Sudoku)Solve. However, the conditions are as follows.
① Be sure to fill the numbers 1 to 9 in all 9x9 squares.
(2) The same number can be used only once in any one row, any one column, and any 3x3.
③ Use the numbers where they are filled.

: question: ** Thinking **

■ Think of a mathematical model Consider 729 9x9x9 boxes, as shown in Figure 2. The axis direction is row, column, and cell numbers. A cell number means a number that fits in each frame of Sudoku.

Suppose a box has either selected or unselected cell numbers.

For example, suppose the first box from the bottom of the 1st row and 1st column has 1 if the number 1 is selected in the 1st row and 1st column cell of Sudoku, and 0 if it is not selected. Following this, the second box from the bottom of the first row, first column cell indicates whether the number 2 is selected or not, and similarly, the top box indicates whether the number 9 is selected or not. These continue in the same way up to the 9th row and 9th column. In general, if the box of cell number z in row x column y cell number z is 1, it means that the number in the cell of row x row y column of Sudoku is z.

Assuming such a box, we will formulate it.

: a: ** Answer **

Each of these 729 boxes will be 0 or 1. The constraints are as follows:

(1) Only one number can be entered in one cell of Sudoku. That is, the total value of 9 boxes of 1x1x9 (row x column x cell number) is 1. (2) Only one same number can be entered in one cell. The total value of 9 boxes of 9x1x1 is 1. (3) Only one same number can be entered in one row of cells. The total value of 9 boxes of 1x9x1 is 1. (4) Only one same number can be entered in a 3x3 square. The total value of 9 boxes of 3x3x1 is 1.

3x3 squares are the 9 squares shown by the thick lines in the attached figure of the question sentence. (5) If the number is specified from the beginning (the figure attached to the problem statement), use that number. The total value of one box of 1x1x1 is 1.

Consider the program. The contents of the program basically follow Google's OR-Tools guide. (https://developers.google.com/optimization)

Write a spell at the beginning of the program.

`ruby:7.4.renshu.py`


from __future__ import print_function
from ortools.linear_solver import pywraplp
import numpy as np

Since it is solved by the mixed integer programming solver, it is declared below.

`ruby:7.4.renshu.py`


# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
    pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

Define the 9x9 squares of Sudoku presented in the problem in the following two-dimensional array pre.

`ruby:7.4.renshu.py`


pre = [[0,0,6,0,0,0,0,0,1],
       [0,7,0,0,6,0,0,5,0],
       [8,0,0,1,0,3,2,0,0],
       [0,0,5,0,4,0,8,0,0],
       [0,4,0,7,0,2,0,9,0],
       [0,0,8,0,1,0,7,0,0],
       [0,0,1,2,0,5,0,0,3],
       [0,6,0,0,7,0,0,8,0],
       [2,0,0,0,0,0,4,0,0]]

Declare 9x9x9 boxes as the 3D array variable dice.

`ruby:7.4.renshu.py`


dice = {}

For 9x9x9 boxes (dice boxes), define each box with a variable. Loop the line from 1 to 9 with the variable x. Loop the column from 1 to 9 with the variable y. Loop with the variable z in the cell number direction.

`ruby:7.4.renshu.py`


#Variable definition of dice box
for x in range(9):
    for y in range(9):
        for z in range(9):
            dice[x,y,z] = solver.BoolVar("dice%i%i%i" % (x,y,z))

The constraints are defined below.

** Constraints (1) ** `Only one number can be entered in one cell of Sudoku. That is, the total value of 9 boxes of 1x1x9 (row x column x cell number) is 1. `` Use solver.Sum () to get the total value. The value to be totaled is from 1 to 9 squares in the z direction of dice, and z is looped from 1 to 9 in the inclusion notation (actually, the index value loops from 0 to 8).

`ruby:7.4.renshu.py`


for x in range(9):
    for y in range(9):
        solver.Add(solver.Sum([dice[x,y,z] for z in range (9)]) == 1)

** Constraint (2) ** Only one same number can be entered in a cell on one line. The total value of 9 boxes of 9x1x1 is 1

`ruby:7.4.renshu.py`


for y in range(9):
    for z in range(9):
        solver.Add(solver.Sum([dice[x,y,z] for x in range (9)]) == 1)

** Constraints (3) ** (3) Only one same number can be entered in a cell in a row. The total value of 9 boxes of 1x9x1 is 1

`ruby:7.4.renshu.py`


for x in range(9):
    for z in range(9):
        solver.Add(solver.Sum([dice[x,y,z] for y in range (9)]) == 1)

** Constraints (4) ** (4) Only one same number can be entered in a 3x3 square. The total value of 9 boxes of 3x3x1 is 1

`ruby:7.4.renshu.py`


#Loop in the z-axis direction
for z in range(9):
    #Loop the x coordinate taken by the center cell of a 3x3 square
    for m1 in [1,4,7]:
        #Loop through the y coordinate taken by the center cell of a 3x3 square
        for m2 in [1,4,7]:
            solver.Add(solver.Sum([dice[x,y,z] for x in [m1 - 1,m1,m1 + 1] for y in [m2 - 1,m2,m2 + 1]]) == 1)

** Constraints (5) ** (5) In the cell where the number is specified from the beginning (problem sentence attached figure), it is the number. The total value of one box of 1x1x1 is 1

`ruby:7.4.renshu.py`


for x in range(9):
    for y in range(9):
        if pre[x][y] != 0:
            z = pre[x][y]
            solver.Add(dice[x,y, z - 1] == 1)

That is all for the constraints. Find a solution. This time there is no need to maximize or minimize.

`ruby:7.4.renshu.py`


#Solution execution
status = solver.Solve()

Validate the result.

`ruby:7.4.renshu.py`


if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Solution:')
    print('ok')
    print('Objective value =', solver.Objective().Value())

    #Create an array p for display
    p = []
    for x in range(9):
        for y in range(9):
            for z in range(9):
                if dice[x,y,z].solution_value() > 0.5:
                    p.append(z + 1)

    print(np.reshape(p, (9, 9)))                    
    print("Time = ", solver.WallTime(), " milliseconds")
else:
    print('The problem does not have an optimal solution.')

In this execution, the following solution was obtained.

Solution: ok Objective value = 0.0 [[5 3 6 8 2 7 9 4 1] [1 7 2 9 6 4 3 5 8] [8 9 4 1 5 3 2 6 7] [7 1 5 3 4 9 8 2 6] [6 4 3 7 8 2 1 9 5] [9 2 8 5 1 6 7 3 4] [4 8 1 2 9 5 6 7 3] [3 6 9 4 7 1 5 8 2] [2 5 7 6 3 8 4 1 9]] Time = 477 milliseconds

Sudoku was solved above. The figure below shows this in the square. The pink part is the cell whose number was decided in advance when the question was asked.

The entire program is described below.

`ruby:7.4.renshu.py`


from __future__ import print_function
from ortools.linear_solver import pywraplp
import numpy as np

# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
    pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

pre = [[0,0,6,0,0,0,0,0,1],
       [0,7,0,0,6,0,0,5,0],
       [8,0,0,1,0,3,2,0,0],
       [0,0,5,0,4,0,8,0,0],
       [0,4,0,7,0,2,0,9,0],
       [0,0,8,0,1,0,7,0,0],
       [0,0,1,2,0,5,0,0,3],
       [0,6,0,0,7,0,0,8,0],
       [2,0,0,0,0,0,4,0,0]]


#Variable definition of dice box
dice = {}
for x in range(9):
    for y in range(9):
        for z in range(9):
            dice[x,y,z] = solver.BoolVar("dice%i%i%i" % (x,y,z))

#Constraint 1-One number per square(1 out of 9 boxes that contains 1 when looping in the z direction)
for x in range(9):
    for y in range(9):
        solver.Add(solver.Sum([dice[x,y,z] for z in range (9)]) == 1)

#Constraint 2-Vertical(y direction)The same number is one(y directionにループした際に1が入る箱は9個のうち1個)
for x in range(9):
    for z in range(9):
        solver.Add(solver.Sum([dice[x,y,z] for y in range (9)]) == 1)

#Constraint 3-side(x direction)The same number is one(x directionにループした際に1が入る箱は9個のうち1個)
for y in range(9):
    for z in range(9):
        solver.Add(solver.Sum([dice[x,y,z] for x in range (9)]) == 1)

#Constraint 4-One same number in 3x3 square
#Loop in the z-axis direction
for z in range(9):
    #Loop the x coordinate taken by the center cell of a 3x3 square
    for m1 in [1,4,7]:
        #Loop through the y coordinate taken by the center cell of a 3x3 square
        for m2 in [1,4,7]:
            solver.Add(solver.Sum([dice[x,y,z] for x in [m1 - 1,m1,m1 + 1] for y in [m2 - 1,m2,m2 + 1]]) == 1)

#Constraint 5-The square containing the number is the number
for x in range(9):
    for y in range(9):
        if pre[x][y] != 0:
            z = pre[x][y]
            #print('z=',z)
            solver.Add(dice[x,y, z - 1] == 1)

#Solution execution
status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Solution:')
    print('ok')
    print('Objective value =', solver.Objective().Value())

    #Create an array p for display
    p = []
    for x in range(9):
        for y in range(9):
            for z in range(9):
                if dice[x,y,z].solution_value() > 0.5:
                    p.append(z + 1)

    print(np.reshape(p, (9, 9)))                    
    print("Time = ", solver.WallTime(), " milliseconds")
else:
    print('The problem does not have an optimal solution.')

Exhibit

This article is based on the exercises described in the reference text "Problem Solving Series with Python: How to Create an Optimization Model Using a Data Analysis Library" about mathematical optimization.

■ Reference text "Problem-solving series using Python: How to create an optimization model using a data analysis library" Tsutomu Saito [Author] Modern Science Company [Publishing]

Opinions etc.

If you have any opinions or corrections, please let us know.

[PYTHON] Solve Mathematical Optimization Model Exercises with Google's OR-Tools (4) Solve Number Places

Introduction

Solve the number place (sudoku)

ruby:7.3.problem

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

Exhibit

Opinions etc.

`ruby:7.3.problem`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`