generating random sudoku puzzles in javascript results in unsolvable boards

Question

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?

Answer 1

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

Answer 2

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

the "dig hold" count is your sudoku puzzle difficulty

in my project , four level difficulty : easy(40) / medium(45) / hard(50) / expert(56)

references

I'am write sudoku solver and generator lib with different languages, maybe you can refer to it：

• sudoku-nodejs
• sudoku-go
• sudoku-dart
• sudoku-flutter