Определить, можно ли решить судоку в JavaScript - PullRequest
Новая
       10

Определить, можно ли решить судоку в JavaScript

7 голосов
/ 22 мая 2019

Это проблема от Прампа. Мне нужно определить, разрешима судоку или нет (не как вопрос LEET-кода, где мне просто нужно посмотреть, действительна ли доска или нет).

Ниже приведен мой код на JavaScript с использованием рекурсии. Я следую логике, предложенной в Pramp, которая заключается в создании вспомогательной функции getCandidates () для поиска всех номеров кандидатов, которые могут идти в пустое пространство. Затем в действительной функции sudokuSolve () найдите пустое пространство с наименьшим набором кандидатов, введите этих кандидатов в пустое пространство, а затем попытайтесь найти доску с помощью рекурсии. Если это работает, плата разрешима.

Мой код дает значение true каждый раз, и я не могу найти проблему. Я исследовал другие подобные вопросы, задаваемые в Интернете, но большинство из них предназначены для нахождения точного решения для доски судоку или для создания доски судоку. Мне просто нужно посмотреть, разрешима ли доска или нет. Если бы вы могли сказать мне, где мой код не так, я бы очень признателен.

Прямо сейчас я получаю "истину" каждый раз, независимо от контрольного примера ... Для этого предоставленного контрольного примера ответ должен давать ложь. 

const test02 = [
  ['.', '8', '9', '.', '4', '.', '6', '.', '5'],
  ['.', '7', '.', '.', '.', '8', '.', '4', '1'],
  ['5', '6', '.', '9', '.', '.', '.', '.', '8'],
  ['.', '.', '.', '7', '.', '5', '.', '9', '.'],
  ['.', '9', '.', '4', '.', '1', '.', '5', '.'],
  ['.', '3', '.', '9', '.', '6', '.', '1', '.'],
  ['8', '.', '.', '.', '.', '.', '.', '.', '7'],
  ['.', '2', '.', '8', '.', '.', '.', '6', '.'],
  ['.', '.', '6', '.', '7', '.', '.', '8', '.']
];

function getCandidates(board, row, col) {
  const candidates = [];

  for (let chr = 1; chr <= 9; chr++) {
    let collision = false;
    for (let i = 0; i < 9; i++) {
      if (
        board[row][i] == chr ||
        board[i][col] == chr ||
        board[row - (row % 3) + Math.floor(i / 3)][
          col - (col % 3) + Math.floor(i / 3)
        ] == chr
      ) {
        collision = true;
        break;
      }
    }

    if (!collision) {
      candidates.push(chr);
    }
  }
  return candidates;
}

function sudokuSolve(board) {
  let row = -1;
  let col = -1;
  let candidates = [];

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      if (board[r][c] === '.') {
        newCandidates = getCandidates(board, r, c);
        if (
          candidates.length === 0 ||
          newCandidates.length < candidates.length
        ) {
          candidates = newCandidates;
          row = r;
          col = c;
        }
      }
    }
  }
  if (candidates.length === 0) {
    return true;
  } else {
    let solvable = false;
    candidates.forEach(val => {
      board[row][col] = val;
      if (sudokuSolve(board)) {
        solvable = true;
      } else {
        board[row][col] = '.';
      }
    });
    return solvable;
  }
}
console.log(
  sudokuSolve(test02)
);

1 Ответ

1 голос
/ 22 мая 2019

Проблема будет в вашей строке: 

if (candidates.length === 0) {
    return true;

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

a) Головоломка была полностьюрешено без неизвестного "."оставшиеся квадраты (в этом случае, да, верните true)

b) Головоломка стала неразрешимой, а оставшиеся "."квадраты не имеют никаких допустимых значений

Поскольку вы возвращаете "true" для обоих из них, будет казаться, что все решено.

Попробуйте добавить логическое значение, чтобы определить, есть ли "."квадраты остаются, и используйте их вместо этого в вашем условии «если»: 

let allSquaresFilled = true;
for (let r = 0; r < 9; r++) {
  for (let c = 0; c < 9; c++) {
    if (board[r][c] === '.') {
        allSquaresFilled = false;


if (allSquaresFilled) {
    return true;
...