1
\$\begingroup\$

I've made a Sudoku generator. It works but it's clearly not very efficient. I'm looking for ways to optimize and speed it up a bit. You can check it out in this fiddle.

The results are printed to the JS console with how many iterations it takes to find a working puzzle and the Sudoku array printed to console.table(). Which can take between 6 to 800 iterations, which I can't help but feel isn't very efficient.

I'd also like any tips to help find the dimensions of the sub boxes to make a Sudoku of any size. I currently have it working with a 9x9 grid with 3x3 sub boxes, and 6x6 grid with 3x2 sub boxes. But is there any formula to figure out how to find sub box dimensions with any grid size?

Using square roots should work to find the sub box dimensions for 4x4, 9x9, 16x16, etc. But what about 6x6?

(function() {
    "use strict";

    var iterations = 0;

    function SudokuCreate(maxNum) {
        //generate number set
        var numSet = [];
        var sudokuArray = [];

        //populates number set and files sudoku with the rows and columns it needs
        for (var i = 1; i <= maxNum; ++i) {
            numSet.push(i);
            sudokuArray.push(new Array(maxNum));
        }

        //size of sub boxes, figure out more dynamic way to set this
        var horizontalBoxSize = 3,
            verticalBoxSize = maxNum === 9 ? 3 : 2;

        //find random number from 0 to max number, expludes max
        function getRandomInt(max) {
            return Math.floor(Math.random() * max);
        }

        //places numbers in the sudoku array
        function placeNumber(num, arr) {
            var lastRowIndex = arr.length - 1, //the index of the last row in the working array
                lastRow = arr[lastRowIndex], //the reference to the last row
                rowsToCheck = lastRowIndex % verticalBoxSize, //find what row of the sub box we are in vertically
                safeIndexes = [], //find which column is save to put a number in to
                randomSafeIndex; //pick one of the columns to place the number into from the safeIndexes array

            //used to find a safe column to place the number in the current row
            function findSafeIndex(boxesUsed) {
                //looks at previous rows if inside the sub box to see if the current number can be placed in the sub box
                function boxSafe(index) {
                    var indexBox = Math.floor(index / horizontalBoxSize);//finds which sub box the current index is in
                    if (boxesUsed.indexOf(indexBox) >= 0) {//checks to see if the current index's sub box has already been used
                        return false;
                    } else {
                        return true;
                    }
                }

                //loop through the current row to find a safe place to put the number
                for (var indexInLastRow = 0, rowLen = lastRow.length; indexInLastRow < rowLen; ++indexInLastRow) {
                    var columnSafe = true; //assume the current column is safe

                    //make sure the current number isn't already used in this column
                    for (var rowIndex = arr.length - 1; rowIndex >= 0; --rowIndex) {
                        if(arr[rowIndex][indexInLastRow] === num) {
                            columnSafe = false;
                        }
                    }

                    //make sure current index is empty, column is safe, and that current box is safe
                    if(lastRow[indexInLastRow] === undefined && columnSafe && boxSafe(indexInLastRow)) {
                        safeIndexes.push(indexInLastRow);
                    }
                }

                //return a safe index to be used for the current number
                return safeIndexes[getRandomInt(safeIndexes.length)];
            }

            var horizontalBoxesUsed = []; //records which sub box has been used, in the current sub box row

            //if we are not if the first row of the sub box, loop through the other rows to see which subboxes have been used
            if (rowsToCheck > 0) {
                for (var i = rowsToCheck; i > 0; --i) {
                    var horizontalBox = Math.floor(arr[lastRowIndex - i].indexOf(num) / horizontalBoxSize);
                    horizontalBoxesUsed.push( horizontalBox );
                }
            }

            //get a safe index to put the number in to the row
            randomSafeIndex = findSafeIndex(horizontalBoxesUsed);

            //if there are no safe indexs return the number
            if(randomSafeIndex === undefined) {
                return num;
            } else {//else if there are safe indexs add the number to an index in the row and return true
                lastRow[randomSafeIndex] = num;
                return true;
            }
        }

        //loop through the numbers to set them in the sudoku
        for (var i = numSet.length - 1; i >= 0; --i) {
            var workingArray = [];//holds the rows we are currently working with and/or have already wored with
            var possible = true;//is the sudoku even possible?
            while (sudokuArray.length > 0) {//while there are rows in the sudokuArray have have been been processed keep looping
                workingArray.push(sudokuArray.shift());//add a row to the working array from the sudoku array

                possible = placeNumber(numSet[i], workingArray);//place the current working number in to the working array, to find out if the sudoku puzzle is possible

                if(possible !== true) {//if its not possible generate a new sudoku puzzle
                    ++iterations;
                    return SudokuCreate(maxNum);
                }
            }

            //make the sudoku array equal to the working array when we're done
            sudokuArray = workingArray;
        }

        console.log(iterations);
        console.table(sudokuArray);
        return sudokuArray;//return our array to start to do some sudoku
    }

    SudokuCreate(9);//make a 9x9 sudoku
})();
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.