When enter recursion ... how can break; // out of recursion without freezes the browser window...?

#1

I have a Sudoku Solver Script in Javascript
it uses backtrack recursion algorithm to solve the sudoku

the problem is that in case conflict in input and the sudoku has No Solution — browser freezes …

When enter recursion … how can break; // out of recursion without freezes the browser window…?

I will provide code soon…

0 Likes

#2

When it’s a loop or recursion that’s happening, you can keep a count of how many times that it’s gone through a set of code.

For example with Sudoku, you can instead keep track of the states of the board, and reset the counter whenever the board changes. When that counter grows large enough then no more progress on the puzzle has occurred, resulting in a good condition to exit the code.

You don’t even need to track the states of the board. You can just use a counter and when it gets to be more than 10,000 or 100,000. you exit out of the code.

0 Likes

#3

There are a couple of tricks that can also be applied specifically to a standard, 9x9 Sudoku - if the number of clues given is less than 17, reject the puzzle immediately as unsolvable (God’s Number for Sudoku Hints is 17. [McGuire, Tugemann, & Civario, 2016] ).
If there are 10 or more empty rows+columns+3x3boxes in the grid, reject the puzzle immediately.
If there is a 5x6 square in which there are no hints, reject the puzzle immediately.
If the hint input is itself invalid (putting two of the same number in a row, column, or box), reject the puzzle immediately.

1 Like

#4

my question
is how exit mid of recursion… ? withOut browser freeze…

0 Likes

#5
function myrecursivefunction() {
   //Always put your break condition first.
   if(execution == 10000000) {
       return;
    }
     execution++;
     //Do A Thing
     myrecursivefunction();
}

var execution = 0; 
myrecursivefunction();
0 Likes

#6

        $("a[name='solve']").click(function (e) {
            
          e.preventDefault();
          e.stopPropagation();
      
          $("div#solution").html("<div style='text-align:center;'><img src='processing.gif' /><br>Please wait...!!!</div>");

          var queryString = $('form').serialize();
          var data=queryString.split('&');
          var result = [];
          var result1 = [];
          l = data.length;
          console.log(l);
          console.log(data);
          
          k=0;
      
          for (var i=0 ; i < l; i++) {
              t = [];
              t = data[i].split("=");

              if ( k >=9 ) {
                result1.push(result); 
                k=0;
                result = [];
              } 
              //console.log(t[1]);
              
                result[k] = parseInt(t[1]) ;
             
                //console.log(result);

                          
                k++; 

              
          }
          result1.push(result); 

          //data = [];
          

          // console.log(result1);
          sol = sudokuSolver(result1);

          console.log(sol);



        //try{
        
            result2 = "";
    
            if (sol != 'NO SOLUTION EXISTS!') {
                // printGrid($grid);		// in case you wanted print 9 lines from 9 chars solution [Not table]
                
                result2 += '<div style="width: 200px;"><a class="ui-shadow ui-btn ui-corner-all ui-btn-icon-left ui-icon-delete ui-btn-b" onclick="hideSolution();">Hide Solution</a><div><br><table style="width: 100%; max-width:500px;" class="initTable9x9Sudoku">';
    
                for(i=0; i<9; i++) {
                    result2 += "<tr>";
                    for(j=0; j<9; j++) {
                        result2 += "<td><input style='width:20px;' name='cc"+i+""+j+"' value='"+sol[i][j]+"' maxlength='1' size='1' /></td>";
                    }
                    result2 += "</tr>";
                }
                
                result2 += '</table>';
                //return result;
            } else
                result2 = '<div data-role="controlgroup" data-type="horizontal" data-mini="true"><a class="ui-shadow ui-btn ui-corner-all ui-btn-icon-left ui-icon-delete ui-btn-b" onclick="hideSolution();">Hide Solution</a><div><br><br>No solution exists';
    
        //}
        // catch (Exception e)
        // {
        //     result = '<div data-role="controlgroup" data-type="horizontal" data-mini="true"><a class="ui-shadow ui-btn ui-corner-all ui-btn-icon-left ui-icon-delete ui-btn-b" onclick="hideSolution();">Hide Solution</a><div><br><br>No solution exists or Error: ' . $e;        
        //     return result;
        // }
    



         
                  $("div#solution").html(result2);

                  //$("div#solution").html("No Exist Solution Or Error!!!");                




        });

        loadSavedSudokus(last100recent);

    });
//////////// Solution by JS only ////////////
  // added

const UNASSIGNED = 0;

function usedInRow(matrix, row, num) {
  for (let col = 0; col < matrix.length; col++) {
    if (matrix[row][col] === num) {
      return true;
    }
  }
  return false;
}

function usedInCol(matrix, col, num) {
  for (let row = 0; row < matrix.length; row++) {
    if (matrix[row][col] === num) {
      return true;
    }
  }
  return false;
}

function usedInBox(matrix, boxStartRow, boxStartCol, num) {
  for (let row = 0; row < 3; row++) {
    for (let col = 0; col < 3; col++) {
      if (matrix[row + boxStartRow][col + boxStartCol] === num) {
        return true;
      }
    }
  }
  return false;
}

function isSafe(matrix, row, col, num) {
  return (
    !usedInRow(matrix, row, num) &&
    !usedInCol(matrix, col, num) &&
    !usedInBox(matrix, row - (row % 3), col - (col % 3), num)
  );
}
function solveSudoku(matrix) {
  let row = 0;
  let col = 0;
  let checkBlankSpaces = false;

  for (row = 0; row < matrix.length; row++) {
    for (col = 0; col < matrix[row].length; col++) {
      if (matrix[row][col] === UNASSIGNED) {
        checkBlankSpaces = true;
        break;
      }
    }
    if (checkBlankSpaces === true) {
      break;
    }
  }
  if (checkBlankSpaces === false) {
    return true;
  }

  for (let num = 1; num <= 9; num++) {
    if (isSafe(matrix, row, col, num)) {
      matrix[row][col] = num;
      if (solveSudoku(matrix)) {
        return true;
      }
      matrix[row][col] = UNASSIGNED;
    } else {
      break;   // added
    }
  }
  return false;
}

function sudokuSolver(matrix) {
  if (solveSudoku(matrix) === true) {
    return matrix;
  } else {
    //alert('NO SOLUTION EXISTS!') ;  // added
    return 'NO SOLUTION EXISTS!';
  }
  
}


///////////////////////////////////////////////
0 Likes

#7

pressing solve
if solvable OK
if Sudoku un-solvable FREEZES

0 Likes

#8

The answer that others are implying but not stating explicitly is that you simply don’t recurse. In other words, when you do not call the function then the recursion will end. m_hutley provides sample code of that. Note that in that sample code, if execution == 10000000 then myrecursivefunction does not call itself.

It is possible to use iteration instead of recursion. I have an article that explains how to do that but they don’t want me to link to my website from here. It is also available in Microsoft and C# Corner. If anyone gets a stack error from recursion then they can use iteration instead.

0 Likes

#9

why getting errors… ?

Uncaught SyntaxError: Unexpected token export
script-JS-NoPHP7.js?2019-04-18:131 Uncaught SyntaxError: Unexpected token {


'use strict';

// sudokuSolverFile.js
export function sudokuSolver(matrix) {   // line 72
  if (solveSudoku(matrix) === true) {
    return matrix;
  }
  return 'NO SOLUTION EXISTS!';
}


// script.js
import { sudokuSolver } from 'sudokuSolverFile';  // line 131

const { sudokuSolver } = sudokuSolverFile;
0 Likes

#10

why getting errors?

0 Likes

#11

SyntaxError: export declarations may only appear at top level of a module sudokuSolverFile.js:87
SyntaxError: import declarations may only appear at top level of a module script-JS-NoPHP7.js:156

in firefox
export // 87
import // 156 other file
well

0 Likes

#12

Without being able to see those files, I’d say that the syntax error says it all.

0 Likes

#13

what you mean…

is Not export and import statements supported … ?

0 Likes

#14

The syntax error says that you aren’t allowed to use them in the way that you are attempting to use them.

0 Likes

#15

can you provide some reference eBook or URL… ?

0 Likes

#16

Only when you’re including the script as

<script type="module" src="my-script.js"></script>

Another approach (which, unlike native modules, also works for IE) is to use a module bundler like webpack. Note that if you want to import NPM modules, you’ll have to use a bundler as node resolves modules differently.

BTW the "use scrict" is not necessary either way, it’s already the default mode for module type scripts.

0 Likes

#17
<script type="module" src="./sudokuSolverFile.js?2019-04-19"></script>

export { sudokuSolver };

getting for this >>>

import sudokuSolver from ‘./sudokuSolverFile’;
Uncaught SyntaxError: Unexpected identifier
Error here ^^^

now how import? export No error

0 Likes

#18

The syntax seems to be valid as far as I can see… but you should see a link to the exact location of the error in the console.

Also note though that you have to include the file extension when using native imports. And above you where using a named export, now you’re trying to import the default export.

0 Likes

#19

2019-04-15_16-05-42

well, with .js the same exactly…

0 Likes

#20

No it should be

import { sudokuSolver } from './sudokuSolverFile.js'

The sudokuSolverFile.js doesn’t have to be included with a <script> tag then.

But that your import is in line 155 looks suspicious, it should be somewhere at the top of your script.js file. What does the preceding statement or expression look like?

0 Likes