# How to make this faster

Joshua Landau joshua.landau.ws at gmail.com
Sat Jul 6 03:45:47 CEST 2013

```On 5 July 2013 17:25, MRAB <python at mrabarnett.plus.com> wrote:
> For comparison, here's my solution:
<CODE>

Unfortunately, there are some sudokus that require guessing - your
algorithm will not solve those. A combination algorithm would be best,
AFAIK.

-----

FWIW, this is my interpretation of the original algorithm:

from collections import defaultdict
from io import StringIO

# For printing
DONE = defaultdict(lambda: " ")

# How many different numbers can go in each slot, indexes are of the
form: [position]
NUM_POSSIBILITIES = defaultdict(lambda: 9)

# How many times each value has been removed from the possibilities,
# indexes are of the form: [value, position]
TIMES_REMOVED = defaultdict(lambda: 0)

# Set of empty spaces in the grid
REMAINING = {(i,j) for i in range(9) for j in range(9)}

# Cache, would normally be done inline
PLACES_TO_REMOVE = {}
for row in range(9):
for column in range(9):
square_top, square_left = 3*(row // 3), 3*(column // 3)

# Across the row
PLACES_TO_REMOVE[row, column]  = {(p_row, column) for p_row in range(9)}

# Across the collumn
PLACES_TO_REMOVE[row, column] |= {(row, p_collumn) for
p_collumn in range(9)}

# Inside the square
PLACES_TO_REMOVE[row, column] |= {
(p_row, p_collumn)
for p_row     in range(square_top,  3+square_top)
for p_collumn in range(square_left, 3+square_left)
}

"""Add value to the position, updating needed globals"""

DONE[position] = value

# Use "REMAINING &" so that we only change places we care about
# It's reversed in a consistent order to allow this
for add_pos in REMAINING & PLACES_TO_REMOVE[position]:

# Remove possibility if it hasn't already been removed

REMAINING.remove(position)

def remove_at(value, position):

# Use "REMAINING &" so that we only change places we care about
# It's reversed in a consistent order to allow this
for remove_pos in REMAINING & PLACES_TO_REMOVE[position]:
TIMES_REMOVED[value, remove_pos] -= 1

# Add posibility back if TIMES_REMOVED falls to 0
if not TIMES_REMOVED[value, remove_pos]:
NUM_POSSIBILITIES[remove_pos] += 1

del DONE[position]

number_remaining = 81

# StringIO iterates over lines
lines = (line.strip() for line in StringIO(input))
lines = (line for line in lines if line and not line.startswith("#"))

for row, line in enumerate(lines):
line = line.strip().replace(" ", "").replace("\t", "")

for column, character in enumerate(line):
if character == "_":
pass

elif character.isdigit():
number_remaining -= 1

else:
raise ValueError("Invalid character {} in input line
{}".format(character, line))

return number_remaining

def print_grid(highlight=None):
row_seperator     = "¦   ·   ·   ¦   ·   ·   ¦   ·   ·   ¦"
special_seperator = "·-----------·-----------·-----------·"
seperators = "  ¦  ¦  ¦"

row_seperators = [special_seperator, row_seperator, row_seperator] * 3

for row, row_seperator in enumerate(row_seperators):
print(row_seperator)

print("¦", end=" ")

for column, seperator in enumerate(seperators):
if (row, column) == highlight:
# These are colors, ignore 'em if you wish
# This is to let you see changes when debugging
print("\x1b[31;01m{}\x1b[39;49;00m".format(DONE[row,
column]), seperator, end=" ")

else:
print(DONE[row, column], seperator, end=" ")

print()

print(special_seperator)
print()

def solve(number_remaining):
if not number_remaining:
return True

# We need to guess -- go for the one where we have the least choice
position = min(REMAINING, key=NUM_POSSIBILITIES.__getitem__)

for value in range(1, 10):
if not TIMES_REMOVED[value, position]:

if solve(number_remaining-1):
return True

remove_at(value, position)

return False

problem = """
_ _ _  _ _ _  _ _ _
_ _ _  _ _ 3  _ 8 5
_ _ 1  _ 2 _  _ _ _

_ _ _  5 _ 7  _ _ _
_ _ 4  _ _ _  1 _ _
_ 9 _  _ _ _  _ _ _

5 _ _  _ _ _  _ 7 3
_ _ 2  _ 1 _  _ _ _
_ _ _  _ 4 _  _ _ 9
"""