Sudoku solver feedback

Code Feedback
1

I have to admit that this has my brain in knots. I have a recursive backtracking algorithm which works but I don’t fully understand why it does. I’ve yet to find an explanation (which I understand) of exactly how the recursion and backtracking code works in practice. Can anyone explain in simple terms how the following solve function actually works?

// grid is a 2D array (row-by-row representation of sudoku grid)
solve(grid) {
  // findNextEmpty returns grid coordinates or [-1, -1] if no empties
    let emptyCell = this.findNextEmpty(grid),
      row = emptyCell[0],
      column = emptyCell[1];
  // if no empty cell grid is solved - return as a string
    if (row == -1) return this.gridToString(grid);

    for (let value = 1; value < 10; value++) {
      if (this.checkValue(grid, row, column, value)) {
        grid[row][column] = value;
        this.solve(grid);
      }
    }

   // if there is an empty cell reset current cell to 0
    if (this.findNextEmpty(grid)[0] != -1) grid[row][column] = 0;

  // if solved return as string else return false
    return /^[1-9]{81}$/.test(this.gridToString(grid))
      ? this.gridToString(grid)
      : false
  }
2

We have blurred this solution so that users who have not completed this challenge can read the discussion in this thread without giving away the solution.

2 Likes
3

I have moved your question to its own thread as the post you were responding to was quite old.

1 Like
4

Well, going through your code I found a few things that are a little confusing so not going to explain your exact code and what it does, but here is the basics…

The beauty of recursion is that you just handle a little piece of the problem, then recall the function to handle the rest of the problem.

So in the Sudoku solver, this is done by calling your solve function recursively… It’s a pretty messy thing to explain in english, but basically the steps look like this:

  1. Find an empty cell (if all cells are filled in, your puzzle is solved)

  2. Assign 1 to that cell if fits there (doesn’t conflict with other already completed cells)
    (If 1 doesn’t work, then try 2, etc until you
    find a workable number for that empty cell…
    if you can’t find a workable number, then it returns false)

  3. Now, call solve on the grid again with that empty cell now filled in
    (This will start at step 1 again with whats left of the puzzle…
    it repeats this until it either fills in every blank in the grid, or
    it gets to a point where it finds a blank spot where 1-9 doesn’t
    fit in the cell meaning it can’t solve the puzzle)

  4. That call to solve in step 3 will either return a completed puzzle, in which case you’ve solved it, or will return false in which case you try the next workable number from step 2

  5. This will continue until you’ve found a solved puzzle, or you’ve tried every number, and return false as not solved.

Its a very brute-force attack, trying many different possible combinations until it finds one that works… to illustrate this maybe more clearly lets look at a simpler example such as a combination solver.

Say we want a program that will find the correct 3 digit combination to a safe… say the combination is 352… and you can’t repeat the same number twice, like 111, and can’t use 0… we’ll use 0 to represent an empty spot like in your Sudoku.

So using the same kind of solver as illustrated above we will follow the steps:

  • call solve on 000
  • pick the first empty spot, and assign it 1 if it fits, that gives us 100
  • call solve on 100 (the recursion)
  • pick the first empty spot (which would be the second number) and assign it 1… oh wait, that conflicts because we can’t repeat numbers, so assign it 2, for 120
  • call solve on 120
  • pick the first empty spot and assign it 1… oh wait, 2… oh wait 3… now 123…
  • call solve on 123
  • there are no empty slots left… but this was an incorrect answer, return false
  • that takes us back to the solver called on 120 (the backtracking)… and since putting a 3 in the empty slot didn’t work, try the next number, so 124
  • call solve on 124
  • there are no empty slots left… but this was an incorrect answer, return false
  • try 125… nope…
  • try 126… nope…

This will continue up to 129… at which point its tried all workable numbers and didn’t solve the puzzle. It will return false for incorrect answer, and return false since it tried every number unsuccessfully, backtracking us back to where you called solve on 100, and will try the next number in the next empty slot, so 130. Solve on 130 will keep going until it tried every number up to 139… and when that doesn’t work, it will go to 140. When it gets to 198 and still doesn’t have an answer, its tried every number in the second and third slots unsuccessfully, so now will return false all the way back to the solve you called on 000… at which point since solve 100 didn’t work… it will try solve 200. This will continue in this fashion until it gets to 352 at which point the since it found a correct answer, it will return the answer(instead of false), which will return the answer, which will return the answer all the way back to your original call of solve (this is why a call to solve either returns false, or the completed puzzle).

Very brute-force, but if there is a valid answer, it will find it. In this example it checked if the combination was right after there are no remaining slots, but in your Sudoku solver, it will backtrack anytime it gets to an empty square that it can’t assign a 1-9 because it conflicts with other cells already assigned.

It’s actually fun to watch this method at work… in your Sudoku solver, you can watch how it works by printing your grid string to console every time you assign a number to the grid (warning: this will print thousands of lines to your console). You’ll be able to watch as your program fills in the grid, usually almost completely, before it hits a conflict and has to backtrack sometimes almost all the way to the beginning to try the next number. Very interesting… or maybe I’m just easily entertained.

I hope this helps a bit. It’s late, so this might just be incoherant babbling.

2 Likes
5

Thanks for your very detailed reply - I appreciate your help!
I conceptually understand recursion (a simple example being an n! function).
I also conceptually understand backtracking and other methods which can be applied to sudoku solving.
What I didn’t understand is exactly what my code does in practice at the point of recursion/backtracking (i.e. within the for loop).
I think my brain has mostly untangled now!

Here’s how (I think) it works:

  1. Invoke solve function.
  2. Find first empty cell and assign first valid value
  3. Invoke solve on updated grid (call it solve2)

Let’s say that there are no possible values for second empty cell given the value we’ve assigned to the first cell.

  1. solve2 exits the for loop and checks if there are empty cells remaining. As there are, current cell is reset to zero (isn’t it already zero as no value has yet been successfully assigned to it)?
  2. Ternary operator checks if puzzle is solved and returns false as it isn’t.
  3. Control passes back to initial solve, which now iterates the for loop to find the next valid value.
  4. Rinse and repeat recursive function until at any point in any of the recursive calls the base case (no remaining empty cells) is reached, at which point the solution is returned.
  5. In case where there is no possible solution at all, the entire solve returns false and we can return ‘puzzle cannot be solved’ error in res.json.

I don’t understand step 4. All I know is that the function doesn’t work without it.
What am I misunderstanding?

6

Wait… I get it now.

I didn’t go deep enough into the recursive loop in my head.
If a valid value were found for solve2 but then not for solve3, and then revisiting solve2 to increment to find a second alternative valid value fails, we need to reset the solve2 value, so that we can then go back to increment solve1 and revisit solve2 afresh.

It makes sense now!

1 Like
7

Picking up on the discussion in your original thread on this topic, the idea of gold-plating is one which I find interesting in this project.

My project solution fulfils all necessary criteria and passes all tests. For any valid submitted string a solution will be found (if the string is solvable). The brute force algorithm and validity checks are flawed in many respects though.

Possible improvements:

  1. A validity check which rejects any string for which there is more than one solution. At present you could present an empty string (i.e. 81 dots) and the solver would return the first of a great many solutions. A legitimate sudoku puzzle MUST contain minimum 17 givens to have a unique solution.
  2. There are countless algorithms which can solve more efficiently than any brute force attempt (e.g. using stochastic methods)
  3. Improving UI so user can input values directly on Sudoku grid, rather than via string input.
  4. Highlighting conflicts directly on the grid as values are input, rather than returning json errors.

Obviously, some of these improvements would render the project a fail within the given FCC constraints, so it’s something to revisit after successful project submission.

1 Like
8

Hello @igorgetmeabrain,
Where is the rest of the code? ( I’m getting a
Unexpected token '{' and let emptyCell = this.findNextEmpty(grid) is not a function when I try to execute the code).

When you don’t understand what the code is doing, you can use a debugger or Python tutor:

As you can see, Python tutor is more “visual”.

https://pythontutor.com/javascript.html#mode=edit

In general, when this happens it is because there is an incomplete mental model of how JS is executed. A step by step execution is a good idea when do you don’t understand the code, this is an answer that I wrote about recursion (a different exercise). Maybe can help you:

Use Recursion to Create a Countdown - Understanding - #3 by Diego_Perez

Cheers and happy coding :slight_smile:

1 Like
9

Yeah, I didn’t include the code for the other functions. I tried to annotate to show what they return, so that the solve function could be understood in isolation.

I haven’t really done much with Python yet but have a few of those projects coming up…

Thanks for the advice - always happy to learn as much as I can from other people!

10

Python tutor is the name of the app, if you watch the video you can see that the code is JS. Also the the answer (for the recursive exercise) was created using python tutor.

11

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