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

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

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

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

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

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

Можно использовать своего рода математическую оптимизацию, если вы знаете размер доски (например, 3x3 или 9x9).

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

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

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;

Допустим, int судоку [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;

}

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

https://norvig.com/sudoku.html

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

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

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

Предположим, что ваша доска идет от 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. 

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

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

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))

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

Некоторое время назад я написал средство проверки судоку, которое проверяет наличие повторяющихся номеров в каждой строке, повторяющихся номеров в каждом столбце и повторяющихся номеров в каждом поле. Я был бы рад, если бы кто-нибудь мог придумать что-то вроде нескольких строк кода 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
}

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

Эта статья была опубликована в апреле 2009 года и получила широкую огласку как однозначное решение судоку (проверьте в Google "Судоку Дж. Ф. Крука") .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Это мое решение на 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)        

Вот мой в C. Пройдите каждую клетку только один раз.

int checkSudoku(int board[]) {
  int i;
  int check[13] = { 0 };

  for (i = 0; i < 81; i++) {
    if (i % 9 == 0) {
      check[9] = 0;
      if (i % 27 == 0) {
        check[10] = 0;
        check[11] = 0;
        check[12] = 0;
      }
    }

    if (check[i % 9] & (1 << board[i])) {
      return 0;
    }
    check[i % 9] |= (1 << board[i]);

    if (check[9] & (1 << board[i])) {
      return 0;
    }
    check[9] |= (1 << board[i]);

    if (i % 9 < 3) {
      if (check[10] & (1 << board[i])) {
        return 0;
      }
      check[10] |= (1 << board[i]);
    } else if (i % 9 < 6) {
      if (check[11] & (1 << board[i])) {
        return 0;
      }
      check[11] |= (1 << board[i]);
    } else {
      if (check[12] & (1 << board[i])) {
        return 0;
      }
      check[12] |= (1 << board[i]);
    }
  }
}

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

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];
        }
    }
}

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

Вот что я только что сделал для этого:

boolean checkers=true;
String checking = "";
    if (a.length/3==1){}
    else{
       for(int l=1; l<a.length/3; l++){
            for(int n=0;n<3*l;n++){
                for(int lm=1; lm<a[n].length/3; lm++){
                    for(int m=0;m<3*l;m++){
                    System.out.print("    "+a[n][m]);
                    if (a[n][m]<=0){
                    System.out.print("        (Values must be positive!)        ");
                    }
                    if (n==0){
                        if (m!=0){
                        checking+ = ", "+a[n][m];
                    }
                    else{
                        checking+=a[n][m];
                    }
                }
                else{
                    checking+ = ", "+a[n][m];
                }
            }
                    }
            System.out.print("        "+checking);
            System.out.println();
                }
       }
            for (int i=1;i<=a.length*a[1].length;i++){
        if (checking.contains(Integer.toString(i))){

        }
        else{
            checkers=false;
        }
            }
        }
    checkers=checkCol(a);
    if (checking.contains("-")&&!checking.contains("--")){
        checkers=false;
    }
    System.out.println();
    if (checkers==true){
        System.out.println("This is correct! YAY!");
    }
    else{
        System.out.println("Sorry, it's not right. :-(");
    }
}
private static boolean checkCol(int[][]a){
    boolean checkers=true;
    int[][]col=new int[][]{{0,0,0},{0,0,0},{0,0,0}};
    for(int i=0; i<a.length; i++){
        for(int j=0; j<a[i].length; j++){
            if (a[i][j]>9||a[i][j]<1){
                checkers=false;
                break;
            }
            else{
                col[a[i].length-j][i]=a[i][j];
            }
        }
    }
    String alia = "";
    for(int i=0; i<col.length; i++){
        for(int j=1; j<=col[i].length; j++){
            alia=a[i].toString();
            if (alia.contains(""+j)){
                alia=col[i].toString();
                if (alia.contains(""+j)){}
                else{
                    checkers=false;
                }   
            }
            else{
                checkers=false;
            }
        }
    }
    return checkers;
}

Вот хороший читабельный подход в Python:

from itertools import chain                                                                                            

def valid(puzzle):                                                                                                     
    def get_block(x,y):                                                                                                
        return chain(*[puzzle[i][3*x:3*x+3] for i in range(3*y, 3*y+3)])                                               
    rows = [set(row) for row in puzzle]                                                                                
    columns = [set(column) for column in zip(*puzzle)]                                                                 
    blocks = [set(get_block(x,y)) for x in range(0,3) for y in range(0,3)]                                             
    return all(map(lambda s: s == set([1,2,3,4,5,6,7,8,9]), rows + columns + blocks))         

Каждый квадрат 3x3 называется блоком, а их 9 в сетке 3x3. Предполагается, что головоломка вводится как список списков, каждый внутренний список которого представляет собой строку.

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

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

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

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

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

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

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)

Вот очень краткая версия на Swift, которая использует только массив Ints для отслеживания групп из 9 чисел и выполняет итерацию судоку только один раз.

import UIKit

func check(_ sudoku:[[Int]]) -> Bool {

    var groups = Array(repeating: 0, count: 27)

    for x in 0...8 {
        for y in 0...8 {
            groups[x] += 1 << sudoku[x][y] // Column (group 0 - 8)
            groups[y + 9] += 1 << sudoku[x][y] // Row (group 9 - 17)
            groups[(x + y * 9) / 9 + 18] += 1 << sudoku[x][y] // Box (group 18 - 27)
        }
    }

    return groups.filter{ $0 != 1022 }.count == 0
}

let 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]
]

if check(sudoku) {
    print("Pass")
} else {
    print("Fail")
}

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