Отслеживание судоку с возвратом со счетчиком решений - PullRequest
Новая
       62

Отслеживание судоку с возвратом со счетчиком решений

4 голосов
/ 28 мая 2020

Фон

Я реализовал алгоритм решения судоку (обратное отслеживание), который выглядит следующим образом: 

//Backtracking-Algorithm
public static boolean solver(int[][] board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == 0) {
                for (int n = 1; n < 10; n++) {
                    if (checkRow(board, i, n) && checkColumn(board, j, n) && checkBox(board, i, j, n)) {
                        board[i][j] = n;
                        if (!solver(board)) {
                            board[i][j] = 0;
                        } else {
                            return true;
                        }
                    }
                }
                return false;
            }
        }
    }
    return true;
}

Это решение работает нормально (оно может решать судоку).

Чего я пытаюсь достичь

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

То, что я пробовал

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

// Backtracking-Algorithm
public int solver(int[][] board, int count) { //Starts with count = 0
  if (count < 2) {
    for (int i = 0; i < GRID_SIZE; i++) {
      for (int j = 0; j < GRID_SIZE; j++) {
        /*
         * Only empty fields will be changed
         */
        if (board[i][j] == EMPTY) {
          /*
           * Try all numbers between 1 and 9
           */
          for (int n = 1; n <= GRID_SIZE; n++) {
            /*
             * Is number n safe?
             */
            if (checkRow(board, i, n) && checkColumn(board, j, n) && checkBox(board, i, j, n)) {
              board[i][j] = n;
              if (solver(board, count) > count) {
                count++;
              } else {
                board[i][j] = 0;
              }
            }
          }
          return count;
        }
      }
    }
    return count + 1;
  }
  return count;
}

Проблема в том, что count всегда переходит на «1», а затем алгоритм останавливается.

Вопрос

Какие изменения в коде необходимы, чтобы он заработал?

Ответы [ 2 ]

3 голосов
/ 28 мая 2020

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

Допустим, это последняя строка вашего судоку (где вам не хватает последнего значения), и ваш счет в настоящее время равен 0 (т.е. пока нет решения): 

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 |

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

При рекурсивном вызове ваш код не найдет никаких пустых значений, поэтому он увеличит счетчик на 1 (так что счетчик теперь равен 1) и вернет, в частности, эту строку: return count + 1; Поскольку вы не делаете никаких дальнейших рекурсивных вызовов в этот момент, увеличенный счетчик будет пропустили рекурсивный стек, и в итоге вы получите значение 1.

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

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

Вы не можете увеличить последнюю ячейку, потому что она уже на 9, поэтому вы устанавливаете ее на 0 / EMPTY и go на предыдущее значение. Предыдущее значение - 8, которое может быть увеличено до 9, поэтому вы делаете это, а затем решаете эту доску: 

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 0 |

Возможно, это не возвращает решение, поэтому вы go верните еще одно ( установка второй последней ячейки на 0 и увеличение предыдущей ячейки: 

| 1 | 2 | 3 | 4 | 5 | 6 | 8 | 0 | 0 |

Теперь посмотрим, дает ли это решение. И так далее ...

TL; DR: как только вы найдете решение , вам необходимо передать его обратно в свой код с более жесткими ограничениями (т.е. принудительно увеличить одно из допустимых значений и посмотреть, дает ли оно еще одно решение).

0 голосов
/ 28 мая 2020

Благодаря этому ответу Азиза Сонаваллы, я думаю, что понял это.

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

Код выглядит так: 

// Backtracking-Algorithm
public int[][] board2 = new int[GRID_SIZE][GRID_SIZE];

public int solver(int[][] board, int count) { // Starts with count = 0

    for (int i = 0; i < GRID_SIZE; i++) { //GRID_SIZE = 9

      for (int j = 0; j < GRID_SIZE; j++) {

        /*
         * Only empty fields will be changed
         */

        if (board[i][j] == EMPTY) { //EMPTY = 0

          /*
           * Try all numbers between 1 and 9
           */

          for (int n = 1; n <= GRID_SIZE && count < 2; n++) {

            /*
             * Is number n safe?
             */
            if (checkRow(board, i, n) && checkColumn(board, j, n) && checkBox(board, i, j, n)) {

              board[i][j] = n;
              int cache = solver(board, count);
              if (cache > count) {
                count = cache;
                for (int k = 0; k < board.length; k++) {
                  for (int l = 0; l < board.length; l++) {
                    if (board[k][l] != EMPTY) {
                      board2[k][l] = board[k][l];
                    }

                  }
                }

                board[i][j] = EMPTY;

              } else {
                board[i][j] = EMPTY;
              }

            }
          }
          return count;
        }
      }
    }
    return count + 1;
}

Решение теперь сохранено в массиве board2.

Эта реализация работает по назначению (насколько мне известно). Если вы обнаружите ошибки, оставьте, пожалуйста, комментарий.

...