Ускорьте решение Sudoku

Я сделал этот решатель Судоку, используя поиск по глубине, для решения любого простого решения (без угадывания) требуется менее 0,1 секунды, но если решение требует угадывания (при использовании DFS), его время растет экспоненциально.

Одна головоломка («жесткая») делает 10 последовательных ветвей в поиске, что позволяет 2 10 (я думаю) возможные результаты. Это головоломка занимает около 40 секунд.

 HARD - 3 RUNS
Total: 114.4 seconds
  Mean: 38.13433 seconds
  Max: 38.67300 seconds
  Min: 37.74700 seconds

get_missing_values()
  Called: 475437 times per run(1426311 total)
  Running for 87.362s(in 3 runs) / 29.12073s per run
create_cells()
  Called: 47700 times per run(143100 total)
  Running for 19.419s(in 3 runs) / 6.47302s per run
get_next_moves()
  Called: 47700 times per run(143100 total)
  Running for 6.117s(in 3 runs) / 2.03890s per run
depth_first_search()
  Called: 1 times per run(3 total)
  Running for 0.856s(in 3 runs) / 0.28532s per run
possible_moves()
  Called: 47700 times per run(143100 total)
  Running for 0.647s(in 3 runs) / 0.21570s per run
main()
  Called: 1 times per run(1 total)
  Running for 0.056s(in 3 runs) / 0.01876s per run
win()
  Called: 1 times per run(3 total)
  Running for 0.000s(in 3 runs) / 0.00002s per run

Как вы можете видеть, источником самой «работы» является метод get_missing_values из класса Cell, что занимает 76% всей рабочей нагрузки. Этот метод ищет каждую ячейку в сетке и сравнивает ее с остальными, чтобы получить возможные значения. Я пытался сжать его как можно больше, используя несколько if -conditions, но он по-прежнему требует много работы.

 import functools
import time

DEBUGGER_TIMER = {}


def timeit(func):
    @functools.wraps(func)
    def wrapper(*args, **kwargs):
        t_start = time.clock()
        ret = func(*args, **kwargs)
        t_end = time.clock() - t_start
        function_name = func.__name__
        if function_name in DEBUGGER_TIMER:
            DEBUGGER_TIMER[function_name][0] += t_end
            DEBUGGER_TIMER[function_name][1] += 1
        else:
            DEBUGGER_TIMER[function_name] = [t_end, 1]
        return ret

    return wrapper

# index:(row,column,group,value)
INDEX_TO_VALUE = {0: (0, 0, 0), 1: (0, 1, 0), 2: (0, 2, 0),
                  3: (0, 3, 1), 4: (0, 4, 1), 5: (0, 5, 1),
                  6: (0, 6, 2), 7: (0, 7, 2), 8: (0, 8, 2),
                  9: (1, 0, 0), 10: (1, 1, 0), 11: (1, 2, 0),
                  12: (1, 3, 1), 13: (1, 4, 1), 14: (1, 5, 1),
                  15: (1, 6, 2), 16: (1, 7, 2), 17: (1, 8, 2),
                  18: (2, 0, 0), 19: (2, 1, 0), 20: (2, 2, 0),
                  21: (2, 3, 1), 22: (2, 4, 1), 23: (2, 5, 1),
                  24: (2, 6, 2), 25: (2, 7, 2), 26: (2, 8, 2),
                  27: (3, 0, 3), 28: (3, 1, 3), 29: (3, 2, 3),
                  30: (3, 3, 4), 31: (3, 4, 4), 32: (3, 5, 4),
                  33: (3, 6, 5), 34: (3, 7, 5), 35: (3, 8, 5),
                  36: (4, 0, 3), 37: (4, 1, 3), 38: (4, 2, 3),
                  39: (4, 3, 4), 40: (4, 4, 4), 41: (4, 5, 4),
                  42: (4, 6, 5), 43: (4, 7, 5), 44: (4, 8, 5),
                  45: (5, 0, 3), 46: (5, 1, 3), 47: (5, 2, 3),
                  48: (5, 3, 4), 49: (5, 4, 4), 50: (5, 5, 4),
                  51: (5, 6, 5), 52: (5, 7, 5), 53: (5, 8, 5),
                  54: (6, 0, 6), 55: (6, 1, 6), 56: (6, 2, 6),
                  57: (6, 3, 7), 58: (6, 4, 7), 59: (6, 5, 7),
                  60: (6, 6, 8), 61: (6, 7, 8), 62: (6, 8, 8),
                  63: (7, 0, 6), 64: (7, 1, 6), 65: (7, 2, 6),
                  66: (7, 3, 7), 67: (7, 4, 7), 68: (7, 5, 7),
                  69: (7, 6, 8), 70: (7, 7, 8), 71: (7, 8, 8),
                  72: (8, 0, 6), 73: (8, 1, 6), 74: (8, 2, 6),
                  75: (8, 3, 7), 76: (8, 4, 7), 77: (8, 5, 7),
                  78: (8, 6, 8), 79: (8, 7, 8), 80: (8, 8, 8)}


class Cell:
    board = []
    missing_values = set('123456789')

    def __init__(self, row, column, group, value, index):
        self.row = row
        self.column = column
        self.value = value
        self.group = group
        self.index = index
        Cell.board.append(self)

    @timeit
    def get_missing_values(self):
        values = set('.')
        for cell in Cell.board:
            if cell.value not in values:
                if cell.row == self.row:
                    values.add(cell.value)
                elif cell.column == self.column:
                    values.add(cell.value)
                elif cell.group == self.group:
                    values.add(cell.value)
        return Cell.missing_values.difference(values)

@timeit
def create_cells(puzzle):
    for index, value in enumerate(puzzle):
        row, column, group = INDEX_TO_VALUE[index]
        Cell(row, column, group, value, index)


@timeit
def get_next_moves():
    try:
        moves = {}
        for cell in Cell.board:
            if cell.value == '.':
                missing_values = cell.get_missing_values()
                moves[cell.index] = missing_values
                if len(missing_values) == 1:
                    return cell.index, moves[cell.index]
        for index in sorted(moves, key=lambda k: len(moves[k])):
            return index, moves[index]
    finally:
        Cell.board = []  # clean-up, just in case


@timeit
def possible_moves(puzzle):
    moves = get_next_moves()
    results = set()
    if moves:
        for move in moves[1]:
            index = moves[0]
            puzzle = puzzle[:index] + move + puzzle[index + 1:]
            results.add(puzzle)
    return results


@timeit
def win(puzzle):
    if "".join(sorted(puzzle)) == '111111111222222222333333333444444444555555555666666666777777777888888888999999999':
        return True
    return False


@timeit
def depth_first_search(graph, start):
    visited, stack = set(), [start]
    solutions = []
    while stack:
        vertex = stack.pop()
        if '.' not in vertex:
            if win(vertex):
                solutions.append(vertex)
                if len(solutions) > 1:
                    raise Exception("More than one solution")
        if vertex not in visited:
            visited.add(vertex)
            create_cells(vertex)
            graph[vertex] = possible_moves(vertex)
            stack.extend(graph[vertex] - visited)
    if solutions:
        return solutions
    else:
        raise Exception("No solution found")

@timeit
def main(min_test_time, min_runs, puzzle):
    easy = "53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79"
    hard = "8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.."

    if puzzle == 'easy':
        test_puzzle = easy
    else:
        test_puzzle = hard

    times = []
    n_runs = 0
    while sum(times) < min_test_time or min_runs > n_runs:
        n_runs += 1
        graph = {test_puzzle: [None]}
        start = time.time()
        result = depth_first_search(graph, graph.keys()[0])
        end = time.time() - start
        if not debug:
            return test_puzzle,result,end
        if end > 0.0:
            times.append(end)
    return times, n_runs

def debugger((times, n_runs)):
    subtracts = {'main': ['depth_first_search'],
                 'depth_first_search': ['create_cells','possible_moves','win'],
                 'possible_moves': ['get_next_moves'],
                 'get_next_moves': ['get_missing_values'],
                 'get_missing_values': [],
                 'create_cells': [],
                 'win': []}
    total_time = sum(times)
    print "%s - %i RUNS"%(puzzle_to_test.upper(),n_runs)
    print "Total: %.1f seconds" % total_time
    if n_runs > 1:
        print "\tMean: %.5f seconds" % (total_time / n_runs)
        print "\tMax: %.5f seconds" % max(times)
        print "\tMin: %.5f seconds\n" % min(times)
    for f_name in DEBUGGER_TIMER:
        f_time = DEBUGGER_TIMER[f_name][0] - sum([DEBUGGER_TIMER[o_name][0] for o_name in subtracts[f_name]])
        DEBUGGER_TIMER[f_name].append(f_time)


    for f_name in sorted(DEBUGGER_TIMER, key=lambda name: DEBUGGER_TIMER[name][2], reverse=True):
        real_time = DEBUGGER_TIMER[f_name][2]
        f_runs = DEBUGGER_TIMER[f_name][1]
        print "%s()\n\t" \
              "Called: %i times per run(%i total)\n\t" \
              "Running for %.3fs(in %i runs) / %.5fs per run" % (
                  f_name, (f_runs + (n_runs - 1)) // n_runs, f_runs, real_time, n_runs, real_time / n_runs)




if __name__ == '__main__':
    puzzle_to_test = 'hard'
    debug = True
    if debug:
        min_test_time = 10  # seconds
        min_runs = 3
        debugger(main(min_test_time,min_runs,puzzle_to_test))
    else:
        puzzle, result,end_time = main(0, 1, puzzle_to_test)
        print "Puzzle: "
        for i, n in enumerate(puzzle,1):
            if i % 9 == 0:
                print n
            else:
                print n,
        print "\nSolution"
        for i,n in enumerate(result[0],1):
            if i%9==0:
                print n
            else:
                print n,
        print "\nTook %.2f seconds"%end_time
11 голосов | спросил f.rodrigues 24 WedEurope/Moscow2014-12-24T03:58:24+03:00Europe/Moscow12bEurope/MoscowWed, 24 Dec 2014 03:58:24 +0300 2014, 03:58:24

2 ответа


5

Во-первых, используйте PyPy.

$ python2 p.py
Total: 29.8 seconds

$ pypy p.py
Total: 5.1 seconds

PyPy на самом деле делает inlining, поэтому значительная часть этого составляет timeit. Удаление его дает

$ pypy p.py
Total: 4.1 seconds

Это уже улучшенный фактор.

Часто PyPy 3 работает быстрее, поэтому попробуйте это. Чтобы сделать это, вы должны

  • измените код print на функции и используйте from __future__ import print_function, чтобы поддерживать совместимость с Python 2 и

  • change debugger использовать def debugger(times, n_runs): и назовите его с помощью debugger(*main(...)).

В среднем он немного быстрее:

$ pypy3 p.py
Total: 4.1 seconds

INDEX_TO_VALUE должен быть кортежем, а не словарем:

INDEX_TO_VALUE = ((0, 0, 0), (0, 1, 0), (0, 2, 0),
                  (0, 3, 1), (0, 4, 1), (0, 5, 1),
                  (0, 6, 2), (0, 7, 2), (0, 8, 2),
                  ...)

Комментарий выше, это плохо

# index:(row,column,group,value)

Интервал немного тесный, но в первую очередь я обеспокоен тем, что есть неправильное количество элементов! Удалите последний.

Кроме того, понимание намного чище:

INDEX_TO_VALUE = tuple((row, col, row//3 + col//3*3) for row in range(9) for col in range(9))

, хотя вы можете сделать функцию, которая поможет:

def group_at(row, col):
    return row // 3 + col // 3 * 3

INDEX_TO_VALUE = tuple((row, col, group_at(row, col)) for row in range(9) for col in range(9))

Ваша функция timeit должна действительно избегать глобальных переменных, используя лексическое определение области. Это поражает меня как хороший компромисс:

debugged = set()

def timeit(func):
    @functools.wraps(func)
    def wrapper(*args, **kwargs):
        t_start = time.clock()
        ret = func(*args, **kwargs)
        t_end = time.clock() - t_start

        wrapper.calls += 1
        wrapper.time += t_end

        return ret

    wrapper.calls = 0
    wrapper.time = 0
    debugged.add(wrapper)
    return wrapper

У вас все еще есть глобальные данные, но вы локализуете его в функции. Для меня это кажется разумной сделкой. Обратите внимание, что debugged и исходный DEBUGGER_TIMER были не константы, поэтому не должно быть в ALL_CAPS.

Другая вещь, которая раздражает меня, - это использование строк для представления платы. Кортежи целых чисел имеют больше смысла и 0 могут заменить ваш .. Строки могут быть пренебрежимо быстрее, но мне кажется, что мне плохо читается.

Вы не используете graph, насколько я могу судить. Просто удалите его.

Вы делаете:

   if vertex not in visited:
        visited.add(vertex)
        ...
        stack.extend(graph[vertex] - visited)

- visited избыточен с помощью if vertex not in visited проверка. Убери это. Кроме того, вам все равно не нужны никакие проверки; стоимость их выполнения превышает выгоду, по крайней мере, после перехода к спискам целых чисел. Возможно, вам потребуется изменить solutions на набор.

Ваш

list(results.add("%s%s%s" % (puzzle[:index], move, puzzle[index + 1:])) for move in moves[1])

немного сумасшедший; просто сделай

for move in moves[1]: results.add("%s%s%s" % (puzzle[:index], move, puzzle[index + 1:]))

Cell.board является глобальным; это действительно плохая идея, так как она разрушает способность использовать это расширяемо (скажем, иметь две платы). Скорее всего, это очень проблематично, потому что вы каждый раз перестраиваете всю сетку; было бы лучше мутировать, когда вы идете и отменяете, когда отступаете. Однако можно улучшить. Я попробовал что-то вроде

@timeit
def get_missing_values(row, column, group, board):
    missing = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    for c_row, c_column, c_group, c_value in board:
        if c_row == row or c_column == column or c_group == group:
            if c_value in missing:
                missing.remove(c_value)

    return missing

@timeit
def create_cells(puzzle):
    taken = []
    untaken = []

    for index, value in enumerate(puzzle):
        row, column, group = INDEX_TO_VALUE[index]
        if value:
            taken.append((row, column, group, value))
        else:
            untaken.append((row, column, group))

    return taken, untaken

@timeit
def get_next_moves(puzzle):
    taken, untaken = create_cells(puzzle)
    other_option = None
    len_option = 9

    for row, column, group in untaken:
        missing_values = get_missing_values(row, column, group, taken)

        if len(missing_values) == 1:
            return 9*row+column, missing_values

        elif len(missing_values) < len_option:
            len_option = len(missing_values)
            other_option = 9*row+column, missing_values

    return other_option

Это избавляет класс от удобства (кортежи здесь проще). get_next_moves теперь генерирует плату и передает ее на get_missing_values. Это улучшает время:

$ python3 p.py
HARD - 3 RUNS
Total: 19.8 seconds

$ python2 p.py
HARD - 3 RUNS
Total: 12.7 seconds

$ pypy3 p.py
HARD - 3 RUNS
Total: 2.3 seconds

$ pypy p.py
HARD - 3 RUNS
Total: 2.3 seconds

Но get_missing_values ожидается, что все еще занимает большинство времени. Использование набора вместо списка ускоряет CPython, но замедляет PyPy.

Это предполагает, что усилия должны быть направлены исключительно на более эффективное представление для этого. Вот одна идея:

@timeit
def create_cells(puzzle):
    rows = [set() for _ in range(9)]
    columns = [set() for _ in range(9)]
    groups = [set() for _ in range(9)]
    untaken = []

    for index, value in enumerate(puzzle):
        row, column, group = INDEX_TO_VALUE[index]
        if value:
            rows[row].add(value)
            columns[column].add(value)
            groups[group].add(value)
        else:
            untaken.append((row, column, group))

    return rows, columns, groups, untaken

@timeit
def get_next_moves(puzzle):
    rows, columns, groups, untaken = create_cells(puzzle)
    other_option = None
    len_option = 9

    for row, column, group in untaken:
        missing_values = {1, 2, 3, 4, 5, 6, 7, 8, 9} - rows[row] - columns[column] - groups[group]

        if len(missing_values) == 1:
            return 9*row+column, missing_values

        elif len(missing_values) < len_option:
            len_option = len(missing_values)
            other_option = 9*row+column, missing_values

    return other_option

Это дает после отключения timeit,

$ python3 p.py
Total: 8.1 seconds

$ python2 p.py
Total: 6.7 seconds

$ pypy3 p.py
Total: 2.0 seconds

$ pypy p.py   
Total: 2.0 seconds

, который является мощным стимулом для CPython.

Так получилось, что get_next_moves все еще занимает больше времени, хотя create_cells догоняет. Одна идея состоит в том, чтобы сменить наборы на битмаски:

@timeit
def create_cells(puzzle):
    rows = [0] * 9
    columns = [0] * 9
    groups = [0] * 9
    untaken = []

    for index, value in enumerate(puzzle):
        row, column, group = INDEX_TO_VALUE[index]
        if value:
            rows[row] |= 1<<(value-1)
            columns[column] |= 1<<(value-1)
            groups[group] |= 1<<(value-1)
        else:
            untaken.append((row, column, group))

    return rows, columns, groups, untaken

decode_bits = [tuple(i+1 for i in range(9) if 1<<i & bits) for bits in range(512)]

@timeit
def get_next_moves(puzzle):
    rows, columns, groups, untaken = create_cells(puzzle)
    other_option = None
    len_option = 9

    for row, column, group in untaken:
        missing_values = decode_bits[0b111111111 & ~rows[row] & ~columns[column] & ~groups[group]]

        if len(missing_values) == 1:
            return 9*row+column, missing_values

        elif len(missing_values) < len_option:
            len_option = len(missing_values)
            other_option = 9*row+column, missing_values

    return other_option

Это дает очень хорошее повышение скорости до PyPy и улучшает CPythonзаметно:

$ python3 p.py
HARD - 3 RUNS
Total: 8.0 seconds
    Mean: 2.66720 seconds
    Max: 2.67445 seconds
    Min: 2.66322 seconds

create_cells()
    Called: 47680 times per run (143040 total)
    Running for 6.101s (in 3 runs) / 2.03374s per run
get_next_moves()
    Called: 47680 times per run (143040 total)
    Running for 1.189s (in 3 runs) / 0.39625s per run
possible_moves()
    Called: 47680 times per run (143040 total)
    Running for 0.443s (in 3 runs) / 0.14770s per run
depth_first_search()
    Called: 1 times per run (3 total)
    Running for 0.268s (in 3 runs) / 0.08946s per run
win()
    Called: 1 times per run (3 total)
    Running for 0.000s (in 3 runs) / 0.00004s per run
main()
    Called: 1 times per run (1 total)
    Running for 0.000s (in 3 runs) / 0.00003s per run

и для PyPy:

$ pypy3 p.py  
HARD - 4 RUNS
Total: 1.0 seconds
    Mean: 0.26078 seconds
    Max: 0.35315 seconds
    Min: 0.21801 seconds

possible_moves()
    Called: 47680 times per run (190720 total)
    Running for 0.519s (in 4 runs) / 0.12972s per run
create_cells()
    Called: 47680 times per run (190720 total)
    Running for 0.339s (in 4 runs) / 0.08473s per run
depth_first_search()
    Called: 1 times per run (4 total)
    Running for 0.094s (in 4 runs) / 0.02351s per run
get_next_moves()
    Called: 47680 times per run (190720 total)
    Running for 0.091s (in 4 runs) / 0.02272s per run
win()
    Called: 1 times per run (4 total)
    Running for 0.000s (in 4 runs) / 0.00009s per run
main()
    Called: 1 times per run (1 total)
    Running for 0.000s (in 4 runs) / 0.00005s per run

Итак, следующая задача - create_cells или possible_moves, в зависимости от того, какой интерпретатор вам больше всего нравится. Начиная с create_cells, у меня есть:

@timeit
def create_cells(puzzle):
    rows = [0] * 9
    columns = [0] * 9
    groups = [0] * 9
    untaken = []

    for index, value in enumerate(puzzle):
        row, column, group = INDEX_TO_VALUE[index]
        if value:
            rows[row] |= 1<<(value-1)
            columns[column] |= 1<<(value-1)
            groups[group] |= 1<<(value-1)
        else:
            untaken.append((row, column, group))

    return rows, columns, groups, untaken

CPython не дедуплицирует повторяющиеся константы, такие как PyPy, поэтому нужно дедуплицировать его вручную. Мы также должны перейти к использованию zip вместо enumerate:

@timeit
def create_cells(puzzle):
    rows = [0] * 9
    columns = [0] * 9
    groups = [0] * 9
    untaken = []

    for position, value in zip(INDEX_TO_VALUE, puzzle):
        if value:
            row, column, group = position
            bit = 1<<(value-1)
            rows[row] |= bit
            columns[column] |= bit
            groups[group] |= bit
        else:
            untaken.append(position)

    return rows, columns, groups, untaken

CPython заметно быстрее:

$ python3 p.py
Total: 5.9 seconds

$ python2 p.py
Total: 4.1 seconds

CPython теперь работает так же быстро, как PyPy был в самом начале! Я не получал времен для PyPy.

Это даже немного быстрее, если мы переносим изменение; заставить все операции действовать на сдвинутые биты и не сдвигать их в конце; например.

bit_counts = tuple(bin(i).count("1") for i in range(512))

@timeit
def get_next_moves(puzzle):
    rows, columns, groups, untaken = create_cells(puzzle)
    other_option = None
    len_option = 9

    for row, column, group in untaken:
        missing_values = 0b111111111 & ~rows[row] & ~columns[column] & ~groups[group]
        set_bits = bit_counts[missing_values]

        if set_bits == 1:
            return 9*row+column, missing_values

        elif set_bits < len_option:
            len_option = set_bits
            other_option = 9*row+column, missing_values

    return other_option

и аналогичный для остальной части кода.

$ pypy3 p.py
    Min: 0.11042 seconds

$ pypy p.py 
    Min: 0.13626 seconds

$ python3 p.py
    Min: 1.70156 seconds

$ python2 p.py
    Min: 1.24454 seconds

Я использую минимальные времена, потому что PyPy становится ниже минимального времени исполнения. Мы видим, что оба переводчика намного быстрее, чем раньше.

Лично я напишу possible_moves как генератор:

@timeit
def possible_moves(puzzle):
    index_moves = get_next_moves(puzzle)

    if not index_moves:
        return

    index, moves = index_moves
    for bit in bits:
        if moves & bit:
            yield puzzle[:index] + (bit,) + puzzle[index + 1:]

Вместо вашего кода времени я бы использовал cProfile. Он встроен и намного проще в использовании. Для CPython я также иногда использовал line_profiler, который дает линейные тайминги. Другими словами, это лучшая вещь эва. Я бы использовал утилиту time, чтобы получить время всего кода, когда не нужны мелкие промежутки времени.

Они избавляются от нетривиальной части кода.

Я был бы очень осторожен, чтобы придерживаться интервала PEP8 и добавлять разрывы строк, где они помогают. Ваш код слишком плотный.

Я бы извлек код сетки в другую функцию.

main не должен действительно возвращать вещи; придерживайтесь всего под if __name__ == '__main__' в main.

depth_first_search будет возвращать только одно решение, поэтому нет необходимости возвращать набор. Далее,

  • Попробуйте вернуться раньше,
  • Поднимите исключение if not win, так как вы ввели недопустимое состояние.
  • Не используйте тип верхнего уровня Exception; используйте более точные варианты.
def depth_first_search(start):
    stack = [start]
    solution = None

    while stack:
        vertex = stack.pop()

        if 0 not in vertex:
            assert win(vertex)

            if solution and vertex != solution:
                raise ValueError("More than one solution")

            solution = vertex

        else:
            stack.extend(possible_moves(vertex))

    if solution is None:
        raise ValueError("No solution found")

    return solution

win на самом деле не проверяет, выиграли ли вы; переименуйте его, скажем, в validate.

INDEX_TO_VALUE действительно должен быть переименован в эту точку. Я бы пошел с POSITIONS.

validate может быть просто:

def validate(puzzle):
    return Counter(puzzle) == dict.fromkeys(BITS, 9)

По-моему, depth_first_search должен давать свои решения, включая дубликаты, и вызывающий должен отвечать за проверку того, что правильное количество решений присутствовать и удалять дубликаты.

Должен быть словарь puzzle name: puzzle, который используется для поиска головоломок. Я также попытался бы форматировать сетку более явно.

Я бы пошел с:

_ = 0

puzzles = {
    'easy': [
        5,3,_, _,7,_, _,_,_,
        6,_,_, 1,9,5, _,_,_,
        _,9,8, _,_,_, _,6,_,

        8,_,_, _,6,_, _,_,3,
        4,_,_, 8,_,3, _,_,1,
        7,_,_, _,2,_, _,_,6,

        _,6,_, _,_,_, 2,8,_,
        _,_,_, 4,1,9, _,_,5,
        _,_,_, _,8,_, _,7,9,
    ],

    'hard': [
        8,_,_, _,_,_, _,_,_,
        _,_,3, 6,_,_, _,_,_,
        _,7,_, _,9,_, 2,_,_,

        _,5,_, _,_,7, _,_,_,
        _,_,_, _,4,5, 7,_,_,
        _,_,_, 1,_,_, _,3,_,

        _,_,1, _,_,_, _,6,8,
        _,_,8, 5,_,_, _,1,_,
        _,9,_, _,_,_, 4,_,_,
    ]
}

Вот полный код:

# encoding: utf8

"""
A puzzle-solving masterpiece!

Solves Soduko.
"""

from __future__ import print_function

import functools
import time

from collections import Counter


def group_at(row, col):
    return row // 3 + col // 3 * 3

# The row, column and group number for each item in the grid
POSITIONS = tuple((row, col, group_at(row, col)) for row in range(9) for col in range(9))

# The number of bits for each value 0 <= i < 512
BIT_COUNTS = tuple(bin(i).count("1") for i in range(512))

# For looping
BITS = tuple(1<<i for i in range(9))

# Inverse of above for printing
DECODE_BIT = {1<<i: i+1 for i in range(9)}
DECODE_BIT[0] = 0


def find_taken(puzzle):
    """
    Return three lists of what numbers are taken in each row, column and group and
    one list of which positions (row, column, group) are untaken.
    """

    rows = [0] * 9
    columns = [0] * 9
    groups = [0] * 9
    untaken = []

    for position, bit in zip(POSITIONS, puzzle):
        if bit:
            row, column, group = position
            rows[row] |= bit
            columns[column] |= bit
            groups[group] |= bit
        else:
            untaken.append(position)

    return rows, columns, groups, untaken


def get_next_moves(puzzle):
    """
    Return the (index, missing_values) pair with the fewest possible moves.
    index is an integer 0 <= index < 81 and missing_values is a bitset
    of length 9.

    Returns None if there are no candidate moves.
    """

    rows, columns, groups, untaken = find_taken(puzzle)
    other_option = None
    len_option = 9

    for row, column, group in untaken:
        missing_values = 0b111111111 & ~rows[row] & ~columns[column] & ~groups[group]
        set_bits = BIT_COUNTS[missing_values]

        if set_bits == 1:
            return 9*row+column, missing_values

        elif set_bits < len_option:
            len_option = set_bits
            other_option = 9*row+column, missing_values

    return other_option


def possible_moves(puzzle, index, moves):
    """
    Yield the states of the grid for after taking the given moves at index on puzzle.

    index is an integer 0 <= index < 81 and moves is a bitset of length 9.
    """

    for bit in BITS:
        if moves & bit:
            yield puzzle[:index] + (bit,) + puzzle[index + 1:]


def validate(puzzle):
    """
    Validate that the puzzle contains 9 of each number and is length 81.

    This does not fully validate that the solution is valid.
    """

    return Counter(puzzle) == dict.fromkeys(BITS, 9)


def depth_first_search(puzzle):
    """
    Do a depth-first search of the solution space for the input Soduku puzzle.
    Yields solutions. May yield duplicates.
    """

    stack = [puzzle]

    while stack:
        vertex = stack.pop()

        if 0 not in vertex:
            assert validate(vertex)
            yield vertex

        else:
            stack.extend(possible_moves(vertex, *get_next_moves(vertex)))


def print_grid(puzzle):
    """
    Print a pretty representation of the input Soduku puzzle.
    """

    for i, bit in enumerate(puzzle, 1):
        value = DECODE_BIT[bit] or "·"

        if i % 9 == 0:
            print(value)
        else:
            print(value, end="")

        if i % 9 and not i % 3:
            print(" ", end="")

        if i == 27 or i == 54:
            print()


def main(puzzle_name):
    _ = 0

    puzzles = {
        'easy': [
            5,3,_, _,7,_, _,_,_,
            6,_,_, 1,9,5, _,_,_,
            _,9,8, _,_,_, _,6,_,

            8,_,_, _,6,_, _,_,3,
            4,_,_, 8,_,3, _,_,1,
            7,_,_, _,2,_, _,_,6,

            _,6,_, _,_,_, 2,8,_,
            _,_,_, 4,1,9, _,_,5,
            _,_,_, _,8,_, _,7,9,
        ],

        'hard': [
            8,_,_, _,_,_, _,_,_,
            _,_,3, 6,_,_, _,_,_,
            _,7,_, _,9,_, 2,_,_,

            _,5,_, _,_,7, _,_,_,
            _,_,_, _,4,5, 7,_,_,
            _,_,_, 1,_,_, _,3,_,

            _,_,1, _,_,_, _,6,8,
            _,_,8, 5,_,_, _,1,_,
            _,9,_, _,_,_, 4,_,_,
        ]
    }

    grid = tuple(i and 1<<(i-1) for i in puzzles[puzzle_name])

    print("Puzzle:")
    print_grid(grid)

    [result] = set(depth_first_search(grid))

    print()
    print("Result:")
    print_grid(result)


if __name__ == '__main__':
    main('hard')
ответил Veedrac 26 FriEurope/Moscow2014-12-26T08:12:34+03:00Europe/Moscow12bEurope/MoscowFri, 26 Dec 2014 08:12:34 +0300 2014, 08:12:34
6

Я думаю, что было бы довольно быстро хранить, какие числа уже использовались в двух массивах int[9] и в одном int[3][3]. Затем используйте растровые изображения для представления того, какое число было использовано в каждом столбце, строке и группе.

Например, когда вы помещаете ---- +: = 2 =: + ---- в ячейку 3, вы бы:

(3,4). row[3] |= 1<<3, column[4] |= 1<<3, а затем вы можете проверить если число находится в строке, col или группе с помощью group[1][2] |= 1<<3 и т. д.

Вы понимаете. По-моему, это было бы довольно быстро. Хотя у меня нет теста. Я думаю, это потому, что вместо того, чтобы проверять каждую ячейку для каждого нового значения, вы проверяете только 3 (один раз за #, который вы хотите сбросить, так что всего 27).

Как это работает?

if row[rowNumber] & 1<<number: - массив из 9 позиций. Каждый row хранит информацию, для которой номер был использован в указанной строке. Как вы знаете, int сохраняется как 32-разрядное двоичное число. Когда вы выполняете int то, что вы на самом деле делаете, это установить младший бит 4 . Так что если число было (я просто собираюсь использовать 10 бит для ясности) row[3] |= 1<<3 он становится 0000000000. Таким образом, когда у вас есть строка, которая, например, использует 0000001000. У вас будет номер, обозначенный как 1, 3, 9 (Последний 1000001010 никогда не помечен, это для использования базы 1 для ясности кода). Теперь, как вы можете узнать, какой бит отмечен? Ну, используя побитовое и 0. Таким образом, вы создаете номер, который имеет только бит, который вы хотите запросить для отмеченного &, а затем используйте 1<<number, чтобы извлечь номер, который может иметь только указанный номер (поскольку каждый другой бит будет сравниваться с & и всегда выведите 0). Таким образом, вы делаете 0, например, чтобы спросить, было ли в строке номер 3 использовано число 9. В нижней части вы будете делать (придерживаясь примера строки с 1, 3, 9):

row[3] & 1<<9

Это даст положительное (то есть ненулевое) число, которое вы можете «1000001010 & 1000000000 ---------- 1000000000 », чтобы увидеть его значение истинности.

Если он был ложным (например, запрашивая if):

8

Это даст 1000001010 & 0100000000 ---------- 0000000000 , поэтому 0 будет false.

Обновление: дополнительные модификации

Чтобы не воссоздать снова и снова все состояние платы (с использованием магазина столько раз). Вы можете сохранить одно состояние в начале if, ROWS и COLUMNS. И затем, каждый раз, когда вы храните что-то в стеке, поставьте туда и то, что вы сделали (строка, столбец, группа и значение). Таким образом, каждый раз, когда вы выталкиваете что-то из стека, вы GROUPS перемещаетесь в этой точке (нужно сохранить только одну вещь, гораздо более эффективную ). И в конце цикла вы можете store его просто сделать (например) unstore. Вот как я понимаю ваш код, это может быть неправильно, но вы можете проанализировать это и сказать мне, может ли он работать.

ответил Santiago 24 WedEurope/Moscow2014-12-24T09:16:27+03:00Europe/Moscow12bEurope/MoscowWed, 24 Dec 2014 09:16:27 +0300 2014, 09:16:27

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132