Как сохранить возврат рекурсивной функции в переменную?

Я написал JavaScript, чтобы решить головоломку судоку с возвратом. Моя цель - сохранить решение в переменной. Прямо сейчас я могу назвать решение только один раз.

var grid = [
  [0,1],
  [1,0]
]

function solve() {
  /// ... the recursive function that change the value of the grid variable.
  data = console.log(grid);
  return data;
}

var result = solve();

console.log(result);

Мой ожидаемый результат для console.log(result) - [[0,1], [1,0]], но вместо этого результат undefined.

=== tl:dr

the sudoku solver in javascript 

/// a string of digits, 1 - 9, and '.' as spaces. Each character represent a square, e.g.,
/// 5 3 . | . 7 . | . . .
/// 6 . . | 1 9 5 | . . .
/// . 9 8 | . . . | . 6 .
/// ------+-------+------
/// 8 . . | . 6 . | . . 3
/// 4 . . | 8 . 3 | . . 1
/// 7 . . | . 2 . | . . 6
/// ------+-------+------
/// . 6 . | . . . | 2 8 .
/// . . . | 4 1 9 | . . 5
/// . . . | . 8 . | . . .

var 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(r,c,n) {
  /// check the row
  for (let i=0;i<9;i++) if (grid[r][i] == n) return false;
  /// check the column
  for (let i=0;i<9;i++) if (grid[i][c] == n) return false;
  /// check the 3x3 grid
  let r0 = Math.floor(r/3)*3;
  let c0 = Math.floor(c/3)*3;
  for (let i=0;i<3;i++) {
    for (let j=0;j<3;j++) {
      if (grid[r0+i][c0+j] == n) return false;
    }
  }
  /// all check passed
  return true;
}

function solve() {
    for (let r=0;r<9;r++) {
      for (let c=0;c<9;c++) {
        /// check grid with value of 0
        if (grid[r][c] === 0) {
          /// check for possible solution
          for (let n=1;n<10;n++) {
            if (possible(r,c,n)) { 
              /// there is a possibility of the selected solution is a bad one.
              /// to solve this, use backtracking: try -> if it turns out the solution is a bad one, we go back to 0.
              grid[r][c] = n;
              /// recursion
              solve();
              grid[r][c] = 0;
            }
          }
          /// if there is no solution, we have to return.
          return;
        }
      }
    }
  data = console.log(grid);
  return data;
}

var result = solve()
console.log(result)

изменить: использование JSON.stringify и вызов функции solve() выводит решение один раз, но результат по-прежнему не сохраняется в переменной.

...
      data = console.log(JSON.stringify(grid));
      return data;
    }
    
    var result = solve()
    console.log(result)

javascript recursion backtracking recursive-backtracking
person kidfrom    schedule 28.07.2020    source источник
comment
console.log всегда возвращает undefined, так что это то, что вы назначаете здесь data = console.log(grid);. Так что не делайте этого, а делайте прямо data = grid. Хотя вам может потребоваться сделать глубокий клон grid в какой-то момент, если вы постоянно его меняете.   -  person VLAZ    schedule 28.07.2020
comment
@VLAZ Я изменил console.log(grid) на data = grid и вызвал console.log(data) вне функции. Результатом является исходная сеточная переменная, чего не ожидалось.   -  person kidfrom    schedule 28.07.2020

Ответы (3)


arrow_upward
1
arrow_downward

У вас нет проверки, завершили ли вы. Если вы хотите вернуть сетку, вам следует проверить, завершена ли она, прежде чем возвращаться. Для этого имеет смысл передать сетку в качестве параметра solve как извне, так и из рекурсивного вызова, а также possible. А написать isSolved функцию довольно тривиально. Я бы просто использовал const isComplete = grid => grid.every(row => !row.includes(0)), но в приведенном ниже примере показан еще один, похожий на остальной код. Эти минимальные изменения должны заставить его работать на вас:

function possible(grid, r,c,n) {
  /// check the row
  for (let i=0;i<9;i++) if (grid[r][i] == n) return false;
  /// check the column
  for (let i=0;i<9;i++) if (grid[i][c] == n) return false;
  /// check the 3x3 grid
  let r0 = Math.floor(r/3)*3;
  let c0 = Math.floor(c/3)*3;
  for (let i=0;i<3;i++) {
    for (let j=0;j<3;j++) {
      if (grid[r0+i][c0+j] == n) return false;
    }
  }
  /// all check passed
  return true;
}

// or just
// const isComplete = grid => grid.every(row => !row.includes(0))
const isComplete = function(grid) {
  return grid.every(function (row) {
    return row.every(function (cell) {
      return cell !== 0
    })
  })
} 

function solve(grid) {
    for (let r=0;r<9;r++) {
      for (let c=0;c<9;c++) {
        /// check grid with value of 0
        if (grid[r][c] === 0) {
          /// check for possible solution
          for (let n=1;n<10;n++) {
            if (possible(grid,r,c,n)) { 
              grid[r][c] = n;
              /// recursion
              grid = solve(grid) || grid; // keep the original if the recursive call returns nothing
              if (isComplete(grid)) {return grid} // *** This is what was really missing ***
              // backtrack
              grid[r][c] = 0;
            }
          }
          /// if there is no solution, we have to return.
          return;
        }
      }
    }
}

var 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],
];

var result = solve(grid)
console.log(result.map(r => r.join('')).join('\n')) // Format the output more readably
.as-console-wrapper {max-height: 100% !important; top: 0}

person Scott Sauyet    schedule 28.07.2020

arrow_upward
0
arrow_downward

Вы назначаете переменные данные функции console.log (), которая возвращает не объект. Вместо этого вы должны вернуть значение сетки из функции.

var grid = [
  [0,1],
  [1,0]
]

function solve() {
  /// ... the recursive function that change the value of the grid variable.
  return grid;
}

var result = solve();

console.log(result);

это должно решить проблему.

person Akshat Raj    schedule 28.07.2020
comment
Спасибо за новые знания. Я применил его к коду решателя судоку, return grid вместо return data. Результат по-прежнему undefined. - person kidfrom; 28.07.2020
comment
Какого результата вы ожидаете. - person Akshat Raj; 28.07.2020
comment
Я ожидаю, что на выходе будет обработанное значение объекта sudoku solution переменной сетки. - person kidfrom; 28.07.2020

arrow_upward
0
arrow_downward

Это устраняет ошибку

/// a string of digits, 1 - 9, and '.' as spaces. Each character represent a square, e.g.,
/// 5 3 . | . 7 . | . . .
/// 6 . . | 1 9 5 | . . .
/// . 9 8 | . . . | . 6 .
/// ------+-------+------
/// 8 . . | . 6 . | . . 3
/// 4 . . | 8 . 3 | . . 1
/// 7 . . | . 2 . | . . 6
/// ------+-------+------
/// . 6 . | . . . | 2 8 .
/// . . . | 4 1 9 | . . 5
/// . . . | . 8 . | . . .

var 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(r,c,n) {
  /// check the row
  for (let i=0;i<9;i++) if (grid[r][i] == n) return false;
  /// check the column
  for (let i=0;i<9;i++) if (grid[i][c] == n) return false;
  /// check the 3x3 grid
  let r0 = Math.floor(r/3)*3;
  let c0 = Math.floor(c/3)*3;
  for (let i=0;i<3;i++) {
    for (let j=0;j<3;j++) {
      if (grid[r0+i][c0+j] == n) return false;
    }
  }
  /// all check passed
  return true;
}

function solve() {
    for (let r=0;r<9;r++) {
      for (let c=0;c<9;c++) {
        /// check grid with value of 0
        if (grid[r][c] === 0) {
          /// check for possible solution
          for (let n=1;n<10;n++) {
            if (possible(r,c,n)) { 
              /// there is a possibility of the selected solution is a bad one.
              /// to solve this, use backtracking: try -> if it turns out the solution is a bad one, we go back to 0.
              grid[r][c] = n;
              /// recursion
              solve();
              grid[r][c] = 0;
            }
          }
          /// if there is no solution, we have to return.
          return;
        }
      }
    }
  console.log(grid);
  

}
 
 var result = solve()


/// Difficulty represent the number of squares with digits.
/// "easy":      62
/// "easy-2":    53
/// "easy-3":    44
/// "medium":    35
/// "hard":      26
/// "very-hard": 17

person Akshat Raj    schedule 28.07.2020
comment
Если вы вызываете переменную результата с console.log(result), на выходе будет undefined, а ожидаемый возврат - это обработанное значение объекта sudoku solution переменной сетки. - person kidfrom; 28.07.2020