Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #50037
| References | <b3ne2rFojnkU1@mid.dfncis.de> <b3nmtfFojnkU3@mid.dfncis.de> <b3o6bkFtc39U4@mid.dfncis.de> <51D6F392.2070301@mrabarnett.plus.com> |
|---|---|
| From | Joshua Landau <joshua.landau.ws@gmail.com> |
| Date | 2013-07-06 02:45 +0100 |
| Subject | Re: How to make this faster |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.4321.1373075195.3114.python-list@python.org> (permalink) |
On 5 July 2013 17:25, MRAB <python@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)
}
def add_at(value, position):
"""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
if not TIMES_REMOVED[value, add_pos]:
NUM_POSSIBILITIES[add_pos] -= 1
TIMES_REMOVED[value, add_pos] += 1
REMAINING.remove(position)
def remove_at(value, position):
"""The inverse of add_at"""
REMAINING.add(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]
def read_sudoku(input):
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():
add_at(int(character), (row, column))
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]:
add_at(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
"""
solve(read_sudoku(problem))
print_grid()
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 08:22 +0000
Re: How to make this faster Fábio Santos <fabiosantosart@gmail.com> - 2013-07-05 10:38 +0100
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 10:07 +0000
Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 11:13 +0100
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 10:53 +0000
Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-05 12:02 +0000
Re: How to make this faster Fábio Santos <fabiosantosart@gmail.com> - 2013-07-05 13:44 +0100
Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 14:41 +0100
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 14:28 +0000
Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 15:45 +0100
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 14:48 +0000
Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 16:26 +0100
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 14:54 +0000
Re: How to make this faster Fábio Santos <fabiosantosart@gmail.com> - 2013-07-05 16:18 +0100
Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-05 16:24 +0000
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 15:17 +0000
Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 16:38 +0100
Re: How to make this faster MRAB <python@mrabarnett.plus.com> - 2013-07-05 17:25 +0100
Re: How to make this faster Joshua Landau <joshua.landau.ws@gmail.com> - 2013-07-06 02:45 +0100
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 15:47 +0000
Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-05 16:52 +0000
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 16:07 +0000
Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-05 16:50 +0000
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 18:39 +0000
Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-06 03:05 +0000
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-06 07:25 +0000
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 18:42 +0000
csiph-web