# source:trunk/examples/Sudoku2.py@340

Last change on this file since 340 was 340, checked in by smitchell, 4 years ago

release 1.4.7

File size: 4.1 KB
Line
1"""
2The Looping Sudoku Problem Formulation for the PuLP Modeller
3
4Authors: Antony Phillips, Dr Stuart Mitcehll
5"""
6# Import PuLP modeler functions
7from pulp import *
8
9# A list of strings from "1" to "9" is created
10Sequence = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
11
12# The Vals, Rows and Cols sequences all follow this form
13Vals = Sequence
14Rows = Sequence
15Cols = Sequence
16
17# The boxes list is created, with the row and column index of each square in each box
18Boxes =[]
19for i in range(3):
20    for j in range(3):
21        Boxes += [[(Rows[3*i+k],Cols[3*j+l]) for k in range(3) for l in range(3)]]
22
23# The prob variable is created to contain the problem data
24prob = LpProblem("Sudoku Problem",LpMinimize)
25
26# The problem variables are created
27choices = LpVariable.dicts("Choice",(Vals,Rows,Cols),0,1,LpInteger)
28
29# The arbitrary objective function is added
30prob += 0, "Arbitrary Objective Function"
31
32# A constraint ensuring that only one value can be in each square is created
33for r in Rows:
34    for c in Cols:
35        prob += lpSum([choices[v][r][c] for v in Vals]) == 1, ""
36
37# The row, column and box constraints are added for each value
38for v in Vals:
39    for r in Rows:
40        prob += lpSum([choices[v][r][c] for c in Cols]) == 1,""
41
42    for c in Cols:
43        prob += lpSum([choices[v][r][c] for r in Rows]) == 1,""
44
45    for b in Boxes:
46        prob += lpSum([choices[v][r][c] for (r,c) in b]) == 1,""
47
48# The starting numbers are entered as constraints
49prob += choices["5"]["1"]["1"] == 1,""
50prob += choices["6"]["2"]["1"] == 1,""
51prob += choices["8"]["4"]["1"] == 1,""
52prob += choices["4"]["5"]["1"] == 1,""
53prob += choices["7"]["6"]["1"] == 1,""
54prob += choices["3"]["1"]["2"] == 1,""
55prob += choices["9"]["3"]["2"] == 1,""
56prob += choices["6"]["7"]["2"] == 1,""
57prob += choices["8"]["3"]["3"] == 1,""
58prob += choices["1"]["2"]["4"] == 1,""
59prob += choices["8"]["5"]["4"] == 1,""
60prob += choices["4"]["8"]["4"] == 1,""
61prob += choices["7"]["1"]["5"] == 1,""
62prob += choices["9"]["2"]["5"] == 1,""
63prob += choices["6"]["4"]["5"] == 1,""
64prob += choices["2"]["6"]["5"] == 1,""
65prob += choices["1"]["8"]["5"] == 1,""
66prob += choices["8"]["9"]["5"] == 1,""
67prob += choices["5"]["2"]["6"] == 1,""
68prob += choices["3"]["5"]["6"] == 1,""
69prob += choices["9"]["8"]["6"] == 1,""
70prob += choices["2"]["7"]["7"] == 1,""
71prob += choices["6"]["3"]["8"] == 1,""
72prob += choices["8"]["7"]["8"] == 1,""
73prob += choices["7"]["9"]["8"] == 1,""
74prob += choices["3"]["4"]["9"] == 1,""
75prob += choices["1"]["5"]["9"] == 1,""
76prob += choices["6"]["6"]["9"] == 1,""
77prob += choices["5"]["8"]["9"] == 1,""
78
79# The problem data is written to an .lp file
80prob.writeLP("Sudoku.lp")
81
82# A file called sudokuout.txt is created/overwritten for writing to
83sudokuout = open('sudokuout.txt','w')
84
85while True:
86    prob.solve()
87    # The status of the solution is printed to the screen
88    print "Status:", LpStatus[prob.status]
89    # The solution is printed if it was deemed "optimal" i.e met the constraints
90    if LpStatus[prob.status] == "Optimal":
91        # The solution is written to the sudokuout.txt file
92        for r in Rows:
93            if r == "1" or r == "4" or r == "7":
94                sudokuout.write("+-------+-------+-------+\n")
95            for c in Cols:
96                for v in Vals:
97                    if value(choices[v][r][c])==1:
98                        if c == "1" or c == "4" or c =="7":
99                            sudokuout.write("| ")
100                        sudokuout.write(v + " ")
101                        if c == "9":
102                            sudokuout.write("|\n")
103        sudokuout.write("+-------+-------+-------+\n\n")
104        # The constraint is added that the same solution cannot be returned again
105        prob += lpSum([choices[v][r][c] for v in Vals
106                                        for r in Rows
107                                        for c in Cols
108                                        if value(vars[v][r][c])==1]) <= 80
109    # If a new optimal solution cannot be found, we end the program
110    else:
111        break
112sudokuout.close()
113
114# The location of the solutions is give to the user
115print "Solutions Written to sudokuout.txt"
Note: See TracBrowser for help on using the repository browser.