TransWikia.com

Why an infinite loop forms in the piece of JavaScript code below?

Stack Overflow Asked by Jay Sinha on January 11, 2021

In the isValid function, when trying to write any line of code in the first for loop, an infinite loop is created. For example when I try console logging i, it just keeps on logging it and never stops.

I guess it has something to do with recursion but i am not able to find exactly why.

The problem is here in the //check same row section

// is Valid
function isValid(board, pos, num){
    //check same row
    for(var i=0; i<9; i++){
      
        // any line here creates problem
        //console.log(i);
      
        if(board[pos[0]][i] == num && i != pos[1]){
            return false;
        }
    }

    //check same column
    for(var i=0; i<9; i++){
        if(board[i][pos[1]] == num && i != pos[0])
            return false;
    }

    //check grid
    var box_x = Math.floor(pos[0]/3);
    var box_y = Math.floor(pos[1]/3);
    for(var i=box_x*3; i<(box_x*3)+3; i++){
        for(var j=box_y*3; j<(box_y*3)+3; j++){
            if(num == board[i][j]){
                return false;
            }
        }
    }

    return true;
}
var board = [
    [8,0,0,0,0,0,0,0,0],
    [0,0,0,2,6,0,0,5,0],
    [0,0,9,8,0,0,0,0,4],
    [7,0,3,0,0,0,0,2,0],
    [0,0,0,0,4,0,0,8,1],
    [5,0,0,0,0,7,0,3,0],
    [0,5,0,0,0,9,2,4,0],
    [0,0,0,7,0,0,0,0,0],
    [9,1,0,0,0,0,0,0,0],
]


// find Empty Cells
function findEmpty(board){
    for(var i=0; i<9; i++){
        for(var j=0; j<9; j++){
            if(board[i][j] == 0){
                var pos = [i, j];
                return pos;
            }
        }
    } 
    var pos = [99,99];
    return pos;
}

//is Valid

function solve(board){
    var pos = findEmpty(board);
    if(pos[0] == 99)
        return true;
    for(var i=1; i<10; i++){
        if(isValid(board, pos, i)){
            board[pos[0]][pos[1]] = i;
            //div_update(pos[0], pos[1], i, board);

            if(solve(board))
                return true;

            board[pos[0]][pos[1]] = 0; //resetting Value
            //div_update(pos[0], pos[1], i, board);
        }
    }
    return false;
}

solve(board);
console.log(board);

One Answer

It's not a infinite loop, if you print a console_log at line 7, your script will try print a value 3,976.879 times in the console. For a browser or editor console will be generate a freeze or stopping show new values after a few thousand printed lines. If you run this script with node in the OS terminal, it takes about 15 minutes, after that done succefully.

Answered by Renato Alencar on January 11, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP