码疯窝

javascript 解数独游戏

2015/08/07 19:32:33    分类: 技术随笔    1人评论 次浏览

最近手机下载了一个数独APP来打发时间玩, 到了6点几的难度, 基本上是每局都得花是40分钟左右才能解出来.
20150807193041

20151020135129

于是想着直接写出代码来解数独游戏.

20151020135236

20150807192944

解法仅仅是对每个单元格进行排除, 然后再穷举. 速度还不错哦, 如果能进行更深一步的排除的话, 速度估计还能提升一倍.


function _dec2bin(v) {
    if (typeof(v) === 'string') {
        v *= 1;
    }
    if (isNaN(v))
        throw 'invalid number';
    return (v === 0) ? 511 : 1 << (v - 1);
}

function _bin2dec(v) {
    var i = 1, len = 9, arr = [];
    for (i = 1; i <= len; i++) {
        if ((1 << (i - 1) & v) !== 0) {
            arr.push(i);
        }
    }
    return arr;
}

// Point Class
function Point(v) {
    if (typeof(v) === 'string') {
        this.setDec(v);
    } else {
        this.setBin(v);
    }
};
Point.prototype.setDec = function (v) {
    this.bin = _dec2bin(v);
    this.setBin(this.bin);
};
Point.prototype.setBin = function (v) {
    var arr = _bin2dec(v);
    this.bin = v;
    this.count = arr.length;
    this.possible = arr;
    this.solved = (this.count === 1);
    this.dec = this.solved ? arr[0] : 0;
};
Point.prototype.remove = function (v) {
    this.setBin(this.bin & ~v);
};
Point.prototype.setTrial = function (index) {
    this.setDec(this.possible[index]);
}

var len = 81, ic = 0, ir = 0, lr = 9, lc = 9;
var Sudoku = {
    // init and load game.
    load: function (str) {
        this.trials = [];
        this.solvedMarks = {};
        this.restore(this.unserialize(str));
    },
    // print the board
    print: function () {
        var board = this.board, output = [];
        for (ir = 0; ir < lr; ir++) {
            output.push('\n');
            for (ic = 0; ic < lc; ic++) {
                output.push('[' + board[ir][ic].possible.join() + ']');
            }
        }
        console.log(output.join(''));
    },
    // print the board in a nice way
    beautyPrint: function () {
        var board = this.board, output = [];
        for (ir = 0; ir < lr; ir++) {
            if (ir === 0 || ir === 3 || ir === 6) {
                output.push('\n -------------------------\n');
            } else {
                output.push('\n');
            }
            for (ic = 0; ic < lc; ic++) {
                if (ic === 0 || ic === 3 || ic === 6) {
                    output.push(' |')
                }
                if (board[ir][ic].count > 1) {
                    output.push('  ');
                } else {
                    output.push(' ' + board[ir][ic].dec);
                }
                if (ic === 8) {
                    output.push(' |')
                }
            }
        }
        output.push('\n -------------------------\n');
        console.log(output.join(''));
    },
    addSolved: function (x, y) {
        this.solvedMarks[x + '-' + y] = true;
    },
    // Get min position of the board
    getMinPos: function () {
        var i = 0, board = this.board, min = 10, minPoint = null, minR, minC;
        for (ir = 0; ir < lr; ir++) {
            for (ic = 0; ic < lc; ic++) {
                if (min > board[ir][ic].count && !board[ir][ic].solved) {
                    min = board[ir][ic].count;
                    minPoint = board[ir][ic];
                    minR = ir;
                    minC = ic;
                }
            }
        }
        if (minPoint === null)
            return false;
        return [minR, minC, minPoint];
    },
    // Check if the board is passed
    check: function (r, c) {
        var rb = 0, rc = 0, i = 0, board = this.board, rbe = 0, rbc = 0;

        for (i = 0; i < lr; i++) {
            rb |= board[r][i].bin;
            if (board[r][i].count === 1) {
                if (rbe === (board[r][i].bin | rbe)) {
                    return false;
                }
                rbe |= board[r][i].bin;
            }
            rc |= board[i][c].bin;
            if (board[i][c].count === 1) {
                if (rbc === (board[i][c].bin | rbc)) {
                    return false;
                }
                rbc |= board[i][c].bin;
            }
        }
        return (rc === 511 && rb === 511);
    },
    // null means failed, true means solved, false means not solved
    remove: function (x, y, v) {
        var point = this.board[x][y];
        point.remove(v.bin);
        if (point.bin === 0)
            return null;
        if (point.solved) {
            this.addSolved(x, y);
            if (!this.check(x, ir)) {
                return null;
            }
            return true;
        }
        return false;
    },
    // Base on the solved to update another 8 * 2 + 4;
    update: function () {
        var blank = this.blank, serial = '',
            solvedMarks = this.solvedMarks, 
            x, y, v, boxX, boxY, i = 0, rst = null,
            boxStart, hasUpdate = false;
        do {
            if (Object.keys(solvedMarks).length === 81) { // All solved
                return null;
            }
            serial = this.serialize();
            hasUpdate = false;
            for (i in solvedMarks) {
                x = i[0];
                y = i[2];
                v = this.board[x][y];
                boxStart = [parseInt(x / 3) * 3, parseInt(y / 3) * 3];

                for (ir = 0; ir < lr; ir++) {
                    if (ir !== y && solvedMarks[x + '-' + ir] === undefined) {
                        hasUpdate = this.remove(x, ir, v);
                        if (hasUpdate === null) {
                            //console.log('WARNING: trial failed, rollback.');
                            return false;
                        }
                        //console.log('INFO: row updated.');
                    }
                    if (ir !== x && solvedMarks[ir + '-' + y] === undefined) {
                        hasUpdate = this.remove(ir, y, v);
                        if (hasUpdate === null) {
                            //console.log('WARNING: trial failed, rollback.');
                            return false;
                        }
                        //console.log('INFO: column update.');
                    }
                    boxX = boxStart[0] + parseInt(ir / 3);
                    boxY = boxStart[1] + ir % 3;
                    if (boxX !== x && boxY !== y && solvedMarks[boxX + '-' + boxY] === undefined) {
                        hasUpdate = this.remove(boxX, boxY, v);
                        if (hasUpdate === null) {
                            //console.log('WARNING: trial failed, rollback.');
                            return false;
                        }
                        //console.log('INFO: box update.');
                    }
                }
            }
            if (!hasUpdate && serial !== this.serialize())
                hasUpdate = true;
        } while (hasUpdate);
        return true;
    },
    // Serialize current state to a string.
    serialize: function (state) {
        var board = this.board, barr = [], stateArr = [];
        for (ir = 0; ir < lr; ir++) {
            for (ic = 0; ic < lc; ic++) {
                barr.push(board[ir][ic].bin);
            }
        }
        if (state)
            stateArr = [state.point.bin, state.r, state.c, state.index];
        return barr.join('|') + ':' + stateArr.join('&');
    },
    // Unserialize a string to state object.
    unserialize: function (str) {
        var obj = str.split(':'),
            stateArr = [], state = undefined,
            code = '', isBin = false,
            row = [], solvedMarks = {}, col = [],
            i = 0;

        if (obj[0].length === 81) {
            isBin = false;
            code = obj[0];
        } else {
            isBin = true;
            code = obj[0].split('|');
        }
        for (i = 0; i < len; i++) {
            if (i != 0 && i % 9 === 0) {
                row.push(col);
                col = [];
            }
            point = new Point(isBin ? (code[i] * 1) : (code[i] + ''));
            col.push(point);
            if (point.solved) {
                solvedMarks[parseInt(i / 9) + '-' + (i % 9)] = true;
            }
        }
        row.push(col);
        if (obj.length === 2) {
            stateArr = obj[1].split('&');
            if (stateArr.length > 0)
            state = {
                point: new Point(stateArr[0] * 1),
                r: stateArr[1] * 1,
                c: stateArr[2] * 1,
                index: stateArr[3] * 1
            }
        }
        return {
            board: row,
            solvedMarks: solvedMarks,
            state: state
        };
    },
    // Backup state
    backUp: function (state) {
        this.trials.push(this.serialize(state));
    },
    // Restore state
    restore: function (obj) {
        if (!obj) {
            obj = this.unserialize(this.trials[this.trials.length - 1]);
        }
        this.board = obj.board;
        this.solvedMarks = obj.solvedMarks;
        return obj;
    },
    // Apply state
    applyState: function (state) {
        var t = this.trials, last = t.length - 1, str = t[last], arr = str.split('&'), index = t[2] * 1;
        t[last] = arr.slice(0, 3).join('&') + '&' + state.index;
        this.board[state.r][state.c].setTrial(state.index);
        this.solvedMarks[state.r + '-' + state.c] = true;
    },
    // New trial
    trialNew: function () {
        var min = this.getMinPos(),
            rst = null,
            state = {
                point: new Point(min[2].bin),
                r: min[0],
                c: min[1],
                index: 0
            };
        //console.log('INFO: new trial [' + state.r + ', ' + state.c + ']=' + state.point.possible[state.index]);
        this.backUp(state);
        this.applyState(state);
        this.trialUpdate(state.r, state.c);
    },
    // Next trial
    trialNext: function () {
        var trial = null, state;
        do {
            if (this.trials.length === 0) {
                console.log('ERROR: this is sudoku do not have a solution');
                return false;
            }
            trial = this.restore();
            state = trial.state;
            if (state.point.count === state.index + 1)
                this.trials.pop();
            else
                break;
        } while (true)
        //console.log('INFO: backward trial [' + state.r + ', ' + state.c + ']=' + state.point.possible[state.index]);
        
        state.index++;
        //console.log('INFO: next trial [' + state.r + ', ' + state.c + ']=' + state.point.possible[state.index]);
        this.applyState(state);
        this.trialUpdate(state.r, state.c);
    },
    // Trial process
    trialUpdate: function (x, y) {
        var rst = null;
        if (this.check(x, y)) {
            rst = this.update();
            if (this.check(x, y)) {
                if (rst === null) {
                    this.beautyPrint();
                    console.log('SUCCESS: it is solved.');
                    return;
                }
            } else {
                rst = false;
            }
        }
        if (rst) {
            this.trialNew();
        } else {
            this.trialNext();
        }
    },
    solve: function () {
        this.update();
        this.trialNew();
    },
    play: function (v) {
        if (typeof(v) === 'string') {
            var startTime, endTime, now;
            startTime = new Date().getTime();
            this.load(v);
            this.beautyPrint();
            this.solve();
            endTime = new Date().getTime();
            console.log('Totally take ' + (endTime - startTime) + 'ms');
        } else {
            var i = 0;
            for (i in v) {
                this.play(v[i]);
            }
        }
    }
}

Sudoku.play([
    // 2.9
    '200900675001347900089620300105009207890574163403200089000050430540003090318000750',
    // world difficult
    '800000000003600000070090200050007000000045700000100030001000068008500010090000400',
    // 6.7
    '250800300700020080008001000900003000005700030000000904060000000007100050000046200',
    // 6.8
    '000004001000090080006300500000001009007500300040080000003000020600000700570200000',
    // 6.9
    '005009038070080005008000600000010002000506090000300500002040007700000200410000000'
]);
继续查看有关 技术随笔的文章

1个访客评论

  1. :-D

    城会玩

    qweqwe Reply