Как отладить рекурсивную функцию в JS

Question

Я написал следующий рекурсивный код для решения головоломки судоку.

grid: глобальная матрица, представляющая головоломку.
возможная функция: возвращает true или false для заданного числа и местоположения
solve: рекурсия, заполняющая сетку.

Однако у меня есть ошибка, как я могу отладить ее, не попадая в бесконечное l oop.

Есть ли какой-нибудь принудительный выход? Вы можете обнаружить ошибку?

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

function possible(x, y, n) {
  for (let i = 0; i < 9; i++) {
    if (grid[y][i] === n) {
      return false
    }
  }
  for (let i = 0; i < 9; i++) {
    if (grid[i][x] === n) {
      return false
    }
  }
  let x0 = Math.floor(x / 3) * 3;
  let y0 = Math.floor(y / 3) * 3;
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (grid[y0 + i][x0 + j] === n) {
        return false
      }
    }
  }
  return true;
}

function solve() {
  for (let y = 0; y < 9; y++) {
    for (let x = 0; x < 9; x++) {
      if (grid[y][x] === 0) {
        for (let n = 1; n < 10; n++) {
          if(possible(y,x,n)){
            grid[y][x] = n;
            solve();
            grid[y][x] = 0;
          }
        }
        return;
      }
    }
  }
}

solve();

Answer 1

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

Рекурсия всегда требуется там быть базовым условием, которое приводит к завершению рекурсии. В вашем случае, если нет нерешенных квадратов, вы можете указать это, вернув true, а затем передать этот статус «success» вверх по цепочке вызовов.

Кроме того, ваш вызов возможного изменил ожидаемые позиции аргумента: x и y.

function solve() {
  for (let y = 0; y < 9; y++) {
    for (let x = 0; x < 9; x++) {
      if (grid[y][x] === 0) {
        for (let n = 1; n < 10; n++) {
          if(possible(x,y,n)){
            grid[y][x] = n;
            var solved = solve();
            if(solved) {
                return true;
            }
            grid[y][x] = 0;
          }
        }
        return false;
      }
    }
  }
  return true; // We didn't find any unsolved squares.
}

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

function possible(x, y, n) {
  for (let i = 0; i < 9; i++) {
    if (grid[y][i] === n) {
      return false
    }
  }
  for (let i = 0; i < 9; i++) {
    if (grid[i][x] === n) {
      return false
    }
  }
  let x0 = Math.floor(x / 3) * 3;
  let y0 = Math.floor(y / 3) * 3;
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (grid[y0 + i][x0 + j] === n) {
        return false
      }
    }
  }
  return true;
}

function solve() {
  // find the first unsolved square.
  for (let y = 0; y < 9; y++) {
for (let x = 0; x < 9; x++) {
  if (grid[y][x] === 0) {
    // try every possible number in that square
    for (let n = 1; n < 10; n++) {
      if(possible(x,y,n)){
        grid[y][x] = n;
        var solved = solve();
        // if this led to a valid board, leave the board as-is and return success.
        if(solved) {
            return true;
        }
        grid[y][x] = 0;
      }
    }
    return false;
  }
}
  }
  console.log("all squares are solved");
  return true; // We didn't find any unsolved squares.
}

console.log(solve());
console.log(grid);

Answer 2

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

В вашем коде вы вызываете solve функция, которая будет l oop от начала grid до конца. И снова функция solve вызывала себя, что вызывало l oop снова и снова ... так что она никогда не остановится, пока не произойдет переполнение стека.

В приведенном ниже коде, я уверен, я не решил Ваша головоломка судоку, но, по крайней мере, она показывает, как избежать бесконечного вызова, сообщая, где перезапустить l oop, чтобы он не повторялся снова и снова. Опять же, я не решил твою головоломку судоку .. просто демо рекурсивного характера. Я также добавил console.log, чтобы вы могли видеть, как функция solve вызывается с разными параметрами каждый раз.

function solve(ystart, xstart) {
  console.log('solve(', ystart + ',' + xstart, ')');
  for (let y = ystart; y < 9; y++) {
    for (let x = xstart; x < 9; x++) {
      if (grid[y][x] === 0) {
        for (let n = 1; n < 10; n++) {
          if(possible(y,x,n)){
            grid[y][x] = n;
            solve(y, x);
            grid[y][x] = 0;
          }
        }
        return;
      }
    }
  }
}

solve(0, 0);

Answer 3

Вы можете использовать Google Chrome Отладка для Java Сценарий

Например, вы можете создать точку останова в этом:

или установить часы для переменных:

Для использования Нажмите F12 и выберите « Источник » и найдите свой JS файл для отладки


Для Подробнее Go И Читать https://www.w3schools.com/js/js_debugging.asp