3
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – DJHenjin Aug 28 '18 at 5:06
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Toby Speight Aug 28 '18 at 8:20
2
\$\begingroup\$

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_*

  5. Remove useless comments

    # If soduku is complete return it.
    if is_complete(soduku):
        return soduku
    

    The code is pretty self explenatory, and this comment only adds noise.

\$\endgroup\$
  • \$\begingroup\$ taking inspiration from (4) how about return all([constraint(soduku) for constraint in [unique_columns, unique_rows, unique_grids]]) for (3) \$\endgroup\$ – Harsh Aug 29 '18 at 2:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.