Как проверить после каждой записи в судоку, что она действительна или нет

Question

Я искал приложение Судоку в магазине Google Play и нашел это приложение очень интересным. У них разные уровни сложности. Что я нахожу в этом приложении, так это то, что у них есть кнопка подсказки и автоматическая проверка ошибок, которая автоматически отсоединяет введенный вами номер или нет. Теперь я хочу знать, как я могу создать алгоритм, который будет выполнять ту же работу с введенным номером, правильно или нет. И как там работает кнопка подсказки?

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

PS: дайте мне знать, если этот вопрос не является конструктивным для сайта. Я с удовольствием удалю этот вопрос, потому что не уверен, стоит ли мне ставить этот вопрос здесь или другому сообществу stackru.

Answer 1

Ваш вопрос звучит запутанно. С одной стороны, вы спрашиваете, как проверить, является ли позиция судоку действительной или нет, но в примере вы показываете, как программа помогает найти позицию, в которой нужно поставить число (не проверяя свою судоку, но делая ход, чтобы решить ее),

Чтобы проверить судоку, вам нужно только убедиться, что числа в каждой строке / столбце / квадрате действительны. Это легко достигается с помощью заданной структуры данных. Я не знаю android и не успеваю посмотреть, поэтому вот простой код на python, который принимает массив строк и сообщает, действительна ли судоку:

from collections import Counter

def isValidCounter(cnt):
    del cnt[0]
    for i in cnt:
        if cnt[i] > 1:
            return False
    return True

def isValid(arr):
    M = [[int(i) if i != '.' else 0 for i in line] for line in arr]

    # rows
    for i in M:
        if not isValidCounter(Counter(i)):
            return False

    # columns
    for i in xrange(9):
        if not isValidCounter(Counter(M[j][i] for j in xrange(9))):
            return False

    # squares
    squares = [
        [M[0][i] for i in xrange(0, 3)] + [M[1][i] for i in xrange(0, 3)] + [M[2][i] for i in xrange(0, 3)],
        [M[0][i] for i in xrange(3, 6)] + [M[1][i] for i in xrange(3, 6)] + [M[2][i] for i in xrange(3, 6)],
        [M[0][i] for i in xrange(6, 9)] + [M[1][i] for i in xrange(6, 9)] + [M[2][i] for i in xrange(6, 9)],

        [M[3][i] for i in xrange(0, 3)] + [M[4][i] for i in xrange(0, 3)] + [M[5][i] for i in xrange(0, 3)],
        [M[3][i] for i in xrange(3, 6)] + [M[4][i] for i in xrange(3, 6)] + [M[5][i] for i in xrange(3, 6)],
        [M[3][i] for i in xrange(6, 9)] + [M[4][i] for i in xrange(6, 9)] + [M[5][i] for i in xrange(6, 9)],

        [M[6][i] for i in xrange(0, 3)] + [M[7][i] for i in xrange(0, 3)] + [M[8][i] for i in xrange(0, 3)],
        [M[6][i] for i in xrange(3, 6)] + [M[7][i] for i in xrange(3, 6)] + [M[8][i] for i in xrange(3, 6)],
        [M[6][i] for i in xrange(6, 9)] + [M[7][i] for i in xrange(6, 9)] + [M[8][i] for i in xrange(6, 9)]
    ]
    for square in squares:
        if not isValidCounter(Counter(square)):
            return False

    return True

А вот как выглядит этот массив:

[
  "53..7....",
  "6..195...",
  ".98....6.",
  "8...6...3",
  "4..8.3..1",
  "7...2...6",
  ".6....28.", 
  "...419..5",
  "....8..79"
]