JS1k, the yearly JS code golfing competition

JS1k: The JavaScript code golfing competition

2013 - Spring!

Home   Rules   Demos   Submit

All the solutions of 8 queen puzzle

Finds all the solutions of 8 queen puzzle. It placing eight chess queens on an 8×8 chessboard so that no two queens attack each other. All the solutions are 92, it prints them.

Author:
Asen Bozhilov
Twitter:
@
GitHub:
Facebook:
Google+:
+
Reddit:
/r/
Pouet:
Website: 
github.com/abozhilov
Compo:
classic
Demo link:
https://js1k.com/2013-spring/demo/1375
Shortlink:
https://js1k.com/1375
Blog post:
please update here!
Bytes:
799
Chars:
799
Submission
(function(){function l(){var t=f%r,l=t*s+t*10,c=Math.floor(f/r),h=c*s+c*10,p=l;for(var d=0;d<e;d++){for(var v=0;v<e;v++){if((v+d)%2==0){a.fillStyle=o;a.fillRect(p,h,i,i)}else{a.fillStyle=u;a.fillRect(p,h,i,i)}if(n[d][v]){a.fillStyle="#FFFFFF";a.fillText("Q",p+2,h+2)}p+=i}p=l;h+=i}f++}function h(t,r){var i=r,s=r;while(t--){if(i--){if(n[t][i])return false}if(s++<e){if(n[t][s])return false}}return true}var e=8,t={},n=[[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0]],r=5,i=20,s=160,o="#dabb85",u="#6b402d";c.width=840;c.height=3220;a.font="13pt Arial";a.textBaseline="top";var f=0;(function p(r){if(r>=e){l();return}for(var i=0;i<e;i++){if(!t[i]&&h(r,i)){t[i]=n[r][i]=1;p(r+1);t[i]=n[r][i]=0}}})(0)})()
Description
Finds all the solutions of 8 queen puzzle. It placing eight chess queens on an 8×8 chessboard so that no two queens attack each other. All the solutions are 92, it prints them.
Base64 encoded
KGZ1bmN0aW9uKCl7ZnVuY3Rpb24gbCgpe3ZhciB0PWYlcixsPXQqcyt0KjEwLGM9TWF0aC5mbG9vcihmL3IpLGg9YypzK2MqMTAscD1sO2Zvcih2YXIgZD0wO2Q8ZTtkKyspe2Zvcih2YXIgdj0wO3Y8ZTt2Kyspe2lmKCh2K2QpJTI9PTApe2EuZmlsbFN0eWxlPW87YS5maWxsUmVjdChwLGgsaSxpKX1lbHNle2EuZmlsbFN0eWxlPXU7YS5maWxsUmVjdChwLGgsaSxpKX1pZihuW2RdW3ZdKXthLmZpbGxTdHlsZT0iI0ZGRkZGRiI7YS5maWxsVGV4dCgiUSIscCsyLGgrMil9cCs9aX1wPWw7aCs9aX1mKyt9ZnVuY3Rpb24gaCh0LHIpe3ZhciBpPXIscz1yO3doaWxlKHQtLSl7aWYoaS0tKXtpZihuW3RdW2ldKXJldHVybiBmYWxzZX1pZihzKys8ZSl7aWYoblt0XVtzXSlyZXR1cm4gZmFsc2V9fXJldHVybiB0cnVlfXZhciBlPTgsdD17fSxuPVtbMCwwLDAsMCwwLDAsMCwwXSxbMCwwLDAsMCwwLDAsMCwwXSxbMCwwLDAsMCwwLDAsMCwwXSxbMCwwLDAsMCwwLDAsMCwwXSxbMCwwLDAsMCwwLDAsMCwwXSxbMCwwLDAsMCwwLDAsMCwwXSxbMCwwLDAsMCwwLDAsMCwwXSxbMCwwLDAsMCwwLDAsMCwwXV0scj01LGk9MjAscz0xNjAsbz0iI2RhYmI4NSIsdT0iIzZiNDAyZCI7Yy53aWR0aD04NDA7Yy5oZWlnaHQ9MzIyMDthLmZvbnQ9IjEzcHQgQXJpYWwiO2EudGV4dEJhc2VsaW5lPSJ0b3AiO3ZhciBmPTA7KGZ1bmN0aW9uIHAocil7aWYocj49ZSl7bCgpO3JldHVybn1mb3IodmFyIGk9MDtpPGU7aSsrKXtpZighdFtpXSYmaChyLGkpKXt0W2ldPW5bcl1baV09MTtwKHIrMSk7dFtpXT1uW3JdW2ldPTB9fX0pKDApfSkoKQ==
Original source
(function () {
    var N = 8,
        USED_COL = {},
        CHESS_BOARD = [
            [0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0]            
        ],
        
        BOARDS = 5,
        SQUARE_DIM = 20,
        BOARD_DIM = 160,
        WHITE = '#dabb85',
        BLACK = '#6b402d';
     
     c.width = 840;
     c.height = 3220;
     a.font = '13pt Arial';
     a.textBaseline = 'top';

    var solution = 0;
    function drawSol() {
        var col = solution % BOARDS,
            x = (col * BOARD_DIM) + (col * 10),
            y = Math.floor(solution / BOARDS),
            top = (y * BOARD_DIM) + (y * 10),
            left = x;
        
        for (var i = 0; i < N; i++) {
            for (var j = 0; j < N; j++) {
                if ((j + i) % 2 == 0) {
                    a.fillStyle = WHITE;
                    a.fillRect(left, top, SQUARE_DIM, SQUARE_DIM);
                }
                else {
                    a.fillStyle = BLACK;
                    a.fillRect(left, top, SQUARE_DIM, SQUARE_DIM);                    
                }
                if (CHESS_BOARD[i][j]) {
                    a.fillStyle = '#FFFFFF';
                    a.fillText('Q', left + 2, top + 2);
                }                
                left += SQUARE_DIM;
            }
            left = x;
            top += SQUARE_DIM;
        }
        solution++;
    }
        
    function isValidPos(row, col) {
        var i = col,
            j = col;
        while(row--) {
            if (i--) {
                if (CHESS_BOARD[row][i]) 
                    return false;
            }
            if (j++ < N) {
                if (CHESS_BOARD[row][j]) 
                    return false;
            }            
        }
        return true;
    }    
    
    /**
     * Generates the permutations of 8 queen on the board
     * Before place the next Queen it checks both above diagonals 
     * while the method places next Queen on every next row,
     * we need to check only above diagonals.
     * This method could be achived with 8 loops, but the recursion 
     * is more elegant and js1k solution.
     */
    (function solve(n) {
        if (n >= N) {
            drawSol();
            return;
        }
        for (var i = 0; i < N; i++) {
            if (!USED_COL[i] && isValidPos(n, i)) {
                USED_COL[i] = CHESS_BOARD[n][i] = 1;
                solve(n + 1);
                USED_COL[i] = CHESS_BOARD[n][i] = 0;
            }
        }
    })(0);
})();