# λ N-Queens

======= Algorithm ======= <syntax js> // checks that there are no queens that are attacking the queen on column i // only ever needs to check queens on columns < i function noConflicts(columns, i) { for (var j=0; j<i; j++) { // same row if (columns[j] === columns[i]) { return false; } // diagonal if (i-j === Math.abs(columns[j]-columns[i])) { return false; } } return true; } // recursively solves the n-queens problem by brute force function queens(columns, i, n) { // we have a complete solution if (i === n) { return columns; } // try placing the next queen on every row for (var j=0; j<n; j++) { columns[i] = j; if (noConflicts(columns, i)) { var solution = queens(columns, i+1, n); if (solution) { return solution; } } } columns.pop(); return false; } // returns an array that records the queens' position in each column // or false if no solution is found solution = queens([], 0, 8); </syntax> ======= Support ======= <syntax js> // nothing </syntax> ======= Tests ======= <syntax js> function eqArrays(a, b) { if (a.length !== b.length) return false; for (var i=a.length-1; i>=0; i--) { if (a[i] !== b[i]) { return false; } } return true; } function testNQueens4x4() { var solution = queens([], 0, 4); var solA = [2,0,3,1]; var solB = [1,3,0,2]; assert(eqArrays(solution, solA) || eqArrays(solution, solB)); }</syntax> ======= Options ======= <syntax js> { "title":"N-Queens", "height": "620px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <script type="text/javascript"> var queenImg = new Image(); queenImg.src = 'lib/exe/fetch.php?media=algorithm:queen_w.png'; var displayed = null; function arrayEquals(a, b) { if (!a || !b ) return false; if (a.length !== b.length) return false; for(var i=0; i<a.length; i++) { if (a[i] !== b[i]) return false; } return true; } function update(n, x, isRunning, duration) { if (duration < 0) { return; // Stateless visualisation. } // get the columns to draw queens in var columns; if (x) { columns = x.lookupInScope("columns") || x.lookupInScope("solution") || (x.stack.length === 1 && x.returnedValue); if (!columns && x.stack.length === 0) { columns = x.returnedValue; } } if (!columns) { columns = []; } if (arrayEquals(columns, displayed)) return; displayed = columns.slice(); var canvas = document.getElementById("canvas"); ctx = canvas.getContext("2d"); ctx.font = "30px times"; // draw the board ctx.clearRect(0, 0, 256, 256); var w = 32; var border = (256-w*8)/2; for (var i=0; i<8; i++) { for (var j=0; j<8; j++) { ctx.fillStyle = (i+j)%2? '#BE783B' : '#F7C48E'; ctx.fillRect(border+i*w, border+j*w, w, w); } } // draw the queens ctx.fillStyle = "white"; for (var i=0; i<columns.length; i++) { var j = columns[i]; ctx.drawImage(queenImg, border+i*w, border+j*w); } } </script> </head> <body> <canvas id="canvas" width="256" height="256" style="vertical-align:top;border:1px solid #CCC"></canvas> </body> </html> </syntax>