-
Notifications
You must be signed in to change notification settings - Fork 2
/
min_conflict.py
81 lines (63 loc) · 2.13 KB
/
min_conflict.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
"""
SudokuPyCSF - Solve sudoku with Python using CSF approach
Version : 1.0.0
Author : Hamidreza Mahdavipanah
Repository: http://github.com/mahdavipanah/SudokuPyCSF
License : MIT License
"""
import math
from random import randint
def var_conflicts(sudoku, var_i, var_j, new_val=None):
if new_val:
val = new_val
else:
val = sudoku[var_i][var_j]
var_conflicts = 0
# Check row
for j in range(len(sudoku)):
if sudoku[var_i][j] != 0 and sudoku[var_i][j] == val and j != var_j:
var_conflicts += 1
# Check column
for i in range(len(sudoku)):
if sudoku[i][var_j] != 0 and sudoku[i][var_j] == val and i != var_i:
var_conflicts += 1
# Check block
sqrt_n = int(math.sqrt(len(sudoku)))
block_i = int(var_i / sqrt_n)
block_j = int(var_j / sqrt_n)
qs = range(sqrt_n)
for i in [block_i * sqrt_n + q for q in qs]:
for j in [block_j * sqrt_n + q for q in qs]:
if (i, j) != (var_i, var_j) and sudoku[i][j] != 0 and sudoku[i][j] == val:
var_conflicts += 1
return var_conflicts
def sudoku_conflicts(sudoku):
sum_conflicts = 0
for i in range(len(sudoku)):
for j in range(len(sudoku)):
sum_conflicts += var_conflicts(sudoku, i, j)
return sum_conflicts
def search(sudoku, max_steps):
# Find fixed vars and randomize the sudoku
fixed_vars = set()
for i in range(len(sudoku)):
for j in range(len(sudoku)):
if sudoku[i][j] != 0:
fixed_vars.add((i, j))
else:
sudoku[i][j] = randint(1, len(sudoku))
domain = set(range(1, len(sudoku) + 1))
i = 0
while i < max_steps:
sum_conflicts = sudoku_conflicts(sudoku)
if sum_conflicts == 0:
return sudoku, 0
rand_i = randint(0, 8)
rand_j = randint(0, 8)
if (rand_i, rand_j) in fixed_vars:
continue
for val in domain:
if var_conflicts(sudoku, rand_i, rand_j) > var_conflicts(sudoku, rand_i, rand_j, val):
sudoku[rand_i][rand_j] = val
i += 1
return sudoku, sum_conflicts