Sudoku solver

Solving sudoku using the backtracking algorithm. Uses ES6 generators to create a stream of possible solutions.

The generateBoards generator below creates all possible boards given the initial configuration. Then after filtering out invalid configurations (isPartialSolutionCorrect) the board is reported as a possible solution (yield board). All possible extensions of that board are also explored (yield* generateSolutions(board)).

Chrome (version 36) supports both ES6 generators and Sets but it's necessary to enable Experimental JavaScript at chrome://flags/#enable-javascript-harmony. Firefox (version 31) supports generators as well as Sets.

To run the example your browser has to support:

• ES6 generators
• for-of loops
• ES6 Sets

function* generateSolutions(board) {
    // copy board as it is modified inside this function
    var board = JSON.parse(JSON.stringify(board));

    for (var suggestion of generateBoards(board)) {
        board[suggestion.row][suggestion.column] = suggestion.value;

        if (isPartialSolutionCorrect(board)) {
            yield board;
            yield* generateSolutions(board);
        }
    }
}

function* generateBoards(board) {
    for (var i = 0; i < board.length; i++) {
        for (var j = 0; j < board[i].length; j++) {
            if (board[i][j] === 0) {
                for (var k = 1; k <= 9; k++) {
                    yield { row: i, column: j, value: k };
                }
            }
        }
    }
}

function isPartialSolutionCorrect(board) {
    return checkRows(board) && checkRows(zip(board)) &&
        checkGroups(board);
}

function isCompleteSolution(board) {
    return board.every(function(row) {
        return row.every(isTruthy);
    });
}

function checkRows(row) {
  return row.every(noDuplicates);
}

function checkGroups(board) {
    function checkGroup(group) {
        return group.map(flatten).every(noDuplicates);
    }
    var partitionByThree = partition.bind(null, 3);
    return zip(board.map(partitionByThree)).map(partitionByThree)
        .map(checkGroup).every(isTruthy);
}

function noDuplicates(array) {
    var filtered = array.filter(isTruthy);
    // new Set([1,2,3]) does not work in Chrome but works in Firefox
    var set = new Set();
    filtered.forEach(function(element) {
        set.add(element);
    });
    return filtered.length === set.size;
}

function zip(arrays) {
    return arrays[0].map(function(element, index) {
        return arrays.map(function(array) {
            return array[index];
        });
    });
}

function partition(chunkSize, array) {
    return flatten(array.map(function(element, index) {
        if (index % chunkSize) {
            return [];
        } else {
            return [ array.slice(index, index + chunkSize) ];
        }
    }));
}

function flatten(array) {
    return Array.prototype.concat.apply([], array);
}

function isTruthy(value) {
    return !!value;
}

function print(board) {
    function elementToCharacter(element) {
        return element === 0 ? '.' : element;
    }
    function getLine(row) {
        return row.map(elementToCharacter).join(' ');
    }
    var text = board.map(getLine).join('\n');
    document.querySelector('.sudoku-board').value = text;
}

function parse(text) {
    function parseCharacter(character) {
        return parseInt(character, 10) || 0;
    }
    function parseLine(line) {
        return line.split(' ').map(parseCharacter);
    }
    return text.split('\n').map(parseLine);
}

var partialElement = document.querySelector('.sudoku-partial');
var completeElement = document.querySelector('.sudoku-complete');
var statusElement = document.querySelector('.sudoku-status');

var startButton = document.querySelector('.sudoku-start');
var stopButton = document.querySelector('.sudoku-stop');

var handle;

startButton.onclick = function() {
    var board = parse(document.querySelector('.sudoku-board').value);
    var boards = generateSolutions(board);
    var partial = 0, complete = 0;

    function printNextSolution() {
        var result = boards.next();
        if (!result.done) {
            var solution = result.value;
            print(solution);
            partial++;
            if (isCompleteSolution(solution)) {
                complete++;
            }
            partialElement.textContent = partial;
            completeElement.textContent = complete;
            handle = setTimeout(printNextSolution, 200);
        } else {
            startButton.disabled = false;
            stopButton.disabled = true;
            statusElement.textContent = 'No more solutions';
        }
    }

    handle = setTimeout(printNextSolution, 200);
    startButton.disabled = true;
    stopButton.disabled = false;
    statusElement.textContent = 'Started';
    partialElement.textContent = partial;
    completeElement.textContent = complete;
};

stopButton.onclick = function() {
    clearTimeout(handle);
    startButton.disabled = false;
    stopButton.disabled = true;
    statusElement.textContent = 'Stopped';
};

document.querySelector('.sudoku-reset').onclick = function() {
    document.querySelector('.sudoku-board').value = '. 6 . 3 . . 8 . 4\n'+
'5 3 7 . 9 . . . .\n'+
'. 4 . . . 6 3 . 7\n'+
'. 9 . . 5 1 2 3 8\n'+
'. . . . . . . . .\n'+
'7 1 3 6 2 . . 4 .\n'+
'3 . 6 4 . . . 1 .\n'+
'. . . . 6 . 5 2 3\n'+
'1 . 2 . . 9 . 8 .';
};

setTimeout(function() {
    startButton.onclick();
}, 100);

Comments