Solve soduko problem

fillSoduko(puzzleString) {
    const puzzleArr = puzzleString.split("")
   var _this = this;

  function fill(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) {
    return choices;
    return puzzleArr.join("")

So I have portion of code above which takes for ever to process. I have to use recursion as there was no other option. Please notify me if I am doing something wrong.

The backend thought about this class method is that it takes puzzle String and automatically fills it. It checks for empty(".") value in string and then check if any(1-9) is working for it. Ofcourse there are plenty of cells empty so we get not 1 but too many number as choice. We are then checking for each choice if it completes and validate a board or not.

Your overall logic makes sense, and the implementation seems fine too. One potential issue is splitting the puzzle string into a 1D array of 81 elements, instead of 2D array of 9 rows and 9 columns.

In your validating method getChoices() I see you had to convert the index into an object of row and column, then use a checkPlaceAndValue() method with puzzleString as an argument. I assume in that method you split puzzleString again to get the rows and columns. By this point I hope you see that exploring the sudoku even a few recursions deep would be immensely straining on both time and space, since the above is called for every single possible choice.

2D array on the otherhand, you do not have to get a separate {row,column} object, nor do you even need the checkPlaceAndValue() method. You have the rows and columns ready to go in the 2D array.

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.