Судоку

Эта задача сводится к задаче, в которой необходимо определить: является ли представленный набор k чисел таковым, что он состоит из множества разных чисел от 1 до k (в нашем случае k=n²). С одной стороны, можно было бы отсортировать этот набор чисел и проверить: в полученном массиве равно ли значение элемента его номеру. Этот метод прошел бы в силу того, что ограничения невелики, однако, этот способ неэффективен и сложнее по реализации, чем следующий. Мы можем определить некоторый массив d[1..k] (в нашем случае лучше описать такой массив из 100 элементов, независимо от n), заполнив его предварительно нулями. В процессе перебора всех чисел представленного набора элементов для каждого числа x будем выполнять присваивание d[x]=1, которое обеспечит факт присутствия числа x в списке. По окончании этой операции достаточно будет проверить все элементы массива d от 1 до k: если встретился хотя бы 1 ноль, то условие не выполнено, иначе все верно.

Описанный выше метод следует сначала применить для элементов каждой строки, далее для элементов каждого столбца, потом для каждого подмассива размерности n x n. Последняя операция, вероятно, более сложна, поэтому приведем примерный код перебора всех таких подмассивов:

  for i=1..n{
    for j=1..n{
      d[1..100]={0..0};
      for y=(i-1)*n+1 .. i*n{
        for x=(j-1)*n+1 .. j*n{
          d[a[y][x]]=1;
        }    
      }
      Check(d);
    }
  }

[Обсуждение] [Все попытки] [Задача]