Прохладный алгоритм для проверки поля Sudoku?

array = [1,2,3,4,5,6,7,8,9]  
sudoku = int [][]
puzzle = 9 #9x9
columns = map []
units = map [] # box    
unit_l = 3 # box width/height
check_puzzle()    


def strike_numbers(line, line_num, columns, units, unit_l):
    count = 0
    for n in line:
        # check which unit we're in
        unit = ceil(n / unit_l) + ceil(line_num / unit_l) # this line is wrong - rushed
        if units[unit].contains(n): #is n in unit already?
             return columns, units, 1
        units[unit].add(n)
        if columns[count].contains(n): #is n in column already?
            return columns, units, 1
        columns[count].add(n)
        line.remove(n) #remove num from temp row
    return columns, units, line.length # was a number not eliminated?

def check_puzzle(columns, sudoku, puzzle, array, units):
    for (i=0;i< puzzle;i++):
        columns, units, left_over = strike_numbers(sudoku[i], i, columns, units) # iterate through rows
        if (left_over > 0): return false

Без полной проверки, первое, что пришло на ум, это должно работать (с небольшим количеством отладки) в то время как только цикличное выполнение дважды. O (n^2) вместо O (3 (n^2))

Давайте предположим, что Ваша плата идет от 1 - n.

Мы создадим массив проверки, заполним его и затем проверим его.

grid [0-(n-1)][0-(n-1)]; //this is the input grid
//each verification takes n^2 bits, so three verifications gives us 3n^2
boolean VArray (3*n*n) //make sure this is initialized to false


for i = 0 to n
 for j = 0 to n
  /*
   each coordinate consists of three parts
   row/col/box start pos, index offset, val offset 
  */

  //to validate rows
  VArray( (0)     + (j*n)                             + (grid[i][j]-1) ) = 1
  //to validate cols
  VArray( (n*n)   + (i*n)                             + (grid[i][j]-1) ) = 1
  //to validate boxes
  VArray( (2*n*n) + (3*(floor (i/3)*n)+ floor(j/3)*n) + (grid[i][j]-1) ) = 1
 next    
next

if every array value is true then the solution is correct. 

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

Скажем, международное судоку [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;

}

Было бы очень интересно проверить если:

when the sum of each row/column/box equals n*(n+1)/2
and the product equals n!
with n = number of rows or columns

это удовлетворяет правила судоку. Поскольку это допускало бы алгоритм O (n^2), суммируя и умножая корректные ячейки.

Рассмотрение n = 9, суммы должны быть 45, продукты 362880.

Вы сделали бы что-то как:

for i = 0 to n-1 do
  boxsum[i] := 0;
  colsum[i] := 0;
  rowsum[i] := 0;
  boxprod[i] := 1;
  colprod[i] := 1;
  rowprod[i] := 1;    
end;

for i = 0 to n-1 do
  for j = 0 to n-1 do
    box := (i div n^1/2) + (j div n^1/2)*n^1/2;
    boxsum[box] := boxsum[box] + cell[i,j];
    boxprod[box] := boxprod[box] * cell[i,j];
    colsum[i] := colsum[i] + cell[i,j];
    colprod[i] := colprod[i] * cell[i,j];
    rowsum[j] := colsum[j] + cell[i,j];
    rowprod[j] := colprod[j] * cell[i,j];
   end;
end;

for i = 0 to n-1 do
  if boxsum[i] <> 45
  or colsum[i] <> 45
  or rowsum[i] <> 45
  or boxprod[i] <> 362880
  or colprod[i] <> 362880
  or rowprod[i] <> 362880
   return false;

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

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

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

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

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

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

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

Просто мысль: разве Вы не должны также проверять числа в каждого 3x3 квадрат?

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

У Peter Norvig есть большая статья о решении судоку (с Python),

http://norvig.com/sudoku.html

, Возможно, это слишком много, для какого Вы хотите сделать, но это - большое чтение так или иначе

Во-первых, вам нужно сделать логическое «правильное». Затем создайте цикл for, как указано выше. Код для цикла и всего, что потом (в Java), такой, как указано, где field - это двумерный массив с равными сторонами, col - еще один с теми же размерами, а l - это одномерный:

for(int i=0; i<field.length(); i++){
    for(int j=0; j<field[i].length; j++){
        if(field[i][j]>9||field[i][j]<1){
            checking=false;
            break;
        }
        else{
            col[field[i].length()-j][i]=field[i][j];
        }
    }
}

Я не знаю точного алгоритма проверки блоков 3х3, но вы должны проверить все строки в поле и столбце с помощью «/*array name goes here*/[i].contains(1)&&/*array name goes here*/[i].contains(2)» (продолжается до тех пор, пока вы не достигнете длины строки) внутри другого для петля.

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

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

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

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

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

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

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

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

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

Вот статья профессора математики Дж. Ф. Крука: Алгоритм с карандашом и бумагой для решения головоломок судоку

Эта статья была опубликована в апреле 2009 года и получила широкую огласку: определенное решение для судоку (проверьте в Google «JFCrook Sudoku»).

Помимо алгоритма, есть также математическое доказательство того, что алгоритм работает (профессор признал, что он не находит Судоку очень интересным, поэтому он набросал немного математики в бумагу, чтобы сделать его веселее).

Некоторое время назад я написал средство проверки судоку, которое проверяет наличие дублирующегося номера в каждой строке, дублирующего номера в каждом столбце & дубликат числа на каждой коробке. Я был бы рад, если бы кто-то смог придумать такой же код, как несколько строк кода Linq.

char VerifySudoku(char grid[81])
{
    for (char r = 0; r < 9; ++r)
    {
        unsigned int bigFlags = 0;

        for (char c = 0; c < 9; ++c)
        {
            unsigned short buffer = r/3*3+c/3;

                        // check horizontally
            bitFlags |= 1 << (27-grid[(r<<3)+r+c]) 
                        // check vertically
                     |  1 << (18-grid[(c<<3)+c+r])
                        // check subgrids
                     |  1 << (9-grid[(buffer<<3)+buffer+r%3*3+c%3]);

        }

        if (bitFlags != 0x7ffffff)
            return 0; // invalid
    }

    return 1; // valid
}

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