# Sudoku challenge driver program

For my planned Sudoku with Handicap challenge over at codegolf.SE, I need a driver program. I've decided to write it in Python, for learning purposes. Since I've got no Python experience, I thought I put it here to see whether it can be improved.

The code is intended to implement the rules as written in the the linked post, except that it tests only one Sudoku (combining the score of several Sudokus is easy to do).

The program gets as first argument the file containing the Sudoku, followed by the command line to start the entry to be scored.

The Sudoku is given in a file containing a 9×9 digit grid, with unknown digits represented by a dot. That grid is followed by an empty line, and a second grid containing the solution. The program checks that the solution indeed fits the original Sudoku (that way I've already spotted a typo on the solution of the first Sudoku in my post), but doesn't currently do any further tests of the validity of the input data.

While validation of the Sudoku file is only nice to have, correct validation of the entries is crucial: It should catch all clients that violate the rules, and even more importantly, it should not declare any valid entry as invalid.

Here's the contents of the file for my first test Sudoku (that's the file I've also done all my testing with):

4.5.7.89.
..2.5.6..
..79..542
..35.6489
...3.8...
6847.91..
238..59..
..6.9.3..
.79.3.2.1

415672893
892453617
367981542
723516489
951348726
684729135
238165974
146297358
579834261


And this is the code:

#!/usr/bin/python

from __future__ import print_function

import sys
import itertools
import subprocess
import re
import copy

# -------------------------------------------------------------------
# general functions
# -------------------------------------------------------------------

# Remove leading and trailing whitespace from all lines
def trim_lines(text):
return map(lambda s: s.strip(), text);

# (for debugging purposes only)
# print a list of lists as 2D array
def arrayprint(array, width):
for row in array:
print( (("{:>"+str(width)+"}")*len(array[0])).format(*row) )

# print on stderr
def error(*content):
print(*content, file=sys.stderr)

# load the content of a file
try:
file = open(filename)
file.close()
except:
error("Could not read file ", filename)
sys.exit(1)
return file_content

def testall(predicate, list):
return reduce(lambda x, y: x and y, [True]+map(predicate, list))

# -------------------------------------------------------------------
# field manipulation and verification
# -------------------------------------------------------------------

def constfield(value):
return [x[:] for x in [[value]*9]*9]

# get the data indicated by the specifier string from the working field
def get_data(field, scratch, specifier):
def subfield(field, k):
i = (k-1) / 3
j = (k-1) % 3
sub3x3=map(lambda s: s[3*i:3*i+3],field[3*j:3*j+3])
return itertools.chain(*sub3x3)

if specifier != "S":
index = int(specifier[1]) - 1

if specifier[0] == 'R':
return field[index]

elif specifier[0] == 'C':
return map(lambda s: s[index], field)

elif specifier[0] == 'F':
i = index / 3
j = index % 3
sub3x3=map(lambda s: s[3*j:3*j+3], field[3*i:3*i+3])
return itertools.chain(*sub3x3)

else:
return scratch

# set the field parts indicated by the specifier string
# to the given data combined with the original data
# using the given function
def set_data(field, scratch, specifier, newvals, combine):
newvals =list(newvals)

if specifier != "S":
index = int(specifier[1]) - 1

if specifier[0] == 'R':
field[index] = map(combine, field[index], newvals)

elif specifier[0] == 'C':
for i in xrange(0,len(field)):
field[i][index] = combine(field[i][index], newvals[i])

elif specifier[0] == 'F':
i = index / 3
j = index % 3
for k in xrange(0,3):
for l in xrange(0,3):
field[3*i+k][3*j+l] = combine(field[3*i+k][3*j+l],
newvals[3*k+l])

else:
for i in xrange(9):
scratch[i] = combine(scratch[i], newvals[i])

# check whether field2 is obtained by making progress on field1
def validate(field1, field2):
for i in xrange(0,9):
for j in xrange(0,9):
if field1[i][j] & field2[i][j] != field2[i][j]:
print("mismatch: ", i, ", ", j, ": ",
field1[i][j], " -> ", field2[i][j], sep="");
return False
return True

# -------------------------------------------------------------------
# parse Sudoku file
# -------------------------------------------------------------------

# parse a single character from the Sudoku field
def parse_sudoku_char(char, allowdot):
if char.isdigit():
return 1 << (int(char) - 1)
elif allowdot and char == '.':
return 511
else:
error("Invalid character in Sudoku field:", char)
sys.exit(1)

# parse a line of the Sudoku field
def parse_sudoku_line(line, allowdot):
if len(line) != 9:
error("Sudoku field: Line too long")
sys.exit(1)
return map(lambda c: parse_sudoku_char(c, allowdot), line)

# parse a complete Sudoku field
def parse_sudoku_field(field, allowdot):
return map(lambda r:parse_sudoku_line(r, allowdot), field)

# parse the complete Sudoku input file

# The file contains two Sudoku fields of 9 lines each,
# separated by an empty line
if len(sudoku_text) != 19 or sudoku_text[9] != "":
error(sys.argv[1], ": file must consist of two Sudoku boards")
error("separated by an empty line")
sys.exit(1)

unsolved_field = parse_sudoku_field(sudoku_text[0:9], True)
solved_field = parse_sudoku_field(sudoku_text[10:19], False)

if not validate(unsolved_field, solved_field):
error("The given solution does not solve the given Sudoku")
sys.exit(1)

return (unsolved_field, solved_field)

# -------------------------------------------------------------------
# check the field and run the solver
# -------------------------------------------------------------------

# test is a specifier is valid
def test_specifier(specifier):
if len(specifier) < 1 or len(specifier) > 2:
return False
if specifier[0] not in "RCFS":
return False
if specifier[0] == "S":
return len(specifier) == 1
return specifier[1].isdigit() and specifier[1] != '0'

# pass data through the solver
# returns one of "continue", "finished" and "disqualified"

CONTINUE     = "continue"
FINISHED     = "finished"
DISQUALIFIED = "disqualified"

def step(field, scratch, specs, solvercommand):
speclist = specs[0]
speclength = len(speclist)

solver = subprocess.Popen(solvercommand,
stdin=subprocess.PIPE,
stdout=subprocess.PIPE)
print(*speclist, file=solver.stdin)
for spec in speclist:
print(*get_data(field, scratch, spec), file=solver.stdin)
solver.stdin.close()

if len(output) != speclength+1:
return DISQUALIFIED
if not testall(lambda line: re.match(r'^(\d+\s+)+\d+\$', line),
output[:speclength]):
return DISQUALIFIED

replacement_data = map(lambda line: map(int, line.split()),
output[:speclength])

def row_valid(row):
return len(row) == 9 and testall(lambda num: 0 <= num < 2**9, row)

if not testall(lambda row: row_valid(row), replacement_data):
return DISQUALIFIED

tmpfield = constfield(511)
tmpscratch = [511]*9

for index in xrange(speclength):
set_data(tmpfield, tmpscratch,
speclist[index], replacement_data[index],
lambda x, y: x & y)

for index in xrange(speclength):
set_data(field, scratch, speclist[index],
get_data(tmpfield, tmpscratch, speclist[index]),
lambda x, y: y);

action = output[len(speclist)]
if (action == "STOP"):
return FINISHED
speclist = action.split()
specs[0] = speclist

if len(speclist) not in range(1,4):
return DISQUALIFIED
if not testall(test_specifier, speclist):
return DISQUALIFIED
return CONTINUE

# The actual runloop and scoring

def runloop(command, unsolved_field, solved_field):
# the working field is the field the process is actually operating on
working_field = copy.deepcopy(unsolved_field)

# The scratch data
scratch = [0]*9

# The list of specifiers for the data to provide
# Initially, that's just the scratch space
# Additional list level to provide reference semantics
specs = [[ "S" ]]

steps = 0;
action = CONTINUE;
while action == CONTINUE:
steps = steps + 1
action = step(working_field, scratch, specs, command)

print("Number of runs:", steps);

if action == DISQUALIFIED:
return None

print("checking with puzzle ... ", end="");
if not validate(unsolved_field, working_field):
return None
print("Ok.");

print("checking with solution ... ", end="");
if not validate(working_field, solved_field):
return None
print("Ok.");

onebits = 0;
for num in itertools.chain(*working_field):
onebits = onebits + bin(num).count('1')

print("Number of set bits:", onebits);

return steps + 5* onebits - 45

# -------------------------------------------------------------------
# main program
# -------------------------------------------------------------------

# Check command line arguments
if len(sys.argv) < 3:
error("Usage: ", sys.argv[0], "sudoku solver [solver-args]")
error("  sudoku      = file containing the sudoku to solve")
error("  solver      = executable that should solve it")
error("  solver-args = arguments to be passed to the solver")
sys.exit(2)

score = runloop(sys.argv[2:], *fields)

if (score):
print("Total score: ", score)
else:
print("Disqualified.")


That was quite a lot of code, so I don't think I'll cover all of it, but lets start from the top:

• Add from __future__ import division – Just to make sure that your integer divisions doesn't produce a float here and there
• Comments are supposed to be """docstrings""" – You have seemingly good comments, but they should be docstrings on the first line after the function definitions instead of hash-comments in front
• Use list comprehension instead of map for trim_lines – List comprehension tends to be easier to read and maintain. Read accepted answer on Python List Comprehension vs. Map, and see code suggestion below:

def trim_lines2(texts):
"Remove leading and trailing whitespace from all lines."

return [text.strip() for text in texts]

• _In arrayprint(): Simplify print calls, if possible – Even though only one line, it is really hard to read. Here are two variants, where I think I prefer the last one:

def arrayprint_v3(array, width):
row_length = len(array[0])
col_format = '{{:>{}}}'.format(width)
for row in array:
print((col_format*row_length).format(*row))

def arrayprint_v3(array, width):
row_length = len(array[0])

for row in array:
print ''.join('{0:>{1}}'.format(col, width) for col in row)

• Use with ... for reading files – See http://www.dotnetperls.com/file-python, which explains why it is better to use with ... instead of ordinary try...except when reading files

• What the duplicate in testall? – I'm not sure I understand what's happening in your testall as you seem to confuscate the original reduce(map(...)) with an extra lambda call?!? Can surely be more readable, and most likely a lot shorter... Shorter version all(map(predicate, list))
• Try out the divmod() function – Try the following on for size: div, mod = divmod(k-1, 3)
• Switch to a one-dimensional sudoku array, using index function – You have loads of double loops, and double indexing and inplace calculation to address a given sudoku field. This could be simplified greatly if you switch to a one-dimensional array, and having a function doing transforming from 2D to 1D. The logic is a little bit to confusing, so I might be wrong, but here is some code trying to illustrating simplifications which should be available:

# Replace
i = index / 3
j = index % 3
for k in xrange(0,3):
for l in xrange(0,3):
field[3*i+k][3*j+l] = combine(field[3*i+k][3*j+l],
newvals[3*k+l])
# with something like
for i in xrange(9):
field[index][i] = combine(field[index][i], newvals[i])

# optionally use some variatons over
i, j = divmod(index, 3)

def pos(x, y):
return 3*x + y

• You are overly fond of for i in xrange, followed by list indexing – Your code would look neater if either you used for row in rows, or even for i, row in enumerate(rows). Then you could access row directly, and if you need to cross reference you could use the i in the latter option. Also remember that xrange(0, 9) is the same as xrange(9)

• ... me is exhausted trying to get through the code ...

## Final note

Even though you have good variable names and function names, and some good vertical spacing (except not haveing two newlines before a function), your code is hard to read, and difficult to understand.

This in some part due to heavy use of lambdas and maps, combined with the complicated for loops. I do believe there is much room for improvement through simplifying list structures, and finding the more pythonic ways of doing things instead of repeating the habits of your older coding language.

• About being "overly fond of" for i in xrange: No, I'm not. It's just that I didn't know an alternative. I didn't know enumerate, and while reading up on that, now I also found zip. Accessing corresponding elements of two arrays is one of the main reasons I used indices; zip handles that nicely. A second reason is that I need indices to update the arrays, as otherwise I'll only modify copies. I've now decided to change set_data to return the updated field instead of updating in place; that together with zip should reduce the number of index uses dramatically. – celtschk Oct 12 '15 at 18:15
• @celtschk, sounds good. Good luck with changes, and welcome back with a new and improved versions here as a new question here at Code Review! Then you might get even better reviews as you've already improved parts of it, and we can clearer see what is actually happening under the hood. – holroy Oct 12 '15 at 18:19
• Thank you, also for the rest of the review; I learned a lot from your comments. – celtschk Oct 12 '15 at 18:52

raise errors

You do not need the following function:

# print on stderr
def error(*content):
print(*content, file=sys.stderr)


The recommended way to signal an error is:

raise AppropriateException("Message text...")


This also makes sys.exit(1) unecessary as raise exits automatically.

Be specific with except

Another line I would like you to avoid is: except:, remember to avoid excepting anything, and specify the wanted exception.

arrayprint with string * integer

I also wrote yet another arrayprint function that makes use of built-in string by integer multiplication that I think is the easiest to read:

def arrayprint(array, width):
delimiter = ' ' * width
for row in array:
print(delimiter.join(str(i) for i in row))


repeated / unused code

You have:

def subfield(field, k):
i = (k-1) / 3
j = (k-1) % 3
sub3x3=map(lambda s: s[3*i:3*i+3],field[3*j:3*j+3])
return itertools.chain(*sub3x3)


And then:

    i = index / 3
j = index % 3
sub3x3=map(lambda s: s[3*j:3*j+3], field[3*i:3*i+3])
return itertools.chain(*sub3x3)


So most probably you wrote the sub-function and forgot to actually use it.

Avoid obscure bitshifting

You use &, from the docs:

x & y Does a "bitwise and". Each bit of the output is 1 if the corresponding bit of x AND of y is 1, otherwise it's 0.

If you are just interested in the logic aspect of this, use and, it is much easier to read.

The same goes for:

1 <<


Just use the appropriate power syntax, as that 0.0001 seconds gain is not worth the puzzling feeling that reading this gives.

Use constants

The commands for the controller are: "RCFS", but you repeat them in at least two places, I would define a constant:

COMMANDS = "RCFS"


And then:

if specifier != COMMANDS[0]:
index = int(specifier[1]) - 1

if specifier[0] == COMMANDS[1]:
field[index] = map(combine, field[index], newvals)

elif specifier[0] == COMMANDS[2]:
for i in xrange(0,len(field)):
field[i][index] = combine(field[i][index], newvals[i])


This way changing the commands just involves modifying one place.

Avoid 511 (and magic numbers in general)

A magic number is a number that pops up in the code many times with no explanation as to why it has that value and is not obvious by the context.

511 is repeated 3 times in your code, and I have absolutely no idea what its meaning is, so put this number in a constant to help future readers.

Use built-ins

As @holroy rightfully noted that you had overlooked the all built-in, I note that you have overlooked the sum built-in:

onebits = 0; # <- minor: remove all semicolons, they are never used in Python.
for num in itertools.chain(*working_field):
onebits = onebits + bin(num).count('1')


Becomes:

onebits = sum(bin(num).count('1') for num in itertools.chain(*working_field))


I think the latter is less verbose and more readable (if the line is too long for your taste, just add a newline before the for statement or alias flatten = itertools.chain`)