在JavaScript中生成随机的Sudoku难题导致无法解决的板

发布于 2025-02-14 02:05:53 字数 4510 浏览 6 评论 0原文

我试图产生可以解决的随机Sudoku难题，但遇到了麻烦。我能够创建一个带有值的9x9二维数组，但是通常，这些值已经在自己的行中重复。我如何防止这种情况发生？以下是我的功能，该功能应该返回带有空位的Sudoku板。

    function pattern (r, c, base, side) { return (base * (r % base) + Math.floor(r / base) + c) % side; }
    function shuffle (s) { return s.sort(function () { return Math.random() - 0.5; }); }

    function getGrid () {

            var X = 0;

            var base = 3;
            var side = base * base;
            var rows = [], columns = [], numbers = [], b = [], newB = [];

            for (var x = 0; x < base; x++) {

                for (var y = 0; y < base; y++) {

                    rows.push(X * base + y);
                    columns.push(x * base + y);

                }

            }

            rows = shuffle(rows);
            columns = shuffle(columns);

            for (var n = 1; n < base * base + 1; n++) { numbers.push(n); }

            numbers = shuffle(numbers);

            for (var r = 0; r < rows.length; r++) {

                for (var c = 0; c < columns.length; c++) {

                    b.push(numbers[pattern(rows[r], columns[c], base, side)]);

                }

            }

            while (b.length) { newB.push(b.splice(0, 9)); }

            console.log(newB); // before removing some items, complete puzzle

            var squares = side * side;

            var emptySpots = Math.floor((squares * 3) / 4);

            for (var cell = 0; cell < squares; cell++) {

                if (Math.random() < 0.4) { newB[Math.floor(cell / side)][cell % side] = X; }

            }

            console.log(newB); // after removing some items, unsolved puzzle
            
            return newB;
            
    }

这是我从此功能中收到的输出的示例：

0: (9) [6, 3, 7, 0, 1, 5, 2, 8, 9]
1: (9) [7, 1, 2, 0, 0, 0, 6, 4, 8]
2: (9) [6, 3, 7, 4, 1, 0, 2, 8, 9]
3: (9) [6, 0, 0, 4, 1, 5, 2, 8, 0]
4: (9) [7, 0, 0, 0, 0, 3, 6, 0, 8]
5: (9) [0, 5, 0, 8, 3, 0, 0, 0, 4]
6: (9) [7, 1, 0, 0, 0, 0, 6, 4, 8]
7: (9) [0, 0, 6, 0, 0, 0, 0, 9, 4]
8: (9) [0, 5, 6, 8, 3, 0, 7, 9, 4]

这不是可解决的sudoku板，因为在同一行/列/方形中重复了值。有人有想法吗？

getGrid();

function pattern (r, c, base, side) { return (base * (r % base) + Math.floor(r / base) + c) % side; }
function shuffle (s) { return s.sort(function () { return Math.random() - 0.5; }); }

function getGrid () {

        var X = 0;

        var base = 3;
        var side = base * base;
        var rows = [], columns = [], numbers = [], b = [], newB = [];

        for (var x = 0; x < base; x++) {

            for (var y = 0; y < base; y++) {

                rows.push(X * base + y);
                columns.push(x * base + y);

            }

        }

        rows = shuffle(rows);
        columns = shuffle(columns);

        for (var n = 1; n < base * base + 1; n++) { numbers.push(n); }

        numbers = shuffle(numbers);

        for (var r = 0; r < rows.length; r++) {

            for (var c = 0; c < columns.length; c++) {

                b.push(numbers[pattern(rows[r], columns[c], base, side)]);

            }

        }

        while (b.length) { newB.push(b.splice(0, 9)); }

        console.log(newB); // before removing some items, complete puzzle

        var squares = side * side;

        var emptySpots = Math.floor((squares * 3) / 4);

        for (var cell = 0; cell < squares; cell++) {

            if (Math.random() < 0.4) { newB[Math.floor(cell / side)][cell % side] = X; }

        }

        console.log(newB); // after removing some items, unsolved puzzle
        
        return newB;
        
}

编辑：我在Python中制作了相同的程序，该程序正常工作，我试图在JavaScript中重写相同的功能，但结果是不同的。这是Python中的工作版本：

def get_board():

    global _board
    global empty
    
    base  = 3
    side  = base * base

    def pattern(r, c): return (base * (r % base) + r // base + c) % side

    def shuffle(s): return sample(s, len(s)) 

    rows  = [g * base + row for g in shuffle(range(base)) for row in shuffle(range(base))] 
    columns  = [g * base + column for g in shuffle(range(base)) for column in shuffle(range(base))]

    numbers  = shuffle(range(1, base * base + 1))

    _board = [[numbers[pattern(r, c)] for c in columns] for r in rows]

    squares = side * side
    empties = squares * 3 // 4
    for p in sample(range(squares), empties): _board[p // side][p % side] = empty

有人可以告诉我算法有何不同？

原文

im trying to generate random sudoku puzzles that can be solved, but am having trouble. i am able to create a 9x9 two-dimensional array with values, but oftentimes, the values have repeated in their own row. how can I prevent this from happening? below is my function which should return a sudoku board with emptied spots to solve.

    function pattern (r, c, base, side) { return (base * (r % base) + Math.floor(r / base) + c) % side; }
    function shuffle (s) { return s.sort(function () { return Math.random() - 0.5; }); }

    function getGrid () {

            var X = 0;

            var base = 3;
            var side = base * base;
            var rows = [], columns = [], numbers = [], b = [], newB = [];

            for (var x = 0; x < base; x++) {

                for (var y = 0; y < base; y++) {

                    rows.push(X * base + y);
                    columns.push(x * base + y);

                }

            }

            rows = shuffle(rows);
            columns = shuffle(columns);

            for (var n = 1; n < base * base + 1; n++) { numbers.push(n); }

            numbers = shuffle(numbers);

            for (var r = 0; r < rows.length; r++) {

                for (var c = 0; c < columns.length; c++) {

                    b.push(numbers[pattern(rows[r], columns[c], base, side)]);

                }

            }

            while (b.length) { newB.push(b.splice(0, 9)); }

            console.log(newB); // before removing some items, complete puzzle

            var squares = side * side;

            var emptySpots = Math.floor((squares * 3) / 4);

            for (var cell = 0; cell < squares; cell++) {

                if (Math.random() < 0.4) { newB[Math.floor(cell / side)][cell % side] = X; }

            }

            console.log(newB); // after removing some items, unsolved puzzle
            
            return newB;
            
    }

here is an example of an output which i have recieved from this function:

0: (9) [6, 3, 7, 0, 1, 5, 2, 8, 9]
1: (9) [7, 1, 2, 0, 0, 0, 6, 4, 8]
2: (9) [6, 3, 7, 4, 1, 0, 2, 8, 9]
3: (9) [6, 0, 0, 4, 1, 5, 2, 8, 0]
4: (9) [7, 0, 0, 0, 0, 3, 6, 0, 8]
5: (9) [0, 5, 0, 8, 3, 0, 0, 0, 4]
6: (9) [7, 1, 0, 0, 0, 0, 6, 4, 8]
7: (9) [0, 0, 6, 0, 0, 0, 0, 9, 4]
8: (9) [0, 5, 6, 8, 3, 0, 7, 9, 4]

this isn't a solvable sudoku board, as there are values repeated in the same row/column/square. does anyone have any ideas?

getGrid();

function pattern (r, c, base, side) { return (base * (r % base) + Math.floor(r / base) + c) % side; }
function shuffle (s) { return s.sort(function () { return Math.random() - 0.5; }); }

function getGrid () {

        var X = 0;

        var base = 3;
        var side = base * base;
        var rows = [], columns = [], numbers = [], b = [], newB = [];

        for (var x = 0; x < base; x++) {

            for (var y = 0; y < base; y++) {

                rows.push(X * base + y);
                columns.push(x * base + y);

            }

        }

        rows = shuffle(rows);
        columns = shuffle(columns);

        for (var n = 1; n < base * base + 1; n++) { numbers.push(n); }

        numbers = shuffle(numbers);

        for (var r = 0; r < rows.length; r++) {

            for (var c = 0; c < columns.length; c++) {

                b.push(numbers[pattern(rows[r], columns[c], base, side)]);

            }

        }

        while (b.length) { newB.push(b.splice(0, 9)); }

        console.log(newB); // before removing some items, complete puzzle

        var squares = side * side;

        var emptySpots = Math.floor((squares * 3) / 4);

        for (var cell = 0; cell < squares; cell++) {

            if (Math.random() < 0.4) { newB[Math.floor(cell / side)][cell % side] = X; }

        }

        console.log(newB); // after removing some items, unsolved puzzle
        
        return newB;
        
}

EDIT: i made the same program in python which worked perfectly, and i attempted to rewrite the same function in javascript, but the results are different. here is the working version in python:

def get_board():

    global _board
    global empty
    
    base  = 3
    side  = base * base

    def pattern(r, c): return (base * (r % base) + r // base + c) % side

    def shuffle(s): return sample(s, len(s)) 

    rows  = [g * base + row for g in shuffle(range(base)) for row in shuffle(range(base))] 
    columns  = [g * base + column for g in shuffle(range(base)) for column in shuffle(range(base))]

    numbers  = shuffle(range(1, base * base + 1))

    _board = [[numbers[pattern(r, c)] for c in columns] for r in rows]

    squares = side * side
    empties = squares * 3 // 4
    for p in sample(range(squares), empties): _board[p // side][p % side] = empty

could someone tell me how the algorithms differ?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

掀纱窥君容 2025-02-21 02:05:53

我只是为了娱乐而制作了一个（在Python算法之前，因为我不知道限制），这对想到的第一个算法不优化。

const getColumn = (colNumber, lines) =>
{
    const col = [];
    for (let i = 0; i < lines.length; ++i)
    {
        const line = lines[i];
        col.push(line[colNumber]);
    }
    return col;
};

const getAllowed = (column, picks) =>
{
    const choosable = [];
    for (let i = 0; i < picks.length; ++i)
    {
        const pick = picks[i];
        if (!column.includes(pick))
        {
            choosable.push(pick);
        }
    }
    return choosable;
};

function getSquare(colNumber, lineNumber, lines)
{
    const detected = [];
    if (!lineNumber)
    {
        return detected;
    }

    let startCol = Math.floor(colNumber / 3) * 3;
    let endCol = startCol + 3;

    let startLine = Math.floor(lineNumber / 3) * 3;
    let endLine = Math.min(startLine + 3, lines.length);

    for (let i = startCol; i < endCol; ++i)
    {
        for (let j = startLine; j < endLine; ++j)
        {
            const item = lines[j][i];
            if (item !== undefined)
            {
                detected.push(item);
            }
        }
    }

    return detected;
}

const generateRandomLine = (lines) =>
{
    const line = [];
    let selectables = [1, 2, 3, 4, 5, 6, 7, 8, 9];
    for (let i = 0; i < 9; ++i)
    {
        const column = getColumn(i, lines);

        let allowed;

        // Remove column items
        allowed = getAllowed(column, [1, 2, 3, 4, 5, 6, 7, 8, 9]);

        // Remove line items
        allowed = getAllowed(line, allowed);

        // remove square items
        const square = getSquare(i, lines.length, lines);
        allowed = getAllowed(square, allowed);

        const random = allowed.length > 1 ? Math.floor(Math.random() * allowed.length) : 0;

        const chosen = allowed[random];
        if (chosen === undefined)
        {
            return false;
        }
        line.push(chosen);

        selectables.splice(selectables.indexOf(chosen), 1);
    }

    return line;
};

const generateGrid = () =>
{
    let iterations;
    do
    {
        const grid = [];
        iterations = 0;
        do
        {
            ++iterations;
            if (iterations > 500)
            {
                iterations = -1;
                // Invalid
                break;
            }

            const line = generateRandomLine(grid);
            if (!line)
            {
                continue;
            }
            grid.push(line);


        } while (grid.length < 9);

        if (iterations !== -1)
        {
            return grid;
        }

    } while (true);

};

const displayGrid = () =>
{
    const grid = generateGrid();

    for (let i = 0; i < grid.length; ++i)
    {
        const line = grid[i];
        console.log(JSON.stringify(line));
    }
};

displayGrid();

PS：〜2H：10分钟

编辑1：重新检查Sudoku规则

编辑2：Hack＆amp;漏洞

I made one just for fun (before the Python algorithm, because I didn't know the restriction), unoptimised with the first algorithm that came to mind.

const getColumn = (colNumber, lines) =>
{
    const col = [];
    for (let i = 0; i < lines.length; ++i)
    {
        const line = lines[i];
        col.push(line[colNumber]);
    }
    return col;
};

const getAllowed = (column, picks) =>
{
    const choosable = [];
    for (let i = 0; i < picks.length; ++i)
    {
        const pick = picks[i];
        if (!column.includes(pick))
        {
            choosable.push(pick);
        }
    }
    return choosable;
};

function getSquare(colNumber, lineNumber, lines)
{
    const detected = [];
    if (!lineNumber)
    {
        return detected;
    }

    let startCol = Math.floor(colNumber / 3) * 3;
    let endCol = startCol + 3;

    let startLine = Math.floor(lineNumber / 3) * 3;
    let endLine = Math.min(startLine + 3, lines.length);

    for (let i = startCol; i < endCol; ++i)
    {
        for (let j = startLine; j < endLine; ++j)
        {
            const item = lines[j][i];
            if (item !== undefined)
            {
                detected.push(item);
            }
        }
    }

    return detected;
}

const generateRandomLine = (lines) =>
{
    const line = [];
    let selectables = [1, 2, 3, 4, 5, 6, 7, 8, 9];
    for (let i = 0; i < 9; ++i)
    {
        const column = getColumn(i, lines);

        let allowed;

        // Remove column items
        allowed = getAllowed(column, [1, 2, 3, 4, 5, 6, 7, 8, 9]);

        // Remove line items
        allowed = getAllowed(line, allowed);

        // remove square items
        const square = getSquare(i, lines.length, lines);
        allowed = getAllowed(square, allowed);

        const random = allowed.length > 1 ? Math.floor(Math.random() * allowed.length) : 0;

        const chosen = allowed[random];
        if (chosen === undefined)
        {
            return false;
        }
        line.push(chosen);

        selectables.splice(selectables.indexOf(chosen), 1);
    }

    return line;
};

const generateGrid = () =>
{
    let iterations;
    do
    {
        const grid = [];
        iterations = 0;
        do
        {
            ++iterations;
            if (iterations > 500)
            {
                iterations = -1;
                // Invalid
                break;
            }

            const line = generateRandomLine(grid);
            if (!line)
            {
                continue;
            }
            grid.push(line);


        } while (grid.length < 9);

        if (iterations !== -1)
        {
            return grid;
        }

    } while (true);

};

const displayGrid = () =>
{
    const grid = generateGrid();

    for (let i = 0; i < grid.length; ++i)
    {
        const line = grid[i];
        console.log(JSON.stringify(line));
    }
};

displayGrid();

PS: ~ 2h:10min

EDIT 1: Recheck Sudoku rules

EDIT 2: Hack & bug

回复收藏 0 原文

轻拂→两袖风尘 2025-02-21 02:05:53

似乎这个答案可以解决您的问题
https://stackoverflow.com/a/76596381/2674707

我分享我的想法

构建完整的sudoku

您可以在完整空白上生成一个随机1-9的地方（例如中间中心）矩阵，看起来像这样：

   ·  ·  ·   ·  ·  ·   ·  .  ·
   ·  .  ·   ·  .  .   .  ·  .
   .  ·  ·   .  ·  ·   ·  ·  .

   ·  .  ·   2  9  1   .  ·  .
   ·  .  ·   8  6  7   ·  ·  ·
   ·  ·  ·   3  5  4   ·  ·  ·

   ·  ·  .   ·  .  ·   .  ·  ·
   ·  ·  .   ·  ·  .   .  ·  .
   ·  .  ·   ·  ·  ·   ·  ·  ·

因此您可以使用 backtrace 求解并制作完整的sudoku

随机“挖掘孔”，在每个“挖掘孔”之后，您需要验证此难题是

基于完整的Sudoku，您可以清除随机位置的数量，即我称其为“挖洞”，在每个挖洞之后，您需要验证拼图并确保是一号解决方案，直到所有挖洞都完成

如何验证sudoku拼图是一索？
使用dfs尝试找到许多解决方案，即使是一个解决方案，这意味着一键，否则您可以打破并返回

“ DIG HOLD”计数是

您的项目中的Sudoku拼图困难，四级难度：easy（40） /媒介（ 45） / HARD（50） /专家（56）

参考文献

>用不同的语言

I'am写sudoku solver < / strong>和发电机< / strong < / strong < / strong < / strong < / strong < / strong < / strong < / strong < / strong < / strong < / strong href =“ https://github.com/einsitang/sudoku-nodejs” rel =“ nofollow noreferrer”> sudoku-nodejs
sudoku-go
sudoku-dart
sudoku-flutter

seem this answer can solve your question
https://stackoverflow.com/a/76596381/2674707

that is I did and seem work very well , so I'am share my idea

build complete Sudoku

you can generate one place (like middle center one) with random 1-9 on complete blank matrix, look like this :

   ·  ·  ·   ·  ·  ·   ·  .  ·
   ·  .  ·   ·  .  .   .  ·  .
   .  ·  ·   .  ·  ·   ·  ·  .

   ·  .  ·   2  9  1   .  ·  .
   ·  .  ·   8  6  7   ·  ·  ·
   ·  ·  ·   3  5  4   ·  ·  ·

   ·  ·  .   ·  .  ·   .  ·  ·
   ·  ·  .   ·  ·  .   .  ·  .
   ·  .  ·   ·  ·  ·   ·  ·  ·

so you can use backtrace solve and make complete sudoku

random "dig hole" , after each "dig hole" you need verify this puzzle is one-solution

based on the complete sudoku , you can clear number of random position at it , that I'am call it "dig hole" , after each dig hole , you need to verify the puzzle and make sure is one-solution, until all dig hole done

how can verify a sudoku puzzle is one-solution ?
use dfs try to find many solution, if only one, that mean one-solution, else you can break and return