Sudoku Solver (Minified to hide solution).

sudoku.js

"use strict";module.exports=function(){var t=require("lodash");var r=function(){var t={exports:{}};var exports=t.exports;"use strict";var r=function(t,r,o){for(var n=t[r];n!==t;n=n[r]){o(n)}};var o=function(t,r,o){for(var n=t[r];n!==t;n=n[r]){o(n)}};var n=function(t){t.next.prev=t.prev;t.prev.next=t.next;r(t.head,"down",function(t){r(t,"right",function(t){t.up.down=t.down;t.down.up=t.up;t.header.length-=1})})};var e=function(t){r(t.head,"up",function(t){r(t,"left",function(t){t.header.length+=1;t.up.down=t;t.down.up=t})});t.next.prev=t;t.prev.next=t};var i=function(t,a){var s=a||{};var l=s.maxSolutions||0;var u=arguments[2]||{};var v=u.k||0;var f=u.solutions||[];var c=u.partials||[];if(l&&f.length===l){return f}if(t.next===t){f.push(c.slice(0))}else{var h;var p;o(t,"next",function(t){if(!h||t.length<p){h=t;p=t.length}});if(h&&h.length>0){n(h);r(h.head,"down",function(o){c[v]=o.rowNumber;r(o,"right",function(t){n(t.header)});i(t,s,{k:v+1,solutions:f,partials:c});r(o,"left",function(t){e(t.header)})});e(h)}}return f};var a=function(t){var r={};var o=t||{};var n=o.column;var e=o.left||(r.left=r.right=r);var i=o.up||(r.up=r.down=r);r.header=n;r.left=e;r.right=e.right;e.right.left=r;e.right=r;r.up=i;r.down=i.down;i.down.up=r;i.down=r;return r};var s=function(t,r){var o=[];var n=null;for(var e=0;e<t[0].length;e+=1){var s={};if(!n){n=s.prev=s.next=s}s.length=0;s.prev=n;s.next=n.next;s.head=a({column:s,left:n.head});n.next.prev=s;n.next=s;n=s;o.push(s)}t.forEach(function(t,r){var n=null;t.forEach(function(t,e){if(t){var i=o[e];var s=a({column:i,left:n,up:i.head.up});s.rowNumber=r;i.length+=1;n=s}})});var l={};l.prev=o[0].prev;l.next=o[0];o[0].prev.next=l;o[0].prev=l;return i(l,r)};exports.solve=s;return t.exports}();function o(t){this._board=t;this._solutions=[]}o.prototype.solve=function(r){var o=t.defaults({},r,{all:false,strategy:"advanced"});if(o.strategy==="advanced"){this._solutions=this._solve2(this._board,o.all)}else if(o.strategy==="backtracking"){this._solutions=this._solveBacktracking(this._board,o.all)}else if(o.strategy==="basic"){this._board=this._solveBasic(this._board).board}if(this._solutions.length){this._board=this._solutions[0]}};o.prototype._solve2=function(t,o){var n=r.solve(this._2ConstraintsMatrix(t),{maxSolutions:o?0:1});return n.map(function(r){var o=t.slice(0);for(var n=0;n<r.length;n++){var e=Math.floor(r[n]/81)%9;var i=Math.floor(r[n]/9)%9;var a=Math.floor(r[n]/1)%9+1;o=this.solveAt(o,e,i,a)}return o},this)};o.prototype._2ConstraintsMatrix=function(t){var r=[];for(var o=0;o<9;o++){for(var n=0;n<9;n++){var e=Number(this.valueAt(t,o,n));var i=function(t,e){var i=Math.floor(o/3)*3+Math.floor(n/3);var a=new Array(324);a[0+o*9+n]=e?1:0;a[81+o*9+t]=e?1:0;a[162+n*9+t]=e?1:0;a[243+i*9+t]=e?1:0;r.push(a)};for(var a=0;a<9;a++){var s=e;if(s===0){s=a+1}else if(s!=a+1){s=0}i(a,s)}}}return r};o.prototype._solveBacktracking=function(t,r){var o=[];var n=this.firstUnsolvedCell(t);if(n){var e=n.row;var i=n.col;for(var a=1;a<=9;a+=1){if(this.numberAllowedAt(t,e,i,a)){t=this.solveAt(t,e,i,a);o=o.concat(this._solveBacktracking(t));if(o.length&&!r){break}}}}else{o.push(t)}return o};o.prototype._solveBasic=function(t){var r=0;var o=true;while(o){o=false;r=this.eachUnsolvedCell(t,function(r,n){var e;for(var i=1;i<=9;i+=1){if(this.numberAllowedAt(t,r,n,i)){if(e){e=undefined;break}else{e=i}}}if(e){t=this.solveAt(t,r,n,e);o=true}})}return{board:t,solved:r===0}};o.prototype.firstUnsolvedCell=function(t,r){var o;for(var n=0;n<9&&!o;n+=1){for(var e=0;e<9&&!o;e+=1){if(!this.isSolved(t,n,e)){o={row:n,col:e}}}}return o};o.prototype.eachUnsolvedCell=function(t,r){var o=0;for(var n=0;n<9;n+=1){for(var e=0;e<9;e+=1){if(!this.isSolved(t,n,e)){o+=1;r.call(this,n,e)}}}return o};o.prototype.numberAllowedAt=function(t,r,o,n){return!this.rowContains(t,r,n)&&!this.colContains(t,o,n)&&!this.boxContains(t,r,o,n)};o.prototype.valueAt=function(t,r,o){return t[o+r*9]};o.prototype.solveAt=function(t,r,o,n){var e=o+r*9;return t.slice(0,e)+n.toString()+t.slice(e+1)};o.prototype.isSolved=function(t,r,o){return+this.valueAt(t,r,o)!==0};o.prototype.rowContains=function(t,r,o){var n=false;for(var e=0;e<9&&!n;e+=1){n=+this.valueAt(t,r,e)===o}return n};o.prototype.colContains=function(t,r,o){var n=false;for(var e=0;e<9&&!n;e+=1){n=+this.valueAt(t,e,r)===o}return n};o.prototype.boxOrigin=function(t,r){return{col:Math.floor(r/3)*3,row:Math.floor(t/3)*3}};o.prototype.boxContains=function(t,r,o,n){var e=this.boxOrigin(r,o);var i=false;for(var a=e.row;a<e.row+3&&!i;a+=1){for(var s=e.col;s<e.col+3&&!i;s+=1){i=+this.valueAt(t,a,s)===n}}return i};o.prototype.solutions=function(){return this._solutions};o.prototype.board=function(t){return this._drawBoard(t||this._board)};o.prototype._drawBoard=function(r){var o="";var n=function(r){t.times(31,function(){o+="-"});if(r){o+=r}};var e=function(){o+="|"};var i=function(n){t.times(9,function(t){if(t%3===0){e()}o+=" "+this.valueAt(r,n,t)+" "},this);e();o+="\n"}.bind(this);n("\n");i(0);i(1);i(2);n("\n");i(3);i(4);i(5);n("\n");i(6);i(7);i(8);n();return o};if(require.main===module){var n=require("fs");var e=require("commander");e.version("0.1.0").usage("[options] <file ...>").option("-i --intelligence <n>","Add peppers",parseInt).option("-s --single","Look for just one solution").parse(process.argv);if(e.args.length===0){e.help()}e.args.forEach(function(r){var i=n.readFileSync(r,{encoding:"utf8"});i.split(".").join(" ").split("\n").forEach(function(r){var n=new o(r);var i={};i.all=!e.single;i.strategy=["basic","backtracking"][e.intelligence];var a=n.board();n.solve(i);if(n._board.indexOf(" ")>=0){console.log("game not solved!");console.log(a);console.log(n.board())}if(n.solutions().length>1){console.log("multiple solutions. uh oh.");t.each(n.solutions(),function(t){console.log(n.board(t))})}process.stdout.write(".")})})}return o}();