# November's Code Share: Solving Problems

• Nov 2, 2011 · 6:30 PM

Solving Problems

The theme for November's Code Share is Solving Problems.  The programmers job is to solve problems with code.

Problem solving in fact is a universal endeavour.  We just happen to be different because we use computers to solve the problems we deal with.

Why do we write code?  To solve problems.  The best code is the code that solves the most important problems.

I looked into some of the recent books that describe design patterns, assuming that they would address recurring code designs for real-world phenomenon. Some of the patterns do,like the controller pattern, but too many others, such as the factory pattern,address problems that are created by the programming language itself.

Leo Brodie in the preface to Thinking Forth (2004)

We need to be careful, because sometimes we inadvertently create new ones.  Those that follow us can spend more time solving the problems we created rather than moving forward the solutions we provided.

We do pay a great deal of of attention to techniques that are essentially syntactic and notational.  That leaves us... paying to little attention to the incalculable complexity of the real world.  Our problems and requirements are in the world, not in the computer.  We must focus on them directly, and describe them conscientiously.

Michael Jackson in Problem Frames (2001)

When we read code we need to ask ourselves some important questions:

• What problem is being solved?  How important is the problem being solved?
• How effectively is the problem reflected in the code?  Does the code show the concerns that need to be addressed to deliver results in the real world?
• How clear does the code make the technical solution?  Does it bury the important aspects of the design below layers of abstraction?

November challange: Solving Soduku

The complexity of the Soduku puzzle is not incalculable, but the creation of soduku solvers has much to teach us.

One again we are going to use a python solution by Peter Norvig as a starting point:

```## Solve Every Sudoku Puzzle

## See http://norvig.com/sudoku.html

## Throughout this program we have:
##   r is a row,    e.g. 'A'
##   c is a column, e.g. '3'
##   s is a square, e.g. 'A3'
##   d is a digit,  e.g. '9'
##   u is a unit,   e.g. ['A1','B1','C1','D1','E1','F1','G1','H1','I1']
##   grid is a grid,e.g. 81 non-blank chars, e.g. starting with '.18...7...
##   values is a dict of possible values, e.g. {'A1':'12349', 'A2':'8', ...}

def cross(A, B):
"Cross product of elements in A and elements in B."
return [a+b for a in A for b in B]

rows     = 'ABCDEFGHI'
cols     = digits
squares  = cross(rows, cols)
unitlist = ([cross(rows, c) for c in cols] +
[cross(r, cols) for r in rows] +
[cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])
units = dict((s, [u for u in unitlist if s in u])
for s in squares)
peers = dict((s, set(sum(units[s],[]))-set([s]))
for s in squares)

################ Unit Tests ################

def test():
"A set of tests that must pass."
assert len(squares) == 81
assert len(unitlist) == 27
assert all(len(units[s]) == 3 for s in squares)
assert all(len(peers[s]) == 20 for s in squares)
assert units['C2'] == [['A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2'],
['C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'],
['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3']]
assert peers['C2'] == set(['A2', 'B2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2',
'C1', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9',
'A1', 'A3', 'B1', 'B3'])
print 'All tests pass.'

################ Parse a Grid ################

def parse_grid(grid):
"""Convert grid to a dict of possible values, {square: digits}, or
return False if a contradiction is detected."""
## To start, every square can be any digit; then assign values from the grid.
values = dict((s, digits) for s in squares)
for s,d in grid_values(grid).items():
if d in digits and not assign(values, s, d):
return False ## (Fail if we can't assign d to square s.)
return values

def grid_values(grid):
"Convert grid into a dict of {square: char} with '0' or '.' for empties."
chars = [c for c in grid if c in digits or c in '0.']
assert len(chars) == 81
return dict(zip(squares, chars))

################ Constraint Propagation ################

def assign(values, s, d):
"""Eliminate all the other values (except d) from values[s] and propagate.
Return values, except return False if a contradiction is detected."""
other_values = values[s].replace(d, '')
if all(eliminate(values, s, d2) for d2 in other_values):
return values
else:
return False

def eliminate(values, s, d):
"""Eliminate d from values[s]; propagate when values or places <= 2.
Return values, except return False if a contradiction is detected."""
if d not in values[s]:
values[s] = values[s].replace(d,'')
## (1) If a square s is reduced to one value d2, then eliminate d2 from the peers.
if len(values[s]) == 0:
return False ## Contradiction: removed last value
elif len(values[s]) == 1:
d2 = values[s]
if not all(eliminate(values, s2, d2) for s2 in peers[s]):
return False
## (2) If a unit u is reduced to only one place for a value d, then put it there.
for u in units[s]:
dplaces = [s for s in u if d in values[s]]
if len(dplaces) == 0:
return False ## Contradiction: no place for this value
elif len(dplaces) == 1:
# d can only be in one place in unit; assign it there
if not assign(values, dplaces[0], d):
return False
return values

################ Display as 2-D grid ################

def display(values):
"Display these values as a 2-D grid."
width = 1+max(len(values[s]) for s in squares)
line = '+'.join(['-'*(width*3)]*3)
for r in rows:
print ''.join(values[r+c].center(width)+('|' if c in '36' else '')
for c in cols)
if r in 'CF': print line
print

################ Search ################

def solve(grid): return search(parse_grid(grid))

def search(values):
"Using depth-first search and propagation, try all possible values."
if values is False:
return False ## Failed earlier
if all(len(values[s]) == 1 for s in squares):
return values ## Solved!
## Chose the unfilled square s with the fewest possibilities
n,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
return some(search(assign(values.copy(), s, d))
for d in values[s])

################ Utilities ################

def some(seq):
"Return some element of seq that is true."
for e in seq:
if e: return e
return False

def from_file(filename, sep='\n'):
"Parse a file into a list of strings, separated by sep."

def shuffled(seq):
"Return a randomly shuffled copy of the input sequence."
seq = list(seq)
random.shuffle(seq)
return seq

################ System test ################

import time, random

def solve_all(grids, name='', showif=0.0):
"""Attempt to solve a sequence of grids. Report results.
When showif is a number of seconds, display puzzles that take longer.
When showif is None, don't display any puzzles."""
def time_solve(grid):
start = time.clock()
values = solve(grid)
t = time.clock()-start
## Display puzzles that take long enough
if showif is not None and t > showif:
display(grid_values(grid))
if values: display(values)
print '(%.2f seconds)\n' % t
return (t, solved(values))
times, results = zip(*[time_solve(grid) for grid in grids])
N = len(grids)
if N > 1:
print "Solved %d of %d %s puzzles (avg %.2f secs (%d Hz), max %.2f secs)." % (
sum(results), N, name, sum(times)/N, N/sum(times), max(times))

def solved(values):
"A puzzle is solved if each unit is a permutation of the digits 1 to 9."
def unitsolved(unit): return set(values[s] for s in unit) == set(digits)
return values is not False and all(unitsolved(unit) for unit in unitlist)

def random_puzzle(N=17):
"""Make a random puzzle with N or more assignments. Restart on contradictions.
Note the resulting puzzle is not guaranteed to be solvable, but empirically
about 99.8% of them are solvable. Some have multiple solutions."""
values = dict((s, digits) for s in squares)
for s in shuffled(squares):
if not assign(values, s, random.choice(values[s])):
break
ds = [values[s] for s in squares if len(values[s]) == 1]
if len(ds) >= N and len(set(ds)) >= 8:
return ''.join(values[s] if len(values[s])==1 else '.' for s in squares)
return random_puzzle(N) ## Give up and make a new puzzle

grid1  = '003020600900305001001806400008102900700000008006708200002609500800203009005010300'
grid2  = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
hard1  = '.....6....59.....82....8....45........3........6..3.54...325..6..................'

if __name__ == '__main__':
test()
solve_all(from_file("easy50.txt", '========'), "easy", None)
solve_all(from_file("top95.txt"), "hard", None)
solve_all(from_file("hardest.txt"), "hardest", None)
solve_all([random_puzzle() for _ in range(99)], "random", 100.0)

## References used:
## http://www.scanraid.com/BasicStrategies.htm
## http://www.sudokudragon.com/sudokustrategy.htm
## http://www2.warwick.ac.uk/fac/sci/moac/currentstudents/peter_cock/python/sudoku/
```

Please have a go at creating your own soduku solver. Whatever you do, though, don't just translate the above code into another language. Take the time to understand the problem and possible solutions, then express your own solution in code as elegantly as you can.

What's Going To Happen?

On Monday 31st October, a couple of days before the share, we'll send out an email to everybody who has signed up.  If you have any code to contribute please send it in a reply to that email.

On Wednesday 2nd November, the Code Share itself, we will all have a couple of short presentations.  This will be followed by breaking out into groups to cast a critical eye over the code for some solutions.  We will print these out, so you won't have to bring a laptop.  Afterwards we will come back together as a group to discuss what we have learned.

After the event we will be heading to the Half Moon, [masked] Mile End Road, Mile End, Greater London, E1 4AA - http://www.jdwetherspoon.co.uk/home/pubs/the-half-moon - for drinks/networking.

ThoughtWorks are delighted to be sponsors of the November Code Share!

This is a joint event with the Graduate Developer Group - http://www.meetup.com/grad-dc/events/38473732/ - providing an opportunity for both experienced developers and newcomers to the profession to share points of view.

• ##### Anji C.

November 10, 2011

• ##### Maris O.

I look forward to see "more readable" version of sudoku solver and my clojure code refactored!

November 3, 2011

• ##### Dave S.

Thanks to Maris for his solutions!
Next month in addition to December's topic (programming language quirks) Jose has promised us a "readable" suduku solver and Ged will see how he can transform Maris's clojure example to address Jose's comments about LISP's readability.

November 3, 2011

• ##### Maris O.

October 31, 2011

• ##### Anji C.

Twitter tag for this event is #ljcjug

October 25, 2011

### 12 went

• ##### Marc T.
• A former member
• A former member

### London, United Kingdom

Founded Nov 26, 2007

#### Organizers:

• ##### Our Blog

Read the latest news from the LJC

• ##### RecWorks Ltd

Fixing Tech Recruitment using the Power of Community

• ##### jClarity

Java/JVM Performance Analysis Tools & mentoring for Java related matters

• ##### LJC Aggrity

Our LJC Aggrity site contains blog posts from our members

• ##### LJC Book Club

Our Book club with book reviews from our members

• ##### Devoxx UK

Java Community Conference in collaboration with the LJC, 8-10th June 16

• ##### SkillsMatter

"Host, help organise, promote, film many of our meetings."

• ##### IBM

Build Enterprise-grade apps at start-up speed.

• ##### New Relic

New Relic makes sense of billions of metrics a day in real time.

• ##### Hazelcast

Hazelcast is the leader in operating in-memory computing.

• ##### Java.Net

We are an official Java User Group recognised by Oracle's JUG program

• ##### O'Reilly

40% discount on printed books and 50% on e-books.

#### People in this Meetup are also in:

• ##### London OpenCoffee Meetup

10,262 Entrepreneurs

• ##### London Dev Community

1,790 Developer, Manager, Architect

• ##### Swift London | A Language Appreciation Society

3,021 Swift Londoners

• ##### OpenSource & Agile Community Events

4,623 OpenSource and Agile developers

858 Members

• ##### London μServices (Microservices)­ User Group

2,274 μServicers