数独求解函数需要永远递归

Question

class SudokuSolver {

  // check for string being sudoku
  validate(puzzleString) {
    const puzzleArr = puzzleString.split("")
    const digitCheck = puzzleArr.every( val => val.match(/[1-9]/) || val.match(/\./))
    const lengthCheck = puzzleArr.length == 81? true: false;
    const checkString = this.checkString(puzzleString)
    if(digitCheck && lengthCheck && checkString){
      return "valid"
    } 
    if(!lengthCheck){
        return "Expected puzzle to be 81 characters long"
    }
      if(!digitCheck){
        return "Invalid characters in puzzle"
      } 
    if(!checkString){
        return "Invalid puzzle string"
      } 
    }
 

  // check for string by digit.
  checkString(puzzleString){
    const puzzleArr = puzzleString.split("")
    const check = puzzleArr.every((val, index) => {
      let {row, column} = this.getRowColumn(index);
      if(val.match(/\./)){
        return true
      }
      if(val.match(/[1-9]/)){
        column += ""
        val = +val;
        const rowCheck = this.checkRowPlacement(puzzleString, row, column, val)
        const colCheck = this.checkColPlacement(puzzleString, row, column, val)
        const sqrCheck = this.checkSquareRegionPlacement(puzzleString, row, column, val)
        if(rowCheck && colCheck && sqrCheck){
          return true
        }
      }
          return false;
    })
    return check;
  }

  // check by place in array of string and returns row and column.
  getRowColumn(place){
    const value = +place
    place += ""
    let obj = {};
    place.match(/\b(9|1[0-7])\b/)? obj = {row: 'B', column: value - 8}
        : place.match(/1[8-9]|2[0-6]/)? obj = {row: 'C', column: value - 17}
        : place.match(/2[7-9]|3[0-5]/)? obj = {row: 'D', column: value - 26}
        : place.match(/3[6-9]|4[0-4]/)? obj = {row: 'E', column: value - 35}
        : place.match(/4[5-9]|5[0-3]/)? obj = {row: 'F', column: value - 44}
        : place.match(/5[4-9]|6[0-2]/)? obj = {row: 'G', column: value - 53}
        : place.match(/6[3-9]|7[0-1]/)? obj = {row: 'H', column: value - 62}
        : place.match(/7[2-9]|80/)? obj = {row: 'I', column: place - 71}
        : obj = {row: 'A', column: value + 1};
    return obj;
  }

  // check for valid inputs.
  checkValues(row, column, value){
    value += ""
    column += ""
    if(!value.match(/[1-9]/)){
        return "Invalid value"
      }
    if(!row.match(/[A-I]/) || !column.match(/[1-9]/)){
        return "Invalid coordinate"
      }
    return "fine"
  }

  // check for row(character) and return min and max value for that row.
  rowAdd(row){
    let arr;
      switch(row){
        case "A":
          arr = [0, 9];
          break;
        case "B":
          arr =  [9, 18];
          break;
        case "C":
          arr =  [18, 27];
          break;
        case "D":
           arr =  [27, 36];
          break;
        case "E":
          arr =  [36, 45];
          break;
        case "F":
          arr =  [45, 54];
          break;
        case "G":
          arr =  [54, 63];
          break;
        case "H":
          arr =  [63, 72];
          break;
        case "I":
          arr =  [72, 81];
          break;
      }
    return arr;
    }

  //check placement by row
  checkRowPlacement(puzzleString, row, column, value) {
    const [min, max] = this.rowAdd(row)
    const index = min + parseInt(column) - 1
    const puzzleArr = puzzleString.split("")
    for(let i = min; i < max; i++){
      if(puzzleArr[i] == value){
        if(i == index){
          continue
        }
        return false
      }
    }
    return true;
  }

  //check placement by col
  checkColPlacement(puzzleString, row, column, value) {
    const puzzleArr = puzzleString.split("")
    const startIndex = parseInt(column) - 1;
    const index = this.rowAdd(row)[0] + parseInt(column) - 1;
    for(let i = startIndex; i < 81; i+= 9){
      if(puzzleArr[i] == value){
        if(index == i){
          continue
        }
        return false;
      }
    }
    return true
  }

  // check for which square does the value belongs
  checkSquareRegion(row, column){
    column = +column;
    switch(row){
      case "A": case "B": case "C":
        if(column < 4){
          return "0"
        }
        if(column < 7){
          return "1"
        }
        if(column < 10){
          return "2"
        }
        ;
        
      case "D": case "E": case "F":
         if(column < 4){
          return "3"
        }
        if(column < 7){
          return "4"
        }
        if(column < 10){
          return "5"
        }
        ;
        
      case "G": case "H": case "I":
         if(column < 4){
          return "6"
        }
        if(column < 7){
          return "7"
        }
        if(column < 10){
          return "8"
        }
        ;
      default:
        return undefined
    }
  }

  // for square check of different values. return true if value does differ then others. 
  checkSquareRegionPlacement(puzzleString, row, column, value) {
    const puzzleArr = puzzleString.split("")
    const square = +this.checkSquareRegion(row,column)
    const check = this.checkValues(row, column, value)
    const index =  this.rowAdd(row)[0] + parseInt(column) - 1;
    if(check == "fine"){ 
      let startIndex = (square * 3)
      let flag = true;
      for(let i = 0; i < 3; i++){
        for(let j = startIndex; j < (startIndex + 3); j++){
          if((parseInt(puzzleArr[j]) == value)){
            if(puzzleArr[j] == puzzleArr[index]){
              continue;
            } else{
            flag = false
            }
          } else{
            continue;
          }
        }
        if(flag == false){
          break;
        }
        startIndex += 9;
      }
      if(flag){
        return true
      }
      return false;
    }else {
      return check;
    }
  }
// solve whole puzzle
  solve(puzzleString) {
    const validate = this.validate(puzzleString)
    if(validate == "valid"){
      puzzleString = this.fillSoduko(puzzleString)
    } else {
      return {error: validate};
      }
    return puzzleString;
    }

  // fill soduko.
 fillSoduko(puzzleString) {
    const puzzleArr = puzzleString.split("")
   var _this = this;
   fill(puzzleArr.indexOf(val => !val.match(/[1-9]/)))

  function fill(index){
      console.log(index)
      while (index < 81 && puzzleArr[index].match(/[1-9]/)) ++index; // skip non-empty cells
      if (index == 81) return true;               // we filled'em all, success!
      let moves = getChoices(index);
      for (let m of moves) {
        puzzleArr[index] = m;              // try one choice
        if (fill(index + 1))          // if we can solve for the next cell
            return true;               // then return true, success!
    }
      puzzleArr[index] = ".";  // no move worked; we failed, clear the cell
      return false;
    } // and backtrack

  function getChoices(index) {
    const {row, column} = _this.getRowColumn(index)
    let choices = [];
    for (let value = 1; value <= 9; ++value) {
        if (_this.checkPlaceAndValue(puzzleString, row, column, value) == true) {
            choices.push(value);
        }
    }
    return choices;
  }
    return puzzleArr.join("")
  }
  
// check for place and value of the value inserted.
  checkPlaceAndValue(puzzleString, row, column, value){
    value = +value;
    const validate = this.validate(puzzleString);
    const check = this.checkValues(row, column, value);
    if((check == "fine") && (validate == "valid")){
      const rowCheck = this.checkRowPlacement(puzzleString, row, column, value)
      const colCheck = this.checkColPlacement(puzzleString, row, column, value)
      const sqrCheck = this.checkSquareRegionPlacement(puzzleString, row, column, value)
      if(rowCheck && colCheck && sqrCheck){
        return true
      } else{
        let obj = {};
        !rowCheck ?  obj = {conflict: "row"}:
        !colCheck ?  obj = {conflict: "column"}:
        obj = {conflict: "region"};
        return obj;
      }
    } else{
      let obj = {}
      validate != "valid"? obj = {error: validate}:
        obj = { error: check};
      return obj;
    }
  }
  }

module.exports = SudokuSolver;

所以我上面有一部分代码需要永远处理。我必须使用递归，因为没有其他选择。如果我做错了什么，请通知我。

后台想到的这个class方法是取puzzle String自动填充。它检查字符串中的空（“。”）值，然后检查是否有任何（1-9）正在为它工作。当然，有很多单元格是空的，所以我们得到的不是 1，而是太多的数字可供选择。然后我们检查每个选择是否完成并验证板。

Answer 1

我注意到的第一件事是：

   fill(puzzleArr.indexOf(val => !val.match(/[1-9]/)))

应该是：

   fill(puzzleArr.findIndex(val => !val.match(/[1-9]/)))

这是一个容易犯的错误。 indexOf 是在提供的值的数组中找到第一个索引。 findIndex 是在提供的谓词函数 returns true.

中找到数组中的第一个索引

修复该问题后，我发现 checkSquareRegionPlacement 中存在错误。我没有深入研究它，但使用一个完全解决的难题并简单地删除最终值，我尝试测试一个非常简单的案例：

const complete = "172396845549287316368514297634975182927831564851462973215749638793658421486123759"
const puzzle =   "17239684554928731636851429763497518292783156485146297321574963879365842148612375."

当我们进入 checkSquareRegionPlacement 时，我们应该测试指数 60。 61、62、69、70、71、78、79、80。但是当索引 j 为 25 时，它失败了（通过设置 flag = false）。我还没有深入了解这段代码中有什么问题，但这至少可以为您指明正确的方向。

总的来说，我建议您解决更大的问题：

拼图串不断地分开。你需要一个更有用的内部格式来解决这个难题。假设这个由数字 (1 - 9) 或点 (.) 填充的 81 个字符的字符串是您需要的输入格式，那么我建议您在输入初始函数时更改这是一种更有用的格式，可以是包含 81 个字符/数字的单个数组，也可以是它们的 9 x 9 数组。如果您需要在最后转换回字符串格式，那很好。在您的初始通话开始和 return 之间，将所有内容保持为更有用的格式。

您重复执行将普通数组索引转换为逻辑网格模型并返回的工作。您可以使用如下代码预先完成一次：

const _09 = [0, 1, 2, 3, 4, 5, 6, 7, 8];
const _03 = [0, 1, 2];
const rows = _09 .map ((i) => _09 .map ((j) => 9 * i + j))
const cols = _09 .map ((i) => _09 .map ((j) => i + 9 * j))
const squares = _03 .flatMap ((i) => _03 .map ((j) => _03 .flatMap (
  (k) => _03 .map (l => 27 * i + 3 * j + 9 * k + l)
)))
const groups = Array .from ({length: 80}, (_, i) => [
  rows .find (row => row .includes (i)),
  cols .find (col => col .includes (i)),
  squares .find (square => square .includes (i))
])

然后使用这些存储的值。例如，“我可以在索引 80 处放置一个 7 吗？”变成类似 groups [80] .every (g => ! g .includes (7)) 的东西（未经测试！）。这将停止很多对行和列的摆弄。

这在 class 中，原因不明。您的方法正在它们之间传递相关数据，因此似乎没有内部状态。在我看来，这作为一个模块会更好。

还有其他问题。但总的来说，问题似乎是你工作太努力了。我认为大量的简化应该真的有帮助。

数独求解函数需要永远递归

Soduko solving function takes forever with recursion

javascript

recursion