So, I'm making a function which solves a 4x4 sudoku. It takes in a 2D array and all the empty fields are replaced with 0s. With the isSafe function I'm trying to split the checks into multiple functions that way that it's easier to read. Althought I've tried some forms of avoiding the too much recursion as to implement a certant amount of checks etc.

I've tried setting maxIterations, tried returning false, returning null... Really was out of ideas.

I've noticed that it crashes quite fast, It can only solve a few numbers and then the error occurs. If anyone has a more efficent way please comment.

function solverFor4x4(grid) {
    let number = generateRandom(1, 5, [0, 5]);
    if (!number) {
        return;
    }
    console.log(number)
    for (let i = 0; i < grid.length; i  ) {
        for (let j = 0; j < grid[i].length; j  ) {
            if(grid[i][j] == 0 && isSafe(grid, number, i, j)) {
                grid[i][j] = number;
            }
        }
    }
    showSolution(grid);
}

function isSafe(grid, number, i, j) {
    if(isSafeRow(grid, number, i, j) && isSafeColumn(grid, number, i, j) && isSafeArea(grid, number, i, j)) {
        return true;
    }
}

function isSafeRow(grid, number, i, j) {
    if (grid[i].includes(number)) {
        solverFor4x4(grid);
    } else {
        return true;
    }
}


function isSafeColumn(grid, number, i, j) {
    let array = [];
    for (let i = 0; i < grid.length; i  ) {
        if(grid[i][j] == number) {
            solverFor4x4(grid);
        } else {
            array.push(grid[i][j]);
        }
    }

    if(array.includes(number)) {
        solverFor4x4(grid);
    } else {
        return true;
    }
}

function isSafeArea(grid, number, i, j) {
    return true;
}

function generateRandom(min, max, exclude) {
    let random;
    let counter = 0;
    const maxIterations = 100;
    while (!random && counter < maxIterations) {
        const x = Math.floor(Math.random() * (max - min   1))   min;
        if (exclude.indexOf(x) === -1) {
            random = x;
        }
        counter  ;
    }
    return random || null;
}

EDIT: Forgot to place the code, sorry.

CodePudding user response：

Here's the updated code:

function solverFor4x4(grid) {
    let number = generateRandom(1, 5, [0, 5]);
    if (!number) {
        return;
    }
    console.log(number)
    for (let i = 0; i < grid.length; i  ) {
        for (let j = 0; j < grid[i].length; j  ) {
            if(grid[i][j] == 0 && isSafe(grid, number, i, j)) {
                grid[i][j] = number;
            }
        }
    }
    showSolution(grid);
}

function isSafe(grid, number, i, j) {
    if(isSafeRow(grid, number, i, j) && isSafeColumn(grid, number, i, j) && isSafeArea(grid, number, i, j)) {
        return true;
    } else {
        return false;
    }
}

function isSafeRow(grid, number, i, j) {
    if (grid[i].includes(number)) {
        return false;
    } else {
        return true;
    }
}


function isSafeColumn(grid, number, i, j) {
    let array = [];
    for (let i = 0; i < grid.length; i  ) {
        if(grid[i][j] == number) {
            return false;
        } else {
            array.push(grid[i][j]);
        }
    }

    if(array.includes(number)) {
        return false;
    } else {
        return true;
    }
}

function isSafeArea(grid, number, i, j) {
    return true;
}

function generateRandom(min, max, exclude) {
    let random;
    let counter = 0;
    const maxIterations = 100;
    while (!random && counter < maxIterations) {
        const x = Math.floor(Math.random() * (max - min   1))   min;
        if (exclude.indexOf(x) === -1) {
            random = x;
        }
        counter  ;
    }
    return random || null;
}

If not working try this:

function solverFor4x4(grid) {
    let number = generateRandom(1, 5, [0, 5]);
    if (!number) {
        return;
    }
    console.log(number)
    for (let i = 0; i < grid.length; i  ) {
        for (let j = 0; j < grid[i].length; j  ) {
            if(grid[i][j] == 0 && isSafe(grid, number, i, j)) {
                grid[i][j] = number;
                break;
            }
        }
    }
    showSolution(grid);
}

function isSafe(grid, number, i, j) {
    if(isSafeRow(grid, number, i, j) && isSafeColumn(grid, number, i, j) && isSafeArea(grid, number, i, j)) {
        return true;
    }
    return false;
}

function isSafeRow(grid, number, i, j) {
    return !grid[i].includes(number);
}

function isSafeColumn(grid, number, i, j) {
    for (let i = 0; i < grid.length; i  ) {
        if(grid[i][j] == number) {
            return false;
        }
    }
    return true;
}

function isSafeArea(grid, number, i, j) {
    return true;
}

function generateRandom(min, max, exclude) {
    let random;
    let counter = 0;
    const maxIterations = 100;
    while (!random && counter < maxIterations) {
        const x = Math.floor(Math.random() * (max - min   1))   min;
        if (exclude.indexOf(x) === -1) {
            random = x;
        }
        counter  ;
    }
    return random || null;
}

CodePudding user response：

It looks like the issue with the code is that it does not update the grid with the number placed if all checks return true. Also, the "isSafe" function does not return false if one of the checks fail. Try modifying the code as follows:

function solverFor4x4(grid) {
    let number = generateRandom(1, 5, [0, 5]);
    if (!number) {
        return;
    }
    console.log(number)
    for (let i = 0; i < grid.length; i  ) {
        for (let j = 0; j < grid[i].length; j  ) {
            if(grid[i][j] == 0 && isSafe(grid, number, i, j)) {
                grid[i][j] = number;
                solverFor4x4(grid);
            }
        }
    }
    showSolution(grid);
}

function isSafe(grid, number, i, j) {
    if(isSafeRow(grid, number, i, j) && isSafeColumn(grid, number, i, j) && isSafeArea(grid, number, i, j)) {
        return true;
    }
    return false;
}

function isSafeRow(grid, number, i, j) {
    if (grid[i].includes(number)) {
        return false;
    } else {
        return true;
    }
}


function isSafeColumn(grid, number, i, j) {
    let array = [];
    for (let i = 0; i < grid.length; i  ) {
        if(grid[i][j] == number) {
            return false;
        } else {
            array.push(grid[i][j]);
        }
    }

    if(array.includes(number)) {
        return false;
    } else {
        return true;
    }
}

This should solve the problem, but keep in mind that the function may still not work correctly due to the random number generation approach.