4

I have written an algorithm for generating a Sudoku board but it is failing. I have written it based on this though it does differ as I had written a lot of my code before I stumbled upon this.

The Code

I have a multidimensional array set up for holding the values called matrix. matrix consists of 9 arrays which are the rows and each of these hold the 9 columns. So to get the value at row 4 column 7 I would use

matrix[3][6];

The function for solving all the squares:

var populateMatrix = function() {
    var possibles = generatePossibleNumbersArray();
    var found = false;
    for(var i=0; i< matrix.length; i++) {
        for(var j=0; j< matrix[i].length; j++) {
            while(possibles[i][j].length > 0) {
                var rnd = Math.floor(Math.random() * possibles[i][j].length);
                var num = possibles[i][j].splice(rnd, 1)[0];
                if(isValid(i, j, num)) {
                    matrix[i][j] = num;
                    found = true;
                    break;
                } else {
                    found = false;
                    continue;
                }
            }
            if(!found) {
                possibles[i][j] = [1,2,3,4,5,6,7,8,9];
                j -= 2;
            }
        }
    }
}   

The generatePossibleNumbersArray() is just a helper function for creating a multidimensional array exactly like matrix except it is initialised to hold an array of integers 1-9 for each cell. During the populateMatrix() function these possible numbers get whittled down for each cell.

The Problem

It fails before completing the matrix every time because j ends up being -1. This is because as more cells get solved it becomes harder for the algorithm to find a value for a cell so it backtracks. But it eventually ends up backtracking all the way back until j == -1.

I really thought this algorithm would work and I've spent all day trying to get my head around this but I'm stumped so any light anyone could shed on this would be very much appreciated.

I thought 'I know, I'll write a javascript function for solving Sudoku. How hard can it be?'. How wrong I was.


[SOLUTION]

Based on a comment by @Steve314 (which he's now deleted!) I added matrix[i][j] = undefined into the if(!found) { ... and the algorithm now works and is lightening fast.

If anyone is interested, here is the complete code.

5
  • So the code works or does not solves the matrix in a reasonable amount of time? Commented Jul 24, 2011 at 20:04
  • @João The code fails because the loop counter j ends up as -1 and matrix[i][j] is then undefined. Commented Jul 24, 2011 at 20:18
  • Isn't that normal? It's like saying that you have hit a dead end: although previous positions may be filled with valid values, it is impossible to fill the current one. So you should go to the previous filled position and try to continue with the next valid value there. Commented Jul 24, 2011 at 20:52
  • Yes, but I was hoping that it would have found the correct value for the cell before j got to less than 0. Commented Jul 24, 2011 at 21:28
  • No, because that would mean that you would NEVER backtrack from one line to the previous, and that can and will happen. BTW, just for future reference, after you fully understand backtracking you may want to learn some good heuristics, forward checking, arc consistency and k-consistency algorithms. You may also want to check dancing links, which is a bit more hardcore :) Commented Jul 24, 2011 at 23:16

1 Answer 1

3

Backtracking algorithms usually restore the state if a branch fails and do the next possible move. So if the random filling of a field creates a failed branch just write back what was originally there.

Sign up to request clarification or add additional context in comments.

8 Comments

This is my first attempt at any sort of backtracking algorithm so I'm still a little confused. At what part in my code should I be considering writing back what was originally there?
Damn - I think I'm confusing the issue - comments deleted.
@Steve314 just described the two approaches. For recursive, your function should return a boolean and call itself after filling out a field, then call itself, if that failed (returned false) restore it. if it returned true you already have a solution, if you're looking for all of them you can restore it and keep on going... for stack based you obviously need a stack, in JS an array should be fine, but if you just learning backtracking avoid that solution. BTW: have you calculated estimates how many leafs (branches) you have to scan?
@Steve314 Actually Steve, you're a genius! Based on your comments I added matrix[i][j] = undefined in the if(!found) bit and the algorithm now works beautifully. Thank you very much! My day has no longer been a complete waste of my life.
@yi_H I haven't calculated how many branches I have to scan. I'm still trying to wrap my head around all this. I think I'm in over my head, however it is now working.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.