Страница не отвечает при создании судоку

Question

Я пытаюсь создать правильную судоку.

Я создал 3 метода для проверки чисел и один для генерации судоку.

createSudoku() пытается создать судоку.

colContainsNumber(): проверить, содержит ли col случайное число, которое я сгенерировал

rowContainsNumber(): То же, что colContainsNumber, только для строки

squareContainsNumber(): проверить, еслиблок содержит случайное число.

В createSudoku() я генерирую случайное число, и с помощью цикла while я продолжаю генерировать новое число, пока ни один из «contains-Methods» не вернет true (true для «да», номер уже находится встроки и т. д.)

Использование всех методов для создания судоку работает. (Например, если я использую только rowContainsNumber, я получу судоку, в котором ни одна строка не содержит того же номера и т. д.)

Но если я использую все три метода вместе, страница не будет отвечать.

Я попытался изменить порядок методов, которые я вызываю в цикле while, но не намного больше, потому что методы работают нормальноесли я позвоню только одному из них.

function createSudoku() {
    var sudoku = [
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0]
    ];
    for (var i = 0; i < 9; i++) {
        for (var j = 0; j < 9; j++) {
            //generate a random number between 1 and 9
            var randomNumber = Math.floor((Math.random() * 9) + 1);

            /*Keep generate a random number, until the square doesn't contain 
            the number. This is the loop where I'm supposed to use all three 
            Methods (colContains-, rowContains- and squareContainsNumber) but 
            the page doesn't respond if I use all three of them. If I only use 
            one like you can see now, the generation works fine*/

            while (squareContainsNumber(sudoku, i, j, randomNumber)) {
                randomNumber = Math.floor((Math.random() * 9) + 1);

            }
            sudoku[i][j] = randomNumber;
            solvedSudoku[i][j] = randomNumber;
        }
    }
    return sudoku;
}

function rowContainsNumber(sudoku, col, number) {
    for (var i = 0; i < 9; i++) {
        if (sudoku[col][i] == number) {
            return true;
        }
    }
    return false;
}

function colContainsNumber(sudoku, row, number) {
    for (var i = 0; i < 9; i++) {
        if (sudoku[i][row] == number) {
            return true;
        }
    }
    return false;
}

function squareContainsNumber(sudoku, col, row, number)
{
    var minRow, maxRow, minCol, maxCol = 0;
    //Check which column the loop is in, then set the min and max column so I 
    //can get the range of the block
    switch (col) {
        case 0:
        case 1:
        case 2:
            minCol = 0;
            maxCol = 2;
            break;
        case 3:
        case 4:
        case 5:
            minCol = 3;
            maxCol = 5;
            break;
        case 6:
        case 7:
        case 8:
            minCol = 6;
            maxCol = 8;
            break;
        default:
            break;
    }
    //Check which row the loop is in, then set the min and max row so I 
    //can get the range of the block
    switch (row) {
        case 0:
        case 1:
        case 2:
            minRow = 0;
            maxRow = 2;
            break;
        case 3:
        case 4:
        case 5:
            minRow = 3;
            maxRow = 5;
            break;
        case 6:
        case 7:
        case 8:
            minRow = 6;
            maxRow = 8;
            break;
        default:
            break;
    }

   //loop through the square and check If the square contains the random number
    for (var i = minRow; i <= maxRow; i++) {
        for (var j = minCol; j <= maxCol; j++) {
            if (sudoku[i][j] == number)
                return true;
        }
    }

    return false;
}

Ожидаемый результат будет правильным судоку, где ни строка, ни столбец, ни квадрат не содержат одно и то же число.

Но, как я уже сказал,страница просто не отвечает, возможно потому, что цикл while занимает слишком много времени.

Answer 1

Алгоритм случайного выбора значения ячейки судоку, основанный на выполнении ограничений не дублировать существующую цифру в строке, столбце или поле, является неполным. Можно следовать ограничениям, но все же обнаружить, что в пустой ячейке ранее все цифры 1-9 были выделены как соседи в строке, ячейке или поле.

Когда опубликованный код достигает этого условия, он пытаетсясоздать новую случайную цифру для головоломки, не проверяя, возможно ли это. Поскольку это невозможно, страница зависает, поскольку она продолжает пытаться использовать другую случайную цифру, которая не будет работать.

Этот фрагмент кода проверяет, что дома (строка, столбец или поле) пустой ячейки на самом деле не используютсяцифра и повторяет головоломку, если нет:

var attempts = 0;

function puzzle( sudoku) {
    ++attempts;

    function House() {
        this.index = Object.create(null);
    }
    House.prototype.add = function( n) {
            if( this.index[n]) {
                return 0;
            }
            this.index[n] = true;
            return n;
        };
    
    let houses = [];
    for( var i = 0; i < 27; ++i) {
        houses [i] = new House();
    }
    let rowOf = index =>  Math.floor(index/9);
    let colOf = index =>  index%9;
    let boxOf = index =>  3 * Math.floor( rowOf( index)/3) + Math.floor( colOf( index)/3);
    
    function randomDigit( index) {
        let rowHouse = houses[ rowOf( index)];
        let colHouse = houses[ 9 + colOf(index)];
        let boxHouse = houses[ 18 + boxOf(index)];
        let domain = [1,2,3,4,5,6,7,8,9].reduce( function( array, digit) {
            if( !(rowHouse.index[ digit] || colHouse.index[digit] || boxHouse.index[ digit])) {
                array.push( digit);
            }
            return array;
        }, []);
        let digit = domain.length ? domain[ Math.floor( domain.length * Math.random())] : 0;
        if( digit) {
            rowHouse.add(digit);
            colHouse.add(digit);
            boxHouse.add(digit);
        }
        return digit;
    }

    var sudoku = [];
    for( var index = 0 ; index < 81; ++index) {
        let digit = randomDigit( index);
        if( digit == 0) {
            break;
        }
        sudoku[ index] = digit;
    }

    if( sudoku.length == 81) {
        return sudoku;
    }
    return puzzle();
}

const sudoku = puzzle();

console.log( "Attempts = " + attempts);
if( sudoku.length < 81) {
    sudoku.push('x');
    console.log("invalid sudoku");
}
for( let i = 0; i < 81; i += 9) {
    console.log( sudoku.slice( i, i+9).toString());
}

Запуск фрагмента кода показывает, что для получения результата может потребоваться большое количество попыток.

Быстрый просмотр в Интернете показывает, что это может бытьнеобычный метод создания законченной головоломки, и без дальнейшего опыта я не могу комментировать ее полезность.