吉吉于

八皇后

八皇后问题:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

 

在线演示

<html xmlns="http://www.w3.org/1999/xhtml"> 
    <head> 
        <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> 
        <title>Eight Queens Puzzle(Recursive algorithm) - 八皇后问题(递归算法)</title> 
        <style type="text/css"> 
            body {  
                background-color: #c1c1c1;  
            }  
            p {  
                text-align: center;  
            }  
            table {  
                border-width: 5px;  
                border-color: #bb3355;  
                border-style: solid;  
                background-color: #ffffff;  
            }  
            td {  
                text-align: center;  
                vertical-align: middle;  
                width: 70px;  
                height: 70px;  
            }  
            td.b {  
                background-color: #000000;  
            }  
        </style> 
        <script type="text/javascript"> 
            var Q = new Array(8); //八皇后所在的列位置  

            // 判断第n个皇后与前面的n-1个皇后是否冲突  
            function Clash(n) {  
                var flag = false; //冲突标志  
                var i = 0; //从第0行逐行判断  
                while ((i < n) && !flag) {  
                    flag = (Q[n] == Q[i]) || (Math.abs(Q[n] - Q[i]) == (n - i)); //在同一列或相同的对角线即为冲突  
                    i++;  
                }  
                return flag;  
            }  

            //搜索第n个皇后的位置  
            function QSeek(n) {  
                //判断是否已经回溯到了第一个皇后之前,即已经找到了所有解  
                if (n >= 0) {  
                    Q[n]++; //将该位置的皇后右移一个位置  
                    if (Q[n] < 8) //当前行的皇后右移未超出范围  
                    {  
                        if (Clash(n)) //冲突则继续搜索当前行的皇后位置  
                            return QSeek(n)  
                        else //不冲突则当前行搜索完成  
                            return true;  
                    }
                    else //当前行无法安放,递归回溯  
                    {  
                        Q[n] = -1; //删除当前行的皇后  
                        if (QSeek(n - 1)) //递归回溯  
                            return QSeek(n) //在前一行搜索成功时,再搜索当前行  
                        else  
                            return false; //无解  
                    }  
                }  
                else  
                    return false; //无解  
            }  

            //刷新皇后图片  
            function showQueens() {  
                //清除原有图像,即清除所有TD标记中的内容  
                var tds = document.getElementsByTagName("TD");  
                for (var i = 0; i < tds.length; i++)  
                    tds[i].innerHTML = "";  
                //绘制新图像  
                for (var i = 0; i < 8; i++) {  
                    eval("r" + i + "c" + Q[i] + ".innerHTML = \"<img src=\\\"queen.jpg\\\" />\";");  
                }  
            }  

            var count = 1; //记录解的个数  

            function Queens() {  

                if (count == 1) { //求第一组解时需搜索前7个皇后的位置  
                    for (var i = 0; i < 7; i++)  
                        QSeek(i);  
                }  
                if (QSeek(7)) {  
                    showQueens();  
                    seekbtn.value = "已经搜索到第" + count + "组解,准备搜索第" + ++count + "组解...";  
                    seekbtn.focus(); //设置焦点到按钮  
                }  
                else  
                    seekbtn.value = "全部解已经搜索完成,共" + (count - 1) + "组!";  
            }  
        </script> 
    </head> 
    <body> 
        <p> 
            Eight Queens Puzzle (Recursive algorithm) - 八皇后问题(递归算法)<br /> 
        </p> 
        <center> 
            <table cellpadding="0" cellspacing="0"> 
                <tr> 
                    <td id="r0c0"></td> 
                    <td class="b" id="r0c1"></td> 
                    <td id="r0c2"></td> 
                    <td class="b" id="r0c3"></td> 
                    <td id="r0c4"></td> 
                    <td class="b" id="r0c5"></td> 
                    <td id="r0c6"></td> 
                    <td class="b" id="r0c7"></td> 
                </tr> 
                <tr> 
                    <td class="b" id="r1c0"></td> 
                    <td id="r1c1"></td> 
                    <td class="b" id="r1c2"></td> 
                    <td id="r1c3"></td> 
                    <td class="b" id="r1c4"></td> 
                    <td id="r1c5"></td> 
                    <td class="b" id="r1c6"></td> 
                    <td id="r1c7"></td> 
                </tr> 
                <tr> 
                    <td id="r2c0"></td> 
                    <td class="b" id="r2c1"></td> 
                    <td id="r2c2"></td> 
                    <td class="b" id="r2c3"></td> 
                    <td id="r2c4"></td> 
                    <td class="b" id="r2c5"></td> 
                    <td id="r2c6"></td> 
                    <td class="b" id="r2c7"></td> 
                </tr> 
                <tr> 
                    <td class="b" id="r3c0"></td> 
                    <td id="r3c1"></td> 
                    <td class="b" id="r3c2"></td> 
                    <td id="r3c3"></td> 
                    <td class="b" id="r3c4"></td> 
                    <td id="r3c5"></td> 
                    <td class="b" id="r3c6"></td> 
                    <td id="r3c7"></td> 
                </tr> 
                <tr> 
                    <td id="r4c0"></td> 
                    <td class="b" id="r4c1"></td> 
                    <td id="r4c2"></td> 
                    <td class="b" id="r4c3"></td> 
                    <td id="r4c4"></td> 
                    <td class="b" id="r4c5"></td> 
                    <td id="r4c6"></td> 
                    <td class="b" id="r4c7"></td> 
                </tr> 
                <tr> 
                    <td class="b" id="r5c0"></td> 
                    <td id="r5c1"></td> 
                    <td class="b" id="r5c2"></td> 
                    <td id="r5c3"></td> 
                    <td class="b" id="r5c4"></td> 
                    <td id="r5c5"></td> 
                    <td class="b" id="r5c6"></td> 
                    <td id="r5c7"></td> 
                </tr> 
                <tr> 
                    <td id="r6c0"></td> 
                    <td class="b" id="r6c1"></td> 
                    <td id="r6c2"></td> 
                    <td class="b" id="r6c3"></td> 
                    <td id="r6c4"></td> 
                    <td class="b" id="r6c5"></td> 
                    <td id="r6c6"></td> 
                    <td class="b" id="r6c7"></td> 
                </tr> 
                <tr> 
                    <td class="b" id="r7c0"></td> 
                    <td id="r7c1"></td> 
                    <td class="b" id="r7c2"></td> 
                    <td id="r7c3"></td> 
                    <td class="b" id="r7c4"></td> 
                    <td id="r7c5"></td> 
                    <td class="b" id="r7c6"></td> 
                    <td id="r7c7"></td> 
                </tr> 
            </table> 
            <br/>
            <input style="width: 300px; height: 25px" type="button" id="seekbtn" value="准备搜索第1组解..." onclick="Queens()" /> 
        </center> 
    </body> 
    </html>

 

转载请注明:于哲的博客 » 八皇后