Классный алгоритм, чтобы проверить поле судоку?

Question

Кто-нибудь знает простой алгоритм проверки правильности конфигурации Sudoku? Простейший алгоритм, который я придумал, (для доски размером n) в псевдокоде

for each row
  for each number k in 1..n
    if k is not in the row (using another for-loop)
      return not-a-solution

..do the same for each column

Но я вполне уверен, что должно быть лучшее (в смысле более элегантного) решение. Эффективность совершенно не важна.

Answer 1

У Питера Норвига есть отличная статья по решению головоломок судоку (с питоном),

http://norvig.com/sudoku.html

Может быть, это слишком много для того, что вы хотите сделать, но в любом случае это отличное чтение

Answer 2

Вам необходимо проверить все ограничения судоку:

• проверить сумму в каждой строке
• проверить сумму по каждому столбцу
• чек на сумму на каждом ящике
• проверка на наличие повторяющихся номеров в каждой строке
• проверить наличие дубликатов в каждом столбце
• проверьте наличие дубликатов на каждом поле

это всего 6 проверок ... с использованием подхода грубой силы.

Некоторая математическая оптимизация может быть использована, если вы знаете размер доски (то есть 3x3 или 9x9)

Редактировать : объяснение ограничения суммы: сначала проверять сумму (и останавливать, если сумма не 45) гораздо быстрее (и проще), чем проверять дубликаты. Это простой способ отказаться от неправильного решения.

Answer 3

Отметьте каждую строку, столбец и поле так, чтобы они содержали номера 1-9, без дубликатов. Большинство ответов здесь уже обсуждают это.

Но как это сделать эффективно? Ответ: используйте цикл вроде

result=0;
for each entry:
  result |= 1<<(value-1)
return (result==511);

Каждое число будет устанавливать один бит результата. Если все 9 чисел уникальны, то самые низкие 9 биты будут установлены. Таким образом, тест «проверка на наличие дубликатов» - это просто проверка того, что установлены все 9 битов, что соответствует результату тестирования == 511 Вам необходимо выполнить 27 таких проверок ... по одной для каждой строки, столбца и поля.

Answer 4

Просто мысль: не нужно ли вам также проверять числа в каждом квадрате 3х3?

Я пытаюсь выяснить, можно ли выполнить условия для строк и столбцов, не имея правильного судоку

Answer 5

Создать массив логических значений для каждой строки, столбца и квадрата. Индекс массива представляет значение , помещенное в эту строку, столбец или квадрат. Другими словами, если вы добавите 5 во второй ряд, первый столбец, вы должны установить для строк [2] [5] значение true вместе со столбцами [1] [5] и квадратами [4] [5], чтобы указать что строка, столбец и квадрат теперь имеют значение 5.

Независимо от того, как выглядит ваша оригинальная доска, это может быть простой и очень быстрый способ проверить ее на полноту и правильность. Просто возьмите числа в порядке их появления на доске и начните строить эту структуру данных. Когда вы размещаете числа на доске, она становится операцией O (1), чтобы определить, дублируются ли какие-либо значения в данной строке, столбце или квадрате. (Вы также можете проверить, что каждое значение является допустимым числом: если вам дают пустое или слишком высокое число, вы знаете, что доска не завершена.) Когда вы доберетесь до конца доски, вы Вы узнаете, что все значения верны, и проверка больше не требуется.

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

Answer 6

Это моё решение в Python, я рад видеть, что оно самое короткое :)

код:

def check(sud):
    zippedsud = zip(*sud)

    boxedsud=[]
    for li,line in enumerate(sud):
        for box in range(3):
            if not li % 3: boxedsud.append([])    # build a new box every 3 lines
            boxedsud[box + li/3*3].extend(line[box*3:box*3+3])

    for li in range(9):
        if [x for x in [set(sud[li]), set(zippedsud[li]), set(boxedsud[li])] if x != set(range(1,10))]:
            return False
    return True  

И исполнение:

sudoku=[
[7, 5, 1,  8, 4, 3,  9, 2, 6],
[8, 9, 3,  6, 2, 5,  1, 7, 4], 
[6, 4, 2,  1, 7, 9,  5, 8, 3],
[4, 2, 5,  3, 1, 6,  7, 9, 8],
[1, 7, 6,  9, 8, 2,  3, 4, 5],
[9, 3, 8,  7, 5, 4,  6, 1, 2],
[3, 6, 4,  2, 9, 7,  8, 5, 1],
[2, 8, 9,  5, 3, 1,  4, 6, 7],
[5, 1, 7,  4, 6, 8,  2, 3, 9]]

print check(sudoku)        

Answer 7

Я сделал это один раз для проекта класса. Я использовал всего 27 наборов для представления каждой строки, столбца и поля. Я бы проверял числа по мере их добавления к каждому набору (каждое размещение числа приводит к добавлению номера к 3 наборам, строке, столбцу и блоку), чтобы убедиться, что пользователь вводит только цифры 9. Единственный способ заполнить набор - это правильно заполнить его уникальными цифрами. Если все 27 наборов были заполнены, головоломка была решена. Настройка отображений из пользовательского интерфейса на 27 наборов была немного утомительной, но оставшуюся логику легко реализовать.

Answer 8

Вы можете извлечь все значения в наборе (строка, столбец, поле) в список, отсортировать его, а затем сравнить с '(1, 2, 3, 4, 5, 6, 7, 8, 9)

Answer 9

Создание наборов ячеек, где каждый набор содержит 9 ячеек, и создание наборов для вертикальных столбцов, горизонтальных рядов и квадратов 3x3.

Затем для каждой ячейки просто определите наборы, в которые она входит, и проанализируйте их.

Answer 10

, если сумма и , умножение строки / столбца равно правильному числу 45/362880