Solving Sudoku with Dancing Links

function dlxSudokuSolver(strings, showSteps) {
    var headers, solutions = [], O = [];

        <<dlx_search>>

        <<dlx_cover_uncover>>

        <<dlx_utilities>>

        <<dlx_initialize_headers>>


    initializeHeaders();
    search(0);
    return solutions;
}

function search(k) {
    var c, r;
    if (headers.right === headers) {
        solutions.push(copySolution());
        return;
    }
    if (showSteps) {
        solutions.push(copySolution());
    }
    c = smallestColumn();
    cover(c);
    r = c.down;
    while (r !== c) {
        O.push(printRow(r));
        r = r.right;
        while (r.col !== c) {
            cover(r.col);
            r = r.right;
        }
        search(k + 1);
        r = r.left;
        while (r.col !== c) {
            uncover(r.col);
            r = r.left;
        }
        r = r.down;
        O.pop();
    }
    uncover(c);
}

function cover(c) {
    var r = c.down;
    c.right.left = c.left;
    c.left.right = c.right;
    while (r !== c) {
        r = r.right;
        while (r.col !== c) {
            r.up.down = r.down;
            r.down.up = r.up;
            r.col.size--;
            r = r.right;
        }
        r = r.down;
    }
}

function uncover(c) {
    var r = c.up;
    c.right.left = c;
    c.left.right = c;
    while (r !== c) {
        r = r.left;
        while (r.col !== c) {
            r.up.down = r;
            r.down.up = r;
            r.col.size++;
            r = r.left;
        }
        r = r.up;
    }
}

function smallestColumn() {
    var h, c, s = Number.MAX_VALUE;
    h = headers.right;
    while (h !== headers) {
        if (h.size < s) {
            c = h;
            s = c.size;
        }
        h = h.right;
    }
    return c;
}
function printRow(r) {
    var s = r.col.name + ' ', e = r;
    r = r.right;
    while (r !== e) {
        s += r.col.name + ' ';
        r = r.right;
    }
    return s;
}
function copySolution() {
    var solution = [].concat(O);
    return solution;
}

function element(name, children) {
    var el = document.createElement(name), i;
    if (children) {
        for(i = 0; i < children.length; i++) {
            var child = children[i];
            if (typeof child === "string") {
                el.appendChild(document.createTextNode(child));
            } else {
                el.appendChild(child);
            }
        };
    }
    return el;
}
function div()   { return element("div", arguments);   }
function table() { return element("table", arguments); }
function tbody() { return element("tbody", arguments); }
function tr()    { return element("tr", arguments);    }
function td()    { return element("td", arguments);    }
function span()  { return element("span", arguments);  }
function withAttribute(element, attr, value) {
    element.setAttribute(attr, value);
    return element;
}
function withClassname(element, cls) {
    return withAttribute(element, "class", cls);
}
function withMouseMoveListener(element, listener) {
    element.onmouseover = listener;
    return element;
}
function slider() {
    return withAttribute(
        withAttribute(element("input"), "type", "range"),
        "min", "0");
}


function makeSudokuBoard() {
    var i, j, board = tbody();
    for (i = 0; i < 9; i++) {
        var row = tr();
        for (j = 0; j < 9; j++) {
            var cell = withClassname(td(), "r" + i + " c" + j + " g" + (Math.floor(i/3)*3 + Math.floor(j/3)));
            row.appendChild(cell);
        }
        board.appendChild(row);
    }
    return withClassname(table(board), "sudokuBoard");
}

function clearBoard(board) {
    var i, cells = board.querySelectorAll("td");
    for (i = 0; i < cells.length; i++) {
        var cell = cells[i];
        cell.innerHTML = "";
    }

}

function setBoardFromString(board, strings, additionalStyle) {
    var i, j;
    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            var curValue = strings[i].charAt(j);
            if (curValue && curValue !== '.') {
                var cell = board.querySelector("td.r"+i+".c"+j);
                cell.innerHTML = "";
                cell.appendChild(document.createTextNode(curValue));

                if (cell.className.indexOf(additionalStyle) === -1)
                    cell.className += " " + additionalStyle;
            }
        }
    }
}

function parseAndReplaceWithBoard(divId, solve) {
    var divEl = document.getElementById(divId),
        data = divEl.innerHTML.trim(),
        board = makeSudokuBoard(),
        solutions,
        sliderEl = slider(),
        progressHeaderEl = div();

    divEl.innerHTML = "";
    setBoardFromString(board, data.split("\n"), "given");

    if (solve) {
        solutions = dlxSudokuSolver(data.split("\n"), true);
        sliderEl.setAttribute("max", solutions.length-1);
        sliderEl.setAttribute("value", 0);
        divEl.appendChild(progressHeaderEl);
        divEl.appendChild(board);
        divEl.appendChild(sliderEl);
        progressHeaderEl.innerHTML = sliderEl.value+" / "+(solutions.length - 1);
        sliderEl.oninput = function() {
            progressHeaderEl.innerHTML = sliderEl.value+" / "+(solutions.length-1);
            clearCells(board, "solution");
            setBoardFromString(board, toSudokuStrings(solutions[sliderEl.value]), "solution");
        }
    } else {
        divEl.appendChild(board);
    }
}

function clearCells(board, style) {
    var cells = board.querySelectorAll("." + style),
        i;
    for (i = 0; i < cells.length; i++) {
        cells[i].innerHTML = "";
    }
}
function toSudokuStrings(solution) {
    var positions = [], i, j, k, d;
    for (i = 0; i < 9; i++) {
        positions[i] = ['.', '.', '.','.', '.', '.','.', '.', '.'];
    }

    for (i = 0; i < solution.length; i++) {
        var position = /p(\d)(\d)/.exec(solution[i]);
        d = parseInt(/r\d(\d)/.exec(solution[i])[1]) + 1;
        j = position[1];
        k = position[2];
        positions[j][k] = d;
    }
    return positions.map(function(v) {return v.join("");});;
}

.sudokuBoard {
  margin: auto;
  background-color: #FFF;
}
.sudokuBoard td {
  width: 20px;
  height: 20px;
  border: solid thin black;
  text-align: center;
  line-height: 20px;
  font-size: 18px;
}
.sudokuBoard td.c3, .sudokuBoard td.c6 {
  border-left: 3px solid black;
}
.sudokuBoard td.r3, .sudokuBoard td.r6 {
  border-top: 3px solid black;
}

pre.example {
  width: 60px;
  background-color: #EEE;
}

td.solution {
  background-color: #EEE;
}
input[type='range'] {
  -webkit-appearance: none;
  border-radius: 5px;
  box-shadow: inset 0 0 5px #333;
  background-color: #999;
  height: 10px;
  vertical-align: middle;
}