Solving sudoku using Backtracking-Search (BTS) with Minimum Remaining Values (MRV) heuristic

Intro

I wrote this code to solve sudoku as part of an assignment (closed now) for an AI course. The program works correctly and I am quite happy with the code. Please let me know if I am rightfully pleased or if the implementation could be so much better.

This is a pure code review question so don't hold back on anything.

The problem

Input

The input is an 81 character string representing the sudoku board with digits listed row-wise. Empty spaces are represented by zeros.
000000000302540000050301070000000004409006005023054790000000050700810000080060009

Output

The program must output the solved sudoku board to a text file output.txt in the same string representation as the input.
148697523372548961956321478567983214419276385823154796691432857735819642284765139

Algorithm

The algorithm is based on backtracking search (glorified DFS) but will also include a heuristic that treats the sudoku as a CSP (constraint satisfaction problem) to improves results. The heuristic Minimal Remaining Values favours making assignments to those variables first that have the least number of available options. (Intuitively it is like attempting to solve the harder ones first so we can backtrack sooner if things don't pan out.)

The algorithm (from AIMA) :-

function RECURSIVE-BACKTRACKING(assignment, csp) returns a solution, or failure
if assignment is complete then return assignment
var ← SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp], assignment, csp)
for each value in ORDER-DOMAIN-VALUES(var , assignment, csp) do
if value is consistent with assignment according to CONSTRAINTS[csp] then
add {var = value} to assignment
result ← RECURSIVE-BACKTRACKING(assignment, csp)
if result != failure then return result
remove {var = value} from assignment
return failure


Code

Here is the code up for review:-

import sys
import numpy as np
from functools import reduce

# Instructions:
# Linux>> python3 driver_3.py <soduku_str>
# Windows py3\> python driver_3.py <soduku_str>

# Inputs
print("input was:", sys.argv)
soduku_str=sys.argv[1]

def str2arr(soduku_str):
"Converts soduku_str to 2d array"
return np.array([int(s) for s in list(soduku_str)]).reshape((9,9))

soduku = str2arr(soduku_str)

slices = [slice(0,3), slice(3,6), slice(6,9)]
s1,s2,s3 = slices
allgrids=[(si,sj) for si in [s1,s2,s3] for sj in [s1,s2,s3]] # Makes 2d slices for grids

def var2grid(var):
"Returns the grid slice (3x3) to which the variable's coordinates belong "
row,col = var
grid = ( slices[int(row/3)], slices[int(col/3)] )
return grid

FULLDOMAIN = np.array(range(1,10)) #All possible values (1-9)

# Constraints
def unique_rows(soduku):
for row in soduku:
if not np.array_equal(np.unique(row),np.array(range(1,10))) :
return False
return True
def unique_columns(soduku):
for row in soduku.T: #transpose soduku to get columns
if not np.array_equal(np.unique(row),np.array(range(1,10))) :
return False
return True

def unique_grids(soduku):
for grid in allgrids:
if not np.array_equal(np.unique(soduku[grid]),np.array(range(1,10))) :
return False
return True

def  isComplete(soduku):
if 0 in soduku:
return False
else:
return True

def checkCorrect(soduku):
if unique_columns(soduku):
if unique_rows(soduku):
if unique_grids(soduku):
return True
return False

# Search
def getDomain(var, soduku):
"Gets the remaining legal values (available domain) for an unfilled box var in soduku"
row,col = var
#ravail = np.setdiff1d(FULLDOMAIN, soduku[row,:])
#cavail = np.setdiff1d(FULLDOMAIN, soduku[:,col])
#gavail = np.setdiff1d(FULLDOMAIN, soduku[var2grid(var)])
#avail_d = reduce(np.intersect1d, (ravail,cavail,gavail))
used_d = reduce(np.union1d, (soduku[row,:], soduku[:,col], soduku[var2grid(var)]))
avail_d = np.setdiff1d(FULLDOMAIN, used_d)
#print(var, avail_d)
return avail_d

def selectMRVvar(vars, soduku):
"""
Returns the unfilled box var with minimum remaining [legal] values (MRV)
and the corresponding values (available domain)
"""
#Could this be improved?
avail_domains = [getDomain(var,soduku) for var in vars]
avail_sizes = [len(avail_d) for avail_d in avail_domains]
index = np.argmin(avail_sizes)
return vars[index], avail_domains[index]

def BT(soduku):
"Backtracking search to solve soduku"
# If soduku is complete return it.
if isComplete(soduku):
return soduku
# Select the MRV variable to fill
vars = [tuple(e) for e in np.transpose(np.where(soduku==0))]
var, avail_d = selectMRVvar(vars, soduku)
# Fill in a value and solve further (recursively),
# backtracking an assignment when stuck
for value in avail_d:
soduku[var] = value
result = BT(soduku)
if np.any(result):
return result
else:
soduku[var] = 0
return False

# Solve
print("solved:\n", BT(soduku))
print("correct:", checkCorrect(soduku))

# Output
with open('output.txt','w') as f:
output_str = np.array2string(soduku.ravel(), max_line_width=90, separator='').strip('[]') + ' Solved with BTS'
f.write(output_str)

• In def checkCorrect, you don’t need to nest he if statements, in fact it makes it look worse if you do. Instead you can have each be if not unique_columns return false, and similar for the others Aug 28, 2018 at 5:06
• @DJHenjin - please add an Answer to make code improvement suggestions (so we can upvote them, for example). Use comments only for improving the question. Thanks. Aug 28, 2018 at 8:20

Your algo is good, I have a few styling nitpicks.

1. Use a if__name__ == '__main__'

This will make sure that when you import this script the root lines will not be executed.

2. Read PEP8 the Python styleguide

• Functions and variables should be snake_case
3. Return directly

As @DJHenjin correctly state, you don't need the nested if statements.

def checkCorrect(soduku):
if unique_columns(soduku):
if unique_rows(soduku):
if unique_grids(soduku):
return True
return False


Can be rewritten as

def check_correct(soduku):
return unique_columns(soduku) and unique_rows(soduku) and unique_grids(soduku)

4. You can use the all or any to make it more pretty

def unique_grids(soduku):
for grid in allgrids:
if not np.array_equal(np.unique(soduku[grid]),np.array(range(1,10))) :
return False
return True


Can be rewritten as

def unique_grid(sudoku):
return all(np.array_equal(np.unique(soduku[grid]),np.array(range(1,10)))
for grid in all_grids)


Same for the other unique_*

# If soduku is complete return it.

• taking inspiration from (4) how about return all([constraint(soduku) for constraint in [unique_columns, unique_rows, unique_grids]]) for (3) Aug 29, 2018 at 2:53