Судоку Решатель: Проблема с заполнением определенных ячеек - PullRequest
Новая
       53

Судоку Решатель: Проблема с заполнением определенных ячеек

1 голос
/ 25 мая 2020

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

Вот стартовая доска: 

let sudoku = [[6, 0, 5, 7, 0, 0, 1, 3, 2],
              [7, 0, 0, 6, 0, 0, 5, 0, 8],
              [0, 1, 9, 3, 0, 0, 0, 0, 4],
              [0, 2, 0, 0, 0, 3, 0, 0, 0],
              [0, 7, 3, 9, 0, 0, 2, 5, 0],
              [0, 5, 1, 2, 0, 0, 0, 0, 9],
              [5, 0, 8, 0, 0, 0, 0, 2, 0],
              [0, 4, 0, 0, 7, 6, 9, 1, 5],
              [0, 9, 0, 0, 4, 0, 6, 8, 0]];

Вот результат 

[[6, 8, 5, 7, 9, 4, 1, 3, 2],
 [7, 3, 2, 6, 1, 0, 5, 9, 8],
 [0, 1, 9, 3, 2, 5, 7, 6, 4],
 [4, 2, 6, 1, 5, 3, 8, 7, 0],
 [8, 7, 3, 9, 6, 0, 2, 5, 1],
 [0, 5, 1, 2, 8, 7, 3, 4, 9],
 [5, 6, 8, 0, 3, 1, 4, 2, 7],
 [2, 4, 0, 8, 7, 6, 9, 1, 5],
 [1, 9, 7, 5, 4, 2, 6, 8, 3]]

0 s - пробелы. Как видите, этот результат не является решенной головоломкой судоку.

Вот мой текущий алгоритм: 

let sudoku = [[6, 0, 5, 7, 0, 0, 1, 3, 2],
              [7, 0, 0, 6, 0, 0, 5, 0, 8],
              [0, 1, 9, 3, 0, 0, 0, 0, 4],
              [0, 2, 0, 0, 0, 3, 0, 0, 0],
              [0, 7, 3, 9, 0, 0, 2, 5, 0],
              [0, 5, 1, 2, 0, 0, 0, 0, 9],
              [5, 0, 8, 0, 0, 0, 0, 2, 0],
              [0, 4, 0, 0, 7, 6, 9, 1, 5],
              [0, 9, 0, 0, 4, 0, 6, 8, 0]];

function possibleCandidate(x, y, n) {
  for(let i = 0; i < sudoku[y].length; i++) {
    if(sudoku[y][i] == n) {
      return false;
    }
  }

  for(let i = 0; i < sudoku.length; i++) {
    if(sudoku[i][x] == n) {
      return false;
    }
  }

    // For 3x3 squares
    let baseX = Math.floor(x / 3) * 3;
    let baseY = Math.floor(y / 3) * 3;

    for(let a = 0; a < 3; a++) {
      for(let b = 0; b < 3; b++) {
        // add incremented values until reaching 3 to check if the value we are checking for is in the square
        if(sudoku[baseY + a][baseX + b] == n) {
          return false;
        }
      }
    }

    return true;
}

function solve() {
  let prev = [];
  let tried;
  for(let i = 0; i < sudoku.length; i++) {
    for(let j = 0; j < sudoku[i].length; j++) {
      if(sudoku[i][j] == 0) {
        for(let l = 0; l < 10; l++) {

          if(possibleCandidate(j, i, l) && l !== tried) {
            if(j == 4 && i == 0) {
              console.log(l);
            }
            prev = [i, j];
            tried = l;
            sudoku[i][j] = l;
            break;
          }
        }
        // return;
      }
    }
  }
  return true;
}

possibleCandidate(1, 0, 6);
solve();
console.log(sudoku);

EDIT:

Функция possibleCandidate() работает правильно, я думаю, проблема связана именно с функцией solve().

1 Ответ

2 голосов
/ 25 мая 2020

Проблема в том, что ваш алгоритм «жадный»: вы предполагаете, что если значение равно возможно , оно должно быть правильным . Это неверно.

В примере судоку, при достижении строки 1, столбца 2 происходит ошибка. Алгоритм решает, что туда можно поместить 2. Но он игнорирует то, что 4 также могут быть помещены туда. Что это из двух? Что ж, 4 не может быть размещено в другом свободном квадрате в этом поле 3x3 (в строке 3, столбце 1), поэтому 4 может быть помещено только в строку 1, столбец 2, тем самым исключая вариант размещения 2 там.

Следовательно, ваш алгоритм (намного) слишком оптимистичен c. Следует рассмотреть и другие альтернативы. Есть много решателей. Даже на Stack Overflow вы сможете их найти. Они основаны на рекурсии и отслеживании с возвратом.

Итак, вам нужно перебрать все значения, которые проходят проверку possibleCandidate, а затем рекурсивно вызвать функцию для следующего открытого квадрата доски. Если этот рекурсивный вызов возвращается с индикацией сбоя, продолжайте l oop, чтобы найти другие значения, которые проходят проверку possibleCandidate, и снова вызовите функцию рекурсивно ... до тех пор, пока она не вернет успех.

A рекурсивная функция перестанет делать рекурсивный вызов, когда либо:

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

  • ни одно из значений, прошедших тест possibleCandidate, не получит успеха из рекурсивного вызова. В этом случае функция возвращает ошибку вызывающей стороне, которая затем продолжит свои собственные l oop, ... et c.

Вы также можете найти решения в стеке Переполнение, например в Python.

...