Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <51D6F392.2070301@mrabarnett.plus.com>
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: Sat, 6 Jul 2013 02:45:47 +0100
Subject: Re: How to make this faster
To: python-list <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.4321.1373075195.3114.python-list@python.org>
Lines: 177
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:50037

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 =3D defaultdict(lambda: " ")

# How many different numbers can go in each slot, indexes are of the
form: [position]
NUM_POSSIBILITIES =3D defaultdict(lambda: 9)

# How many times each value has been removed from the possibilities,
# indexes are of the form: [value, position]
TIMES_REMOVED =3D defaultdict(lambda: 0)

# Set of empty spaces in the grid
REMAINING =3D {(i,j) for i in range(9) for j in range(9)}

# Cache, would normally be done inline
PLACES_TO_REMOVE =3D {}
for row in range(9):
    for column in range(9):
        square_top, square_left =3D 3*(row // 3), 3*(column // 3)

        # Across the row
        PLACES_TO_REMOVE[row, column]  =3D {(p_row, column) for p_row in ra=
nge(9)}

        # Across the collumn
        PLACES_TO_REMOVE[row, column] |=3D {(row, p_collumn) for
p_collumn in range(9)}

        # Inside the square
        PLACES_TO_REMOVE[row, column] |=3D {
            (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] =3D 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] -=3D 1

        TIMES_REMOVED[value, add_pos] +=3D 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] -=3D 1

        # Add posibility back if TIMES_REMOVED falls to 0
        if not TIMES_REMOVED[value, remove_pos]:
            NUM_POSSIBILITIES[remove_pos] +=3D 1

    del DONE[position]


def read_sudoku(input):
    number_remaining =3D 81

    # StringIO iterates over lines
    lines =3D (line.strip() for line in StringIO(input))
    lines =3D (line for line in lines if line and not line.startswith("#"))

    for row, line in enumerate(lines):
        line =3D line.strip().replace(" ", "").replace("\t", "")

        for column, character in enumerate(line):
            if character =3D=3D "_":
                pass

            elif character.isdigit():
                add_at(int(character), (row, column))
                number_remaining -=3D 1

            else:
                raise ValueError("Invalid character {} in input line
{}".format(character, line))

    return number_remaining


def print_grid(highlight=3DNone):
    row_seperator     =3D "=C2=A6   =C2=B7   =C2=B7   =C2=A6   =C2=B7   =C2=
=B7   =C2=A6   =C2=B7   =C2=B7   =C2=A6"
    special_seperator =3D "=C2=B7-----------=C2=B7-----------=C2=B7--------=
---=C2=B7"
    seperators =3D "  =C2=A6  =C2=A6  =C2=A6"

    row_seperators =3D [special_seperator, row_seperator, row_seperator] * =
3

    for row, row_seperator in enumerate(row_seperators):
        print(row_seperator)

        print("=C2=A6", end=3D" ")

        for column, seperator in enumerate(seperators):
            if (row, column) =3D=3D 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=3D" ")

            else:
                print(DONE[row, column], seperator, end=3D" ")

        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 =3D min(REMAINING, key=3DNUM_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 =3D """
    _ _ _  _ _ _  _ _ _
    _ _ _  _ _ 3  _ 8 5
    _ _ 1  _ 2 _  _ _ _

    _ _ _  5 _ 7  _ _ _
    _ _ 4  _ _ _  1 _ _
    _ 9 _  _ _ _  _ _ _

    5 _ _  _ _ _  _ 7 3
    _ _ 2  _ 1 _  _ _ _
    _ _ _  _ 4 _  _ _ 9
"""

solve(read_sudoku(problem))
print_grid()