Sudoku.

[yestlmush]

Добрый день! Пытаюсь написать решатель Судоку на C++, но почему-то мое простое переборное решение
работает (как мне кажется) вечно. Помогите, пожалуйста, разобраться, что не так.
Изначально решатель писался для задачи http://projecteuler.net/problem=96,
но он виснет на первом же из предложенных Судоку.

#include <cstdio>
#include <memory.h>

using namespace std;

const int size = 9;
const int cell = 3;
const int grids = 1;

char grid[size][size];

void init_grid() 
{
  char buf[size+2];
  scanf("%s", buf);
  scanf("%s", buf);
  
  for (int i = 0; i < size; i++) 
  {
    scanf("%s", buf);
    for (int j = 0; j < size; j++)
      grid[i][j] = buf[j] - '0';
  }
}

bool done()
{
  for (int i = 0; i < size; i++)
    for (int j = 0; j < size; j++)
      if (grid[i][j] == 0)
        return false;
  return true;
}

char used[size+1];

void backtrack()
{
  if (done())
  {
    puts("done");
    return;
  }

  for (int i = 0; i < size; i++)
    for (int j = 0; j < size; j++)
      if (grid[i][j] == 0)
      {
        memset(used, 0, sizeof(used));

        for (int k = 0; k < size; k++)
        {
          if (grid[i][k]) used[grid[i][k]] = 1;
          if (grid[k][j]) used[grid[k][j]] = 1;
        }

        int sq_i = i / cell, sq_j = j / cell;

        for (int k = sq_i*cell; k < (sq_i+1)*cell; k++)
          for (int l = sq_j*cell; l < (sq_j+1)*cell; l++)
            if (grid[k][l]) used[grid[k][l]] = 1;

        for (char k = 1; k <= size; k++)
          if (!used[k])
          {
            grid[i][j] = k;
            used[k] = 1;

            backtrack();
          }

        grid[i][j] = 0;
      }
}

int main()
{
  freopen("sudoku.txt", "rt", stdin);

  init_grid();

  backtrack();

  for (int i = 0; i < size; i++)
  {
    for (int j = 0; j < size; j++)
      printf("%d", grid[i][j]);
    puts("");
  }
  
  return 0;
}

[Vova_Gidro]

Можете описать свой алгоритм решения словесно и подробно

[yestlmush]

Vova_Gidro в сообщении #616129 писал(а):

Можете описать свой алгоритм решения словесно и подробно

Ну, у меня алгоритм простой, для каждой свободной клетки я определяю множество допустимых цифр (просто цифры, которых
еще нет в строке, столбце, квадрате 3x3), затем ставлю в эту клетку первую цифру, рекурсивно вызываюсь (продолжаю поиск
для следующей свободной клетки), затем ставлю следующую цифру из множества, и т.д.

[Sonic86]

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

[yestlmush]

Sonic86 в сообщении #616885 писал(а):

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

Спасибо, но хотелось бы разобраться, что не так с моей реализацией.

[Xaositect]

Реализацию не читал, с ней, вполне возможно, все хорошо.

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

[arseniiv]

Там точно поиск с возвратом? Показалось, что там нет обнуления клеток, если все предыдущие кандидаты для текущей клетки не подошли. Их надо хранить. И непонятно, зачем рекурсия.

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

[venco]

Да и алгоритм неправильный.
Вы используете глобальный массив used[], так что посчитанные в нём значения теряются при рекурсивном вызове backtrack().
И вообще, для скорости лучше постоянно поддерживать массивы used для каждых строк/столбцов/квадратов при добавлении/удалении каждой цифры, вместо того, чтобы их подсчитывать каждый раз. И done() вызывать не обязательно - количество цифр (вызовов backtrack()) можно посчитать заранее.
Ну и порядок перебора должен быть более умным - сначала ставить цифры в ячейку с меньшим числом вариантов.

[rockclimber]

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

[mikroz]

Вот пример работающего решения задачи, основанное на данном:

Используется синтаксис C++

#include <cstdio>
#include <memory.h>
#include <vector>

using namespace std;

const int size = 9;
const int cell = 3;
const int grids = 50;

char grid[size+2][size+2];
char used[size+2][size+2][size+1];

void init_grid()
{
  char buf[size+2];
  scanf("%s", buf);
  scanf("%s", buf);
 
  for (int i = 0; i < size; i++)
  {
    scanf("%s", buf);
    for (int j = 0; j < size; j++)
      grid[i][j] = buf[j] - '0';
  }

  memset(used, 0, sizeof(used));

  for (int i = 0; i < size; i++)
    for (int j = 0; j < size; j++)
      if (!grid[i][j])
      {
        for (int k = 0; k < size; k++)
        {
          if (grid[i][k]) used[i][j][grid[i][k]] = 1;
          if (grid[k][j]) used[i][j][grid[k][j]] = 1;
        }

        int sq_i = i / cell, sq_j = j / cell;

        for (int k = sq_i*cell; k < (sq_i+1)*cell; k++)
          for (int l = sq_j*cell; l < (sq_j+1)*cell; l++)
            if (grid[k][l]) used[i][j][grid[k][l]] = 1;
      }
}

bool done()
{
  int cnt = 0;
  for (int i = 0; i < size; i++)
    for (int j = 0; j < size; j++)
      if (grid[i][j] == 0)
        return false;

  return true;
}

bool check(int x, int y, char k)
{
  for (int i = 0; i < size; i++)
    if (grid[i][y] == k || grid[x][i] == k)
      return false;

  int sq_i = x / cell, sq_j = y / cell;

  for (int i = sq_i*cell; i < (sq_i+1)*cell; i++)
    for (int j = sq_j*cell; j < (sq_j+1)*cell; j++)
      if (!(i == x && j == y) && grid[i][j] == k)
        return false;

  return true;
}

int sum = 0;

void backtrack()
{
  if (done())
  {
    sum += (int)grid[0][0] * 100 + (int)grid[0][1] * 10 + (int)grid[0][2];
    return;
  }

  int min_i = 0, min_j = 0, min_cnt = 1 << 20, cnt;

  for (int i = 0; i < size; i++)
    for (int j = 0; j < size; j++)
      if (!grid[i][j])
      {
        cnt = 0;

        for (char k = 1; k <= size; k++)
          if (!used[i][j][k])
            ++cnt;

        if (cnt > 0 && cnt < min_cnt)
          min_i = i, min_j = j, min_cnt = cnt;
      }

  if (min_cnt == 1 << 20)
    return;

  for (char k = 1; k <= size; k++)
    if (!used[min_i][min_j][k] && check(min_i, min_j, k))
    {
      grid[min_i][min_j] = k;
      used[min_i][min_j][k] = 1;

      backtrack();

      used[min_i][min_j][k] = 0;
      grid[min_i][min_j] = 0;
    }
}

int main()
{
  freopen("sudoku.txt", "rt", stdin);

  for (int i = 0; i < grids; i++)
  {
    init_grid(); backtrack();
  }

  printf("%d\n", sum);

  return 0;
}

 

[mikroz]

*основанного, простите.