Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit bad7128

Browse filesBrowse files
stonebigstonebig
committed
sudoku precision and ortools version
1 parent 3896ae7 commit bad7128
Copy full SHA for bad7128

File tree

Expand file treeCollapse file tree

2 files changed

+110
-2
lines changed
Filter options
Expand file treeCollapse file tree

2 files changed

+110
-2
lines changed

‎docs/Solvers_Raymond_Hettinger/python/sudoku_norvig_for_comparison_of_complexity.py

Copy file name to clipboardExpand all lines: docs/Solvers_Raymond_Hettinger/python/sudoku_norvig_for_comparison_of_complexity.py
+6-2Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -189,8 +189,12 @@ def random_puzzle(N=17):
189189

190190
grid1 = '003020600900305001001806400008102900700000008006708200002609500800203009005010300'
191191
grid2 = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
192-
hard1 = '.....6....59.....82....8....45........3........6..3.54...325..6..................'
193-
hard2 = '8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..'
192+
hard00 = '.......1......2..3...4...........5..4.16.......71......5....2......8..4..3.91....'
193+
hard0 = '........1.......23..4..5......1.........3.6....7...58.....67....1...4...52.......' #is a sudoku 17 digits, https://en.wikipedia.org/wiki/Mathematics_of_Sudoku
194+
hard1 = '.....6....59.....82....8....45........3........6..3.54...325..6..................' #aargh, not a sudoku !, https://www.thonky.com/sudoku/solution-count
195+
hard2 = '8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..'
196+
medi1 = '.6..5..2....3...9.7..6...1...6.3.4....4.7.1....5.9.8...4...1..6.3...8....2..4..5.'
197+
medi2 = '.2..........6....3.74.8.........3..2.8..4..1.6..5.........1.78.5....9..........4.'
194198
if __name__ == '__main__':
195199
test()
196200
solve_all([hard1], "easy", 0)

‎docs/Solvers_Raymond_Hettinger/python/sudoku_ortools.py

Copy file name to clipboard
+104Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
#!/usr/bin/env python3
2+
# Copyright 2010-2022 Google LLC
3+
# Licensed under the Apache License, Version 2.0 (the "License");
4+
# you may not use this file except in compliance with the License.
5+
# You may obtain a copy of the License at
6+
#
7+
# http://www.apache.org/licenses/LICENSE-2.0
8+
#
9+
# Unless required by applicable law or agreed to in writing, software
10+
# distributed under the License is distributed on an "AS IS" BASIS,
11+
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12+
# See the License for the specific language governing permissions and
13+
# limitations under the License.
14+
15+
"""This model implements a sudoku solver."""
16+
17+
from ortools.sat.python import cp_model
18+
19+
20+
def solve_sudoku():
21+
"""Solves the sudoku problem with the CP-SAT solver."""
22+
# Create the model.
23+
model = cp_model.CpModel()
24+
25+
cell_size = 3
26+
line_size = cell_size**2
27+
line = list(range(0, line_size))
28+
cell = list(range(0, cell_size))
29+
30+
initial_grid = [
31+
[0, 0, 0, 0, 0, 0, 0, 0, 1],
32+
[0, 0, 0, 0, 0, 0, 0, 2, 3],
33+
[0, 0, 4, 0, 0, 5, 0, 0, 0],
34+
[0, 0, 0, 1, 0, 0, 0, 0, 0],
35+
[0, 0, 0, 0, 3, 0, 6, 0, 0],
36+
[0, 0, 7, 0, 0, 0, 5, 8, 0],
37+
[0, 0, 0, 0, 6, 7, 0, 0, 6],
38+
[0, 1, 0, 0, 0, 4, 0, 0, 0],
39+
[5, 2, 0, 0, 0, 0, 0, 0, 0],
40+
]
41+
42+
hard1 = [
43+
[0, 0, 0, 0, 0, 6, 0, 0, 0],
44+
[0, 5, 9, 0, 0, 0, 0, 0, 8],
45+
[2, 0, 0, 0, 0, 8, 0, 0, 0],
46+
[0, 4, 5, 0, 0, 0, 0, 0, 0],
47+
[0, 0, 3, 0, 0, 0, 0, 0, 0],
48+
[0, 0, 6, 0, 0, 3, 0, 5, 4],
49+
[0, 0, 0, 3, 2, 5, 0, 0, 6],
50+
[0, 0, 0, 0, 0, 0, 0, 0, 0],
51+
[0, 0, 0, 0, 0, 0, 0, 0, 0],
52+
]
53+
hard0 = [
54+
[0, 0, 0, 0, 0, 0, 0, 0, 1],
55+
[0, 0, 0, 0, 0, 0, 0, 2, 3],
56+
[0, 0, 4, 0, 0, 5, 0, 0, 0],
57+
[0, 0, 0, 1, 0, 0, 0, 0, 0],
58+
[0, 0, 0, 0, 3, 0, 6, 0, 0],
59+
[0, 0, 7, 0, 0, 0, 5, 8, 0],
60+
[0, 0, 0, 0, 6, 7, 0, 0, 0],
61+
[0, 1, 0, 0, 0, 4, 0, 0, 0],
62+
[5, 2, 0, 0, 0, 0, 0, 0, 0],
63+
]
64+
65+
initial_grid = hard0
66+
67+
grid = {}
68+
for i in line:
69+
for j in line:
70+
grid[(i, j)] = model.NewIntVar(1, line_size, "grid %i %i" % (i, j))
71+
72+
# AllDifferent on rows.
73+
for i in line:
74+
model.AddAllDifferent(grid[(i, j)] for j in line)
75+
76+
# AllDifferent on columns.
77+
for j in line:
78+
model.AddAllDifferent(grid[(i, j)] for i in line)
79+
80+
# AllDifferent on cells.
81+
for i in cell:
82+
for j in cell:
83+
one_cell = []
84+
for di in cell:
85+
for dj in cell:
86+
one_cell.append(grid[(i * cell_size + di, j * cell_size + dj)])
87+
88+
model.AddAllDifferent(one_cell)
89+
90+
# Initial values.
91+
for i in line:
92+
for j in line:
93+
if initial_grid[i][j]:
94+
model.Add(grid[(i, j)] == initial_grid[i][j])
95+
96+
# Solve and print out the solution.
97+
solver = cp_model.CpSolver()
98+
status = solver.Solve(model)
99+
if status == cp_model.OPTIMAL:
100+
for i in line:
101+
print([int(solver.Value(grid[(i, j)])) for j in line])
102+
103+
104+
solve_sudoku()

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.