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

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

24 голосов
/ 14 ноября 2008

Кто-нибудь знает простой алгоритм проверки правильности конфигурации 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

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

Ответы [ 25 ]

0 голосов
/ 15 апреля 2014

Вы можете проверить, решена ли судоку, двумя способами:

  • Проверьте, является ли номер уникальным в каждой строке, столбце и блоке.

Наивным решением было бы выполнить итерацию по каждому квадрату и проверить, является ли число уникальным в строке, блок столбца, который занимает это число.

Но есть и лучший способ.

  • Судоку решается, если каждая строка, столбец и блок содержит перестановку чисел (от 1 до 9)

Для этого требуется только проверить каждую строку, столбец и блок, а не делать это для каждого числа. Простая реализация состояла бы в том, чтобы иметь битовое поле чисел от 1 до 9 и удалять их при итерации столбцов, строк и блоков. Если вы попытаетесь удалить пропущенный номер или если поле не заполнено, когда вы закончите, судоку не будет решена правильно.

0 голосов
/ 14 октября 2016 
def solution(board):
    for i in board:
        if sum(i) != 45:
            return "Incorrect"

    for i in range(9):
        temp2 = []
        for x in range(9):
            temp2.append(board[i][x])

        if sum(temp2) != 45:
            return "Incorrect"

    return "Correct"

board = []
for i in range(9):
    inp = raw_input()
    temp = [int(i) for i in inp]
    board.append(temp)

print solution(board)
0 голосов
/ 29 апреля 2009

Я бы написал интерфейс с функциями, которые получают поле sudoku и возвращают true / false, если это решение. Затем реализуйте ограничения как отдельные классы проверки для каждого ограничения.

Для проверки просто переберите все классы ограничений, и когда все пройдут, судоку будет правильным. Для ускорения поместите те, которые, скорее всего, потерпят неудачу, и остановитесь на первом результате, который указывает на недопустимое поле.

Довольно общий шаблон. ; -)

Конечно, вы можете улучшить это, чтобы получить подсказки, какое поле предположительно неверно и т. Д.

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

0 голосов
/ 12 декабря 2018

Одна небольшая оптимизация, которую вы можете сделать, заключается в том, что вы можете проверять наличие дубликатов в строке, столбце или поле за O (n) время, а не за O (n ^ 2): когда вы перебираете набор чисел, вы добавляете каждый хэшсет. В зависимости от языка, вы можете использовать настоящий хэш-набор, который представляет собой поиск и вставку с постоянным временем; тогда проверка на дубликаты может быть выполнена на том же шаге, проверяя, была ли вставка успешной или нет. Это небольшое улучшение в коде, но переход от O (n ^ 2) к O (n) является существенной оптимизацией.

0 голосов
/ 14 ноября 2008

Допустим, int sudoku [0..8,0..8] - это поле судоку. 

bool CheckSudoku(int[,] sudoku)
{
    int flag = 0;

// Check rows
for(int row = 0; row < 9; row++)
{
    flag = 0;
    for (int col = 0; col < 9; col++)
    {
        // edited : check range step (see comments)
        if ((sudoku[row, col] < 1)||(sudoku[row, col] > 9)) 
        {
            return false;
        }

        // if n-th bit is set.. but you can use a bool array for readability
        if ((flag & (1 << sudoku[row, col])) != 0) 
        {
            return false;
        }

        // set the n-th bit
        flag |= (1 << sudoku[row, col]); 
    }
}

// Check columns
for(int col= 0; col < 9; col++)
{
    flag = 0;
    for (int row = 0; row < 9; row++)
    {
        if ((flag & (1 << sudoku[row, col])) != 0)
        {
            return false;
        }
        flag |= (1 << sudoku[row, col]);
    }
}

// Check 3x3 boxes
for(int box= 0; box < 9; box++)
{
    flag = 0;
    for (int ofs = 0; ofs < 9; ofs++)
    {
        int col = (box % 3) * 3;
        int row = ((int)(box / 3)) * 3;

        if ((flag & (1 << sudoku[row, col])) != 0)
        {
            return false;
        }
        flag |= (1 << sudoku[row, col]);
    }
}
return true;

}

Страница:
...