javascript - 查询 : Sliding Puzzle Generator Giving Unsolvable Puzzles

Question

根据我的理解，创建一个可解决的滑动拼图必须遵循以下规则:

A. If the grid width is odd, then the number of inversions in a solvable situation is even.

B. If the grid width is even, and the blank is on an even row counting from the bottom (second->last, fourth-last etc), then the number of inversions in a solvable situation is odd.

C. If the grid width is even, and the blank is on an odd row counting from the bottom (last, third-last, fifth-last etc) then the number of inversions in a solvable situation is even.

我的生成器计算反转的次数并检测空白区域的位置，如果解决方案不遵循这些规则，则应重新掷出拼图。

Jquery/javascript 贴在下面

$(document).ready(function () {
    var tds = $("td");
    var tileCount = 15;
    var gameStart = false;

    function countInversions(board) {
        var inversions = 0;
        $.each(board, function (index, value) {
            if ($(value).children("div").attr("id") === "empty") {
                return true;
            } else {
                var tileNum = $(value).children("div").attr("id").replace(/[^0-9.]/g, '') * 1;
                $.each(board, function (index2, value2) {
                    if ($(value2).children("div").attr("id") === "empty" || index2 <= index) {
                        return true;
                    } else {
                        var tileNum2 = $(value2).children("div").attr("id").replace(/[^0-9.]/g, '') * 1;
                        if (tileNum > tileNum2) {
                            inversions++;
                        }
                    }
                });
            }
        });
        console.log(inversions);
        return inversions;
    }

    var scramble = function () {
        do {
            for (var i = 0; i <= 20; i++) {
                var ranNum = Math.floor(Math.random() * tds.length);
                var ranNum2 = Math.floor(Math.random() * tds.length);

                if (ranNum === ranNum2) {
                    continue;
                }

                var td1 = tds[ranNum];
                var td2 = tds[ranNum2];
                var tile1 = $(td1).children("div");
                var tile2 = $(td2).children("div");
                $("#" + $(td1).attr("id")).html(tile2);
                $("#" + $(td2).attr("id")).html(tile1);
            }
        } while ((countInversions($(tds)) % 2 !== 0 && $("#empty").parents("tr").attr("id").replace(/[^0-9.]/g, '') * 1 === (1 || 3)) || (countInversions($(tds)) % 2 === 0 && $("#empty").parents("tr").attr("id").replace(/[^0-9.]/g, '') * 1 === (2 || 4)));
        gameStart = true;
    };

    function slide(tile) {
        if (gameStart === true) {
            var tileNum = $(tile).attr("id").replace(/[^0-9.]/g, '') * 1;
            var $tile = $("#tile" + tileNum).clone();
            var pos = $(tile).parents("td");
            var posNum = $(tile).parents("td").attr("id").replace(/[^0-9.]/g, '') * 1;
            var y = posNum - 4;
            var x = posNum + 4;
            var $empty = $("#empty").clone();

            if ($(pos).next().children("div").attr("id") === "empty") {
                $(pos).next().children().replaceWith($tile.hide());
                $(pos).children().effect("slide", {
                    direction: "right",
                    mode: "hide"
                }, "fast", function () {
                    $(pos).children().replaceWith($empty);
                });
                $(pos).next().children().effect("slide", {
                    direction: "left",
                    mode: "show"
                }, "fast", function () {
                    victoryCheck();
                });
                addSlide(); //slide right
            } else if ($(pos).prev().children("div").attr("id") === "empty") {
                $(pos).prev().children().replaceWith($tile.hide());
                $(pos).children().effect("slide", {
                    direction: "left",
                    mode: "hide"
                }, "fast", function () {
                    $(pos).children().replaceWith($empty);
                });
                $(pos).prev().children().effect("slide", {
                    direction: "right",
                    mode: "show"
                }, "fast", function () {
                    victoryCheck();
                });
                addSlide(); //slide left
            } else if ($("#td" + x).children("div").attr("id") === "empty") {
                $("#td" + x).children().replaceWith($tile.hide());
                $(pos).children().effect("slide", {
                    direction: "down",
                    mode: "hide"
                }, "fast", function () {
                    $(pos).children().replaceWith($empty);
                });
                $("#td" + x).children().effect("slide", {
                    direction: "up",
                    mode: "show"
                }, "fast", function () {
                    victoryCheck();
                });

                addSlide(); //slide up
            } else if ($("#td" + y).children("div").attr("id") === "empty") {
                $("#td" + y).children().replaceWith($tile.hide());
                $(pos).children().effect("slide", {
                    direction: "up",
                    mode: "hide"
                }, "fast", function () {
                    $(pos).children().replaceWith($empty);
                });
                $("#td" + y).children().effect("slide", {
                    direction: "down",
                    mode: "show"
                }, "fast", function () {
                    victoryCheck();
                });

                addSlide(); //slide down
            }
        }
    }

    function victoryCheck() {
        if (countInversions($("td")) === 0 && $("#empty").parents("td").attr("id") === "td16") {
            gameStart = false;
            alert("You won. Winner.");
            return true;
        } else {
            return false;
        }

    }

});

参见 http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html更详细地解释方 block 游戏的可溶性。

公共(public) fiddle 示例: http://jsfiddle.net/themonstersarecoding/rzmKA/

Answer 1

我认为你检查拼图是否不可解的逻辑是不正确的，这是因为当你检查带有空 block 的行是奇数还是偶数时，你忽略了“从底部开始计数”的部分。解决此问题的一种方法是更改​​ <tr> 的“id”值元素，以便它们从底部开始计数。

更改为:

<table id="slidingPuzzle">
    <tr id="tr4">
        ...
    </tr>
    <tr id="tr3">
        ...
    </tr>
    <tr id="tr2">
        ...
    </tr>
    <tr id="tr1">
        ...
    </tr>
</table>