Suduko Solver Algo works but returns incorrectly?

Hi All,

I wonder if you guys could help me pass the last test of the suduko solver challenge!

I’m getting some really weird outcomes from my recursive solving algorithm, I get the full and complete puzzle string in my console log but when the recursion unravels it always returns either the default ‘Could not be solved’ case or the original puzzle string!

No console errors or misplaced syntax as far as I can see, but having wrapped a few logs in different places it looks like it’s a ‘final iteration’ error of some sort as the logs do this:

no empties: 769235418851496372432178956174569283395842761628713549283657194516924837947381625
no error: 76923541885149637243217895617456928339584276162871354928365719451692483794738162.

But my chai test outputs this :

Uncaught AssertionError: expected '..9..5.1.85.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..' to equal '769235418851496372432178956174569283395842761628713549283657194516924837947381625'
      + expected - actual

      -..9..5.1.85.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
      +769235418851496372432178956174569283395842761628713549283657194516924837947381625

Absolutely baffled on this one, tried for a few days of returning true, false, objects etc and nothing seems to be working :slight_smile:

Repl link: https://repl.it/@anilsiv/boilerplate-project-sudoku-solver

Full code in case you’d rather read it here:

  class SudokuSolver {

      validate(puzzleString) {
          //console.log(puzzleString)

          if (puzzleString.length === 0) {
              return {
                  error: 'Required field missing'
              }
          }

          if (puzzleString.length !== 81) {
              return {
                  error: 'Expected puzzle to be 81 characters long'
              }
          }

          if (!/^[0-9.]*$/.test(puzzleString)) {
              return {
                  error: 'Invalid characters in puzzle'
              };
          }

          return true

      }

      createBoard(puzzleString) {
          //create a new row on 0th or 9th iteration
          let puzzleBoard = [
              [],
              [],
              [],
              [],
              [],
              [],
              [],
              [],
              []
          ]
          let puzzle = puzzleString.split('');
          let row = -1

          for (let i = 0; i < puzzle.length; i++) {
              if (i % 9 === 0) {
                  row++
              }

              puzzleBoard[row].push(puzzle[i])

          }
          return puzzleBoard
      }

      checkRowPlacement(board, row, column, value) {

          for (let i = 0; i < 9; i++) {
              if (board[row][i] == value) {
                  return {
                      valid: false,
                      conflict: 'row'
                  }
              }
          }

          return {
              valid: true
          }

      }

      checkColPlacement(board, row, column, value) {

          for (let i = 0; i < 9; i++) {
              if (board[i][column] == value) {
                  return {
                      valid: false,
                      conflict: 'column'
                  };
              }
          }

          return {
              valid: true
          };

      }

      checkRegionPlacement(board, row, column, value) {

          let regionStartRow = parseInt(row / 3) * 3;
          let regionStartCol = parseInt(column / 3) * 3;
          for (let i = regionStartRow; i < regionStartRow + 3; i++) {
              for (let j = regionStartCol; j < regionStartCol + 3; j++) {
                  if (board[i][j] == value) {
                      return {
                          valid: false,
                          conflict: 'region'
                      }
                  }
              }
          }
          return {
              valid: true
          }
      }

      coordToBoard(input) {
          let res = [];
          // A1 -> A = 0, 1 = 0 
          res.push(input.toUpperCase().charCodeAt(0) - 65)
          res.push(parseInt(input.charAt(1)) - 1)


          return res

      }

      checkPlacement(puzzleString, coordinate, value) {
          if (!puzzleString || !coordinate || !value) {
              return {
                  error: 'Required field(s) missing'
              }
          }

          if (this.validate(puzzleString) != true) {
              return this.validate(puzzleString)
          };

          let coordSplit = coordinate.split('')

          if (!/[A-Ia-i]/.test(coordSplit[0] || !/[0-9]/.test(coordSplit[1]))) {
              return {
                  error: 'Invalid coordinate'
              }
          };

          if (value < 1 || value > 9 || isNaN(value)) {
              return {
                  error: 'Invalid value'
              }
          }

          let boardCoords = this.coordToBoard(coordinate)
          //console.log("boardCoords: " + boardCoords)

          let board = this.createBoard(puzzleString)
          //console.log(board)


          let conflicts = []

          if (this.checkRowPlacement(board, boardCoords[0], boardCoords[1], value).valid != true) {
              conflicts.push(this.checkRowPlacement(board, boardCoords[0], boardCoords[1], value).conflict)
          }

          if (this.checkColPlacement(board, boardCoords[0], boardCoords[1], value).valid != true) {
              conflicts.push(this.checkColPlacement(board, boardCoords[0], boardCoords[1], value).conflict)
          }

          if (this.checkRegionPlacement(board, boardCoords[0], boardCoords[1], value).valid != true) {
              conflicts.push(this.checkRegionPlacement(board, boardCoords[0], boardCoords[1], value).conflict)
          }
          //if value is the same as current coordinate make blank and check if valid and if so return true
          if (board[boardCoords[0]][boardCoords[1]] == value) {

              board[boardCoords[0]][boardCoords[1]] = '.'

              if (this.checkRegionPlacement(board, boardCoords[0], boardCoords[1], value).valid == true && this.checkColPlacement(board, boardCoords[0], boardCoords[1], value).valid == true && this.checkRowPlacement(board, boardCoords[0], boardCoords[1], value).valid == true) {

                  return {
                      valid: true
                  }

              }
          }

          if (this.checkRegionPlacement(board, boardCoords[0], boardCoords[1], value).valid != true || this.checkColPlacement(board, boardCoords[0], boardCoords[1], value).valid != true || this.checkRowPlacement(board, boardCoords[0], boardCoords[1], value).valid != true) {
              return {
                  valid: false,
                  conflict: conflicts
              }
          }




          return {
              valid: true
          }

      }

      findUnassignedLocation(puzzleString) {

            return puzzleString.indexOf('.')
          
          
      }

      rowColToCoord(index) {
    
      let col = (index % 9) + 1;
      let row = String.fromCharCode(parseInt(index / 9) + 65)

      
      return row + col
    }


  solve(puzzleString) {
          if (!puzzleString) {
              return {
                  error: 'Required field missing'
              }
          }
          if (this.validate(puzzleString) != true) {
              return this.validate(puzzleString)
          }
          let empty = this.findUnassignedLocation(puzzleString)

          if (empty == -1) {
            console.log('no empties: ' + puzzleString)
              return true
          } else {
            let coord = this.rowColToCoord(empty)

            for (var num = 1; num <= 9; num++) {
                if (this.checkPlacement(puzzleString, coord, num).valid ) {
                    if (!this.solve((puzzleString.substr(0, empty) + num + puzzleString.substr(empty + 1))).error) {
                      console.log('no error: ' + puzzleString)
                      return {solution: puzzleString}
                    }
                    
                }
                
            }
            console.log('Cannot be solved: ' + puzzleString)
            return {error: 'Puzzle cannot be solved'}
          }
  
  }

          
        
         

  }

  module.exports = SudokuSolver;
1 Like

Full log when running this is here:

Cannot be solved: 7692354188514763.2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
Cannot be solved: 7692354188514769.2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
Cannot be solved: 769235418851476..2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
Cannot be solved: 76923541885147...2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
Cannot be solved: 7692354188514963724321785..1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
Cannot be solved: 76923541885149637243217895617456928339582..6.62.71...9......1945....4.37.4.3..6..
no empties: 769235418851496372432178956174569283395842761628713549283657194516924837947381625
no error: 76923541885149637243217895617456928339584276162871354928365719451692483794738162.
no error: 7692354188514963724321789561745692833958427616287135492836571945169248379473816..
no error: 76923541885149637243217895617456928339584276162871354928365719451692483794738.6..
no error: 7692354188514963724321789561745692833958427616287135492836571945169248379473..6..
no error: 76923541885149637243217895617456928339584276162871354928365719451692483794.3..6..
no error: 769235418851496372432178956174569283395842761628713549283657194516924837.4.3..6..
no error: 769235418851496372432178956174569283395842761628713549283657194516924.37.4.3..6..
no error: 7692354188514963724321789561745692833958427616287135492836571945169.4.37.4.3..6..
no error: 769235418851496372432178956174569283395842761628713549283657194516..4.37.4.3..6..
no error: 76923541885149637243217895617456928339584276162871354928365719451...4.37.4.3..6..
no error: 7692354188514963724321789561745692833958427616287135492836571945....4.37.4.3..6..
no error: 76923541885149637243217895617456928339584276162871354928365.1945....4.37.4.3..6..
no error: 7692354188514963724321789561745692833958427616287135492836..1945....4.37.4.3..6..
no error: 769235418851496372432178956174569283395842761628713549283...1945....4.37.4.3..6..
no error: 76923541885149637243217895617456928339584276162871354928....1945....4.37.4.3..6..
no error: 7692354188514963724321789561745692833958427616287135492.....1945....4.37.4.3..6..
no error: 769235418851496372432178956174569283395842761628713549......1945....4.37.4.3..6..
no error: 7692354188514963724321789561745692833958427616287135.9......1945....4.37.4.3..6..
no error: 769235418851496372432178956174569283395842761628713..9......1945....4.37.4.3..6..
no error: 76923541885149637243217895617456928339584276162871...9......1945....4.37.4.3..6..
no error: 76923541885149637243217895617456928339584276162.71...9......1945....4.37.4.3..6..
no error: 76923541885149637243217895617456928339584276.62.71...9......1945....4.37.4.3..6..
no error: 769235418851496372432178956174569283395842.6.62.71...9......1945....4.37.4.3..6..
no error: 76923541885149637243217895617456928339584..6.62.71...9......1945....4.37.4.3..6..
no error: 7692354188514963724321789561745692833958...6.62.71...9......1945....4.37.4.3..6..
no error: 769235418851496372432178956174569283395....6.62.71...9......1945....4.37.4.3..6..
no error: 76923541885149637243217895617456928339.....6.62.71...9......1945....4.37.4.3..6..
no error: 769235418851496372432178956174569283.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 769235418851496372432178956174569.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 769235418851496372432178956174.69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 76923541885149637243217895617..69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 7692354188514963724321789561...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 76923541885149637243217895.1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 7692354188514963724321789..1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 769235418851496372432178...1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 76923541885149637243217....1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 7692354188514963724321.....1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 769235418851496372432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 7692354188514963.2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 769235418851496..2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 76923541885149...2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 7692354188514....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 76923541885.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 76923541.85.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 769235.1.85.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 7692.5.1.85.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 769..5.1.85.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 7.9..5.1.85.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: ..9..5.1.85.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
1 Like

This can be tricky to wrap head around, but the output is actually telling part of the story.

Let’s start from line no empties:, this means that base case is reached, puzzle is solved, and solution can be returned. In above code true is returned, while on the repl, it’s {solution: puzzleString}.
Both of these can be valid, depending on what later happens with it. Going further then.

                    if (!this.solve((puzzleString.substr(0, empty) + num + puzzleString.substr(empty + 1))).error) {
                      console.log('no error: ' + puzzleString)
                      return {solution: puzzleString}
                    }

After base case is reached, and result returned, true or {solution: puzzleString} doesn’t have .error attribute, so “no error”, with current puzzleString is printed to console and then returned.
This goes on, up to first recursive call, where puzzleString is the initial:

..9..5.1.85.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..

That string is returned as json for the /api/solve call made from getSolved. As it doesn’t differ from the input string, then it’s not visible, that something was filled.

Hope this points you in the right direction.

Thanks for your time sanity, it’s appreciated!

I guess this means in theory I should be able to preclude that with either of these:

            for (var num = 1; num <= 9; num++) {
                if (this.checkPlacement(puzzleString, coord, num).valid && empty != -1) {
                    if (!this.solve((puzzleString.substr(0, empty) + num + puzzleString.substr(empty + 1))).error && empty != -1) {
                      console.log('no error: ' + puzzleString)
                      return {solution: puzzleString}
                    }
                    
                }
                
            }

To return to the calling function based on the logic empty == -1 but this still fires the “no error” function, which makes me think I am not calling the function correctly for the final time when error == -1 !

I’ll keep hunting, thank you for the effort anyhow!

Yes, up to the point where solution is found everything is okay.

Keep in mind how recursion works, first it’s going deeper in the recursive calls, until base case is reached, then everything goes back in the reverse order. Going deeper with each step makes solution closer, until it’s found, but does that mean all previous recursive calls are aware what exactly that solution is?

Managed to get it sorted Sanity - for anyone else making a similar mistake I was, here’s the code:


        if (empty == -1) {
            console.log('no empties: ' + puzzleString)
            return {
                solution: puzzleString
            }
        } else {
            let coord = this.rowColToCoord(empty)

            for (var num = 1; num <= 9; num++) {


                if (this.checkPlacement(puzzleString, coord, num).valid) {

                    let result = this.solve((puzzleString.substr(0, empty) + num + puzzleString.substr(empty + 1)));
                    if (!result.error) {
                        return result; // Return what you got from the recursive call (the solution)
                    }
                }
            }
            return {
                error: 'Puzzle cannot be solved'
            }

The issue was the return value from the recurring function was passing back the puzzle string, it wasn’t passing back the solution through the stack but the original string!!

Thanks again for the hints Sanity.

1 Like