Arduino.ru

Смеха ради написал на Питоне, а потом переписывал на Си. Код не оптимален и не красив. Но "причесывать" не стал, комментарии только добавил. Можно еще компактнее сделать и в Тиньку 85 запихнуть... А может и 45?

Все мы любим судоку и гордимся, что в тилипоне или на компе выбираем уровень максимальной сложности. Так? ;)))

Программка покажет нам величину "ценности" этого навыка. Примерно 3К кода и 1К памяти ;))))))

Как обычно условия запуска- IDE 1.8.13, Arduino Nano, 328 old bootloader.

// основная и изменяема матрицы задачи 81 клетка с множеством вариантов
// множество задается своей битовой маской

uint16_t cels[81];
uint16_t altcels[81];

//задачка 0 - не заполненная клетка
char sd[9][10] = {
  "050300009",
  "008100000",
  "000006010",
  "403009070",
  "800000500",
  "605004020",
  "000007030",
  "001200000",
  "020900004"
};

//p от power = мощность множества = количество единичек
byte p(uint16_t d) {
  byte r;
  //защита "от дурака"
  d &= 0b1111111110;
  for (r = 0; d != 0; d >>= 1) r += d & 1;
  return r;
}

//по номеру клетки её ряд/столбец/клетка 3х3
byte row(byte i) {
  return i / 9;
}

byte col(byte i) {
  return i % 9;
}

byte sqw(byte i) {
  return i / 9 / 3 * 3 + i % 9 / 3;
}

//список подмножеств (0-8 ряды / 9-17 столбцы / 18-26 клетки)
byte subSets[27][9];

//главная функция - редукция
//1. вычеркивает из вариантов уже установленные цифры
//2. при единственном месте для цифры в подмножестве - ставит её
//дурацкое имя параметра Acels - появилось при отладке... ну пусть так и останется

int8_t reduceSudoku(uint16_t * Acels)
{
  int8_t i, j, l, l1, n, ncel; //всякие индексы циклов

  while (1) {
//подсчитаем сумму к-ва вариантов по клеткам
    for (i = 0, l = 0 ; i < 81; i++) l += p(Acels[i]);
//цикл по всем подмножествам с проверкой на наличие единственных мест
    for (byte ss = 0; ss < 27; ss++) {
      //проверим каждую цифру
      for (byte d = 1; d < 10; d++) {
        //в какое к=во клеток в подмножестве она входит?
        byte x;
        for (i = 0, x = 0; i < 9; i++) x += (Acels[ subSets[ss][i] ] & (1 << d)) ? 1 : 0;
        //если только в одну то туда её и поставим... придется снова найти это место ;))
        if (1 == x)
          for (i = 0; i < 9; i++)
            if (Acels[ subSets[ss][i] ] & (1 << d) )
              Acels[ subSets[ss][i] ] = (1 << d);
      }
    }
// вычеркивание из подмножеств установленных цифр
    for (ncel = 0; ncel < 81; ncel++) {

      if (p(Acels[ncel]) == 1)
      //в каждом подмножестве 9 элементов. на Питоне такие циклы выглядят красивее
        for (i = 0; i < 9; i++) {
          if (ncel != subSets[row(ncel)][i] )
            Acels[ subSets[row(ncel)][i] ] &= ~(Acels[ncel]);
          if (ncel != subSets[col(ncel) + 9][i])
            Acels[ subSets[col(ncel) + 9][i]] &= ~(Acels[ncel]);
          if (ncel != subSets[sqw(ncel) + 18][i])
            Acels[ subSets[sqw(ncel) + 18][i]] &= ~(Acels[ncel]);
        }
    }
//снова найдем сумму вариантов, если она не уменьшилась - выйдем из цикла
    for (i = 0, l1 = 0 ; i < 81; i++) l1 += p(Acels[i]);
    if (l == l1) break;
  }

  //проверим на наличие ноля вариантов - то есть несовместности условия
  for (i = 0, l1 = 9 ; i < 81; i++)  if (Acels[i] == 0) l1 = 0;
  if (l1 == 0)
  // -1 если задача не совместна
    return -1;
  else
  //сумма вариантов иначе, я её не использую, думал, что понадобится ;))
    return l;
}

//печать задачки 
//печатаем построчно, клетки - через пробел
//все возможные для клетки цифры - слитно
//если для клетки нет вариантов (несовместная задача) - в ней Х
void printSudoku(uint16_t * cels) {
  byte i, j, d;

  Serial.println("====================================");

  for (i = 0; i < 9; i++) {
    for (j = 0; j < 9; j++) {
      if (cels[i * 9 + j] == 0)
        Serial.print('X');
      else
        for (d = 1; d < 10; d++)
          if ((1 << d) & cels[i * 9 + j])
            Serial.print((char)(d + '0'));
      Serial.print(' ');
    }
    Serial.println();
  }
  Serial.println("====================================");
}



//====================================
void setup() {
  byte i, j, n, d, l; //индексы в циклах

  Serial.begin(115200);
//строим списки подмножеств, можно было и руками написать, но это лень
  for (byte d = 0; d < 81; d++) {
    subSets[d / 9 + 0][d % 9] = d;
    subSets[d % 9 + 9][d / 9] = d;
    subSets[d / 9 / 3 * 3 + d % 9 / 3 + 18] [d % 3 * 3 + d / 9 % 3] = d;
  }
//заполняем таблицу задачи в каждой клетке - множество вариантов цифр
  for (i = 0; i < 9; i++)
    for (j = 0; j < 9; j++) {
      if (sd[i][j] != '0')
        cels[i * 9 + j] = (1 << (sd[i][j]) - '0');
      else
        cels[i * 9 + j] = 0b1111111110;
    }
//первая редукция
  printSudoku(cels);
  reduceSudoku(cels);

//массив оставшихся клеток с альтернативами
  byte alts[81];

  for (i = 0, j = 0; i < 81; i++) {
    if (p(cels[i]) > 1) alts[j++] = i;
  }
  alts[j] = 0;

//перебираем альтернативы
  for (n = 0; alts[n]; n++) {
    uint16_t savedcel = cels[alts[n]];
    //для каждого варианта - проведем редукцию с ним
    for (d = 1; d < 10; d++) if (cels[alts[n]] & (1 << d)) {
        memcpy(altcels, cels, 162);
        altcels[ alts[n] ] = (1 << d);
        //если вариант приводит к несовместности
        if (reduceSudoku(altcels) == -1)
          //вычеркиваем его
          savedcel &= ~(1 << d);
      }
    cels[alts[n]] = savedcel;
    reduceSudoku(cels);
  }

  //радостно печатаем результат
  //минимум вариантов в клетке == 0 - нерешаемая задача
  for (i = 0, l = 9 ; i < 81; i++)  if (l > p(cels[i])) l = p(cels[i]);
  if (l == 0)
    Serial.println("UNSOLABLE");

  else {
    //сумма вариантов в 9х9 клеток == 81 - решено
    for (i = 0, l = 0 ; i < 81; i++) l += p(cels[i]);

    if (l == 81)
      Serial.println("SOLVED");
    else
      Serial.println("NOT SOLVED");

    printSudoku(cels);
  }
}

void loop() {}

Следует сказать, что алгоритм БЕЗ перебора с возвратом может решать не все задачки. Я не встречал таких, но если кто встретит - будет интересно.

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

Легко доказать, что если у головоломки ЕДИНСТВЕННОЕ решение, то оно достижимо таким алгоритмом.

Таки ж она NP-полная :-(

Не читал доказательство NP-полноты, но верю. ;)) Тут хитрость в том, что на подмножестве условий, созданных компьютером  задачка уже совершенно иная.

Мы заранее уведомлены о существующем и единственном решении. Эта априорная информация дает нам право рассчитывать на полиномиальное решение. Как-то так, если "по Гамбургскому счету" ;))).