文章 - Canvas绘制N皇后 | 前端网（QDFuns）

一个小作业，忽然想起来好久没发过东西了，发上来冒个泡
顺便吐槽下ES6写多了写ES5是真的不习惯

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
    <link rel="stylesheet" href="./index.css">

aside {
            position: absolute;
            left: 0;
            top: 0;
            width: 240px;
            height: 100%;
            padding: 30px 30px 30px 30px;
            background: #ddd;
        }

aside>* {
            display: block;
            margin: 0 0 30px 0;
        }

aside .title {
            font-weight: 200;
        }

aside select, aside input {
            width: 200px;
            height: 37px;
            padding: 0 10px;
            border-radius: 3px;
            font-size: 16px;
            border: #999 solid 1px;
        }

aside input {
            width: 180px;
        }

aside select:focus {
            border-color: #409eff;
        }

aside button {
            float: left;
            width: 40%;
            height: 35px;
            text-align: center;
            border: none;
            border-radius: 3px;
            font-size: 18px;
            color: #fff;
            background-color: #409eff;
        }

aside button:hover {
            cursor: pointer;
        }

.next {
            margin-left: 10%;
        }

.container {
            position: relative;
            overflow: hidden;
            height: 100%;
            margin-left: 300px;
        }

.container:before, .container:after {
            content: '';
            display: block;
            height: 5%;
        }

.container canvas {
            display: block;
            margin: auto;
        }

.container .grid {
            position: absolute;
            left: 50%;
            transform: translateX(-50%);
            -webkit-transform: translate(-50%);
            -o-transform: translate(-50%);
            -moz-transform: translate(-50%);
        }
    </style>
</head>
<body>

<aside>
        <h1 class='title' placeholder="选择皇后数">N皇后问题</h1>
        <select id="count">
            <option value="4">4</option>
            <option value="5">5</option>
            <option value="6">6</option>
            <option value="7">7</option>
            <option value="8" selected>8</option>
            <option value="9">9</option>
            <option value="10">10</option>
            <option value="11">11</option>
            <option value="12">12</option>
            <option value="13">13</option>
            <option value="14">14</option>
            <option value="15">15</option>
            <option value="16">16</option>
            <option value="17">17</option>
            <option value="18">18</option>
            <option value="19">19</option>
            <option value="20">20</option>
            <option value="21">21</option>
            <option value="22">22</option>
            <option value="23">23</option>
            <option value="24">24</option>
            <option value="25">25</option>
            <option value="26">26</option>
            <option value="27">27</option>
            <option value="28">28</option>
            <option value="29">29</option>
            <option value="30">30</option>
            <option value="31">31</option>
            <option value="32">32</option>
        </select>
        <div class='info'></div>
        <input type="text" class='order' placeholder="选择解法序号">
        <button class='prev'>prev</button>
        <button class='next'>next</button>
    </aside>

window.onload = function() {

[].slice.call(document.querySelectorAll('canvas'), 0).forEach(function(v) { v.width  = v.height = window.innerHeight * 0.9});

//得到画笔
    var grid   = document.querySelector('.container .grid').getContext('2d'),
        ctx    = document.querySelector('.container .queens').getContext('2d'),
        select = document.querySelector('#count'),
        order  = document.querySelector('.order'),
        prev   = document.querySelector('.prev'),
        next   = document.querySelector('.next'),
        info   = document.querySelector('.info');

window.requestAnimationFrame = (function(){
        return  window.requestAnimationFrame       ||
                window.webkitRequestAnimationFrame ||
                window.mozRequestAnimationFrame    ||
                function( callback ){
                    window.setTimeout(callback, 1000 / 60);
                };
        })();

var data = {
        //画布的宽度
        width: window.innerHeight * 0.9,
        //每一格大小
        cellWidth: 0,
        //N皇后
        count: 0,
        _count: 0,
        //网格线的宽度,颜色
        gridWidth: 1,
        gridColor: 'rgba(0, 0, 0, .6)',
        //皇后的大小,相对于cellWidth的比例
        radius: 0.3,

//第几种解法
        index: 0,
        _index: 0
    };

//存放结果信息
    var result = [];

//数据绑定，在N皇后变化时重新绘制网格
    Object.defineProperty(data, 'count', {
        get() {
            return this._count;
        },
        set(value) {
            if(value !== this.count) {

this._count = value;

//绘制网格
                drawGrid();

//绘制解法
                result = [], prev = null;
                getResult();
                drawResult(0);
            }

return value;
        }
    });

//数据绑定，在解法索引变化时重新绘制解法
    Object.defineProperty(data, 'index', {
        get() {
            return this._index;
        },
        set(value) {
            if(value !== this._count) {
                info.textContent = `${data.count}皇后共有${result.length}种解法，当前是第${value + 1}种`;
                order.value = value + 1;
            }

return this._index = value;
        }
    })

select.addEventListener('change', function(e) {
        data.count = Number(e.target.value);
    });

order.addEventListener('change', function(e) {
        if(0 < e.target.value && e.target.value <= result.length) {
            drawResult(Number(e.target.value) - 1);
        }else {
            alert('输入有误');
            drawResult(0);
        }
    });

prev.addEventListener('click', function() {
        drawResult(data._index === 0 ? result.length - 1 : data._index - 1);
    });

next.addEventListener('click', function() {
        drawResult(data._index === result.length - 1 ? 0 : data._index + 1);
    });

//绘制网格
    function drawGrid() {
        var count = data._count;

//绘制网格
        data.cellWidth = (grid.canvas.width - count * data.gridWidth) / (count + 1);

grid.strokeStyle = data.gridColor;
        grid.lineWidth   = data.gridWidth;

ctx.clearRect(0, 0, grid.canvas.width, grid.canvas.width);
        grid.clearRect(0, 0, grid.canvas.width, grid.canvas.width);
        grid.beginPath();

for(var i = 1; i <= count; i++) {
            grid.moveTo(data.cellWidth + data.gridWidth * 0.5, data.cellWidth * i + data.gridWidth * (i - 0.5));
            grid.lineTo(data.cellWidth * count + data.gridWidth * (count - 0.5), data.cellWidth * i + data.gridWidth * (i - 0.5));
            grid.moveTo(data.cellWidth * i + data.gridWidth * (i - 0.5), data.cellWidth + data.gridWidth * 0.5);
            grid.lineTo(data.cellWidth * i + data.gridWidth * (i - 0.5), data.cellWidth * count + data.gridWidth * (count - 0.5));
        }

grid.stroke();
    }

//计算解
    function getResult() {
        var yPos = Array.apply(null, {length: data.count}).map(function(v, i) { return i });

while(next_permutation(yPos)) {
            //符合要求则为一个解
            //使用Uint8Array存储节省内存
            check() && result.push(yPos.map(function(v, i) { return new Uint8Array([i, v]) }));
        }

function check() {
            for(var i = 0; i < yPos.length - 1; i++) {
                for(var j = i + 1; j < yPos.length; j++) {
                    if((j - i) === Math.abs(yPos[i] - yPos[j]))
                        return false;
                }
            }

return true;
        }
    }

//上一次的解, 第几个解, 绘制动画的帧数
    var prev = null, frameCount = 60;

//将解法绘制在网格上
    function drawResult(index) {

//上一种解为空时给定默认值
        prev || (prev = result[result.length - 1]);

var interval = result[index].map(function(v, i) { return (v[1] - prev[i][1]) * (data.gridWidth + data.cellWidth) }),
            prevXPos = prev.map(function(v) { return (v[1] + 1) * (data.gridWidth + data.cellWidth) - 0.5 * data.gridWidth }),
            counter  = 0;

prev = result[index];
        data.index = index;

function draw() {
            ctx.clearRect(0, 0, ctx.canvas.width, ctx.canvas.width);

for(var i = 0; i < data.count; i++) {
                ctx.arc((i + 1) * (data.cellWidth + data.gridWidth) - 0.5 * data.gridWidth, prevXPos[i] + interval[i] / frameCount * counter, data.radius * data.cellWidth, 0, Math.PI * 2, false);
                ctx.fill();
                ctx.beginPath();
            }

counter++ !== frameCount && requestAnimationFrame(draw);
        }

draw();
    }

//数组部分反向
    function partial_reverse(array, start, end) {
        var i = start, ceil = start + Math.ceil(end - start), temp;

for(; i < ceil; i++) {
            array[i] = [array[end - (i - start)], array[end - (i - start)] = array[i]][0];
        }
    }

//求给定序列的下一个排列
    function next_permutation(array) {

var len = array.length;

for(var i = len - 1; i > 0; i--) {
            //从后向前找到第一个逆序
            if(array[i - 1] < array[i]) {
                //替换
                for(var j = len - 1; j >= i; j--) {
                    if(array[j] > array[i - 1]) {
                        array[i - 1] = [array[j], array[j] = array[i - 1]][0];
                        break;
                    }
                }
                //将反向递增序列反向为正向递增序列
                partial_reverse(array, i, len - 1);
                break;
            }
        }

//当所有数字按照递减序列时，没有下一个排列,i为0
        return i;
    }

//初始为8皇后
    data.count = 8;
}

</script>