CODEWITHSUNDEEP
javascriptjqueryarraysrandom
Harsh Makadia
Harsh Makadia

Reputation: 3443

Generate a random array in Javascript/jquery for Sudoku puzzle

I want to fill the 9 x 9 grid from the array by taking care of following condition

  1. A particular number should not be repeated across the same column.
  2. A particular number should not be repeated across the same row.

When i execute the below mentioned code it fills all the 9 X 9 grid with random values without the above mentioned condition.How can I add those two condition before inserting values into my 9 X 9 Grid.

var sudoku_array = ['1','2','3','4','6','5','7','8','9'];

$('.smallbox input').each(function(index) {
    $(this).val(sudoku_array[Math.floor(Math.random()*sudoku_array.length)]);

});

My JSFIDDLE LINK

Upvotes: 4

Views: 4072

Answers (3)

Ikechi Michael
Ikechi Michael

Reputation: 489

To ensure that no number is repeated on a row, you might need a shuffling function. For columns, you'll just have to do it the hard way (checking previous solutions to see if a number exists on that column). I hope i am not confusing rows for columns, i tend to do it a lot.

It's similar to the eight queens problem in evolutionary computing. Backtracking, a pure random walk or an evolved solution would solve the problem.

This code will take a while, but it'll do the job.

You can the iterate through the returned two dimensional array, and fill the sudoku box. Holla if you need any help with that

Array.prototype.shuffle = function() {
  var arr = this.valueOf();
  var ret = [];
  while (ret.length < arr.length) {
    var x = arr[Math.floor(Number(Math.random() * arr.length))];
    if (!(ret.indexOf(x) >= 0)) ret.push(x);
  }
  return ret;
}

function getSudoku() {
  var sudoku = [];
  var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
  sudoku.push(arr);
  for (var i = 1; i < 9; i++) {

    while (sudoku.length <= i) {
      var newarr = arr.shuffle();
      var b = false;
      for (var j = 0; j < arr.length; j++) {
        for (var k = 0; k < i; k++) {
          if (sudoku[k].indexOf(newarr[j]) == j) b = true;
        }

      }
      if (!b) {
        sudoku.push(newarr);
        document.body.innerHTML += `${newarr}<br/>`;
      }
    }
  }
  return sudoku;
}

getSudoku()

Upvotes: 3

lex82
lex82

Reputation: 11317

Generating and solving Sudokus is actually not as simple as other (wrong) answers might suggest, but it is not rocket science either. Instead of copying and pasting from Wikipedia I'd like to point you to this question.

However, since it is bad practice to just point to external links, I want to justify it by providing you at least with the intuition why naive approaches fail.

If you start generating a Sudoku board by filling some fields with random numbers (thereby taking into account your constraints), you obtain a partially filled board. Completing it is then equivalent to solving a Sudoku which is nothing else than completing a partially filled board by adhering to the Sudoku rules. If you ever tried it, you will know that this is not possible if you decide on the next number by chosing a valid number only with respect to the 3x3 box, the column and the row. For all but the simplest Sudokus there is some trial and error, so you need a form of backtracking.

I hope this helps.

Upvotes: 5

ozgeneral
ozgeneral

Reputation: 6809

You need to keep track of what you have inserted before, for the following line:

 $(this).val(sudoku_array[Math.floor(Math.random()*sudoku_array.length)]);

For example you can have a jagged array (arrays of arrays, its like a 2-D array) instead of 'sudoku_array' you have created to keep track of available numbers. In fact, you can create two jagged arrays, one for column and one for rows. Since you don't keep track of what you have inserted before, numbers are generated randomly.

After you create an array that keeps available numbers, you do the following:

  • After you generate number, remove it from the jagged array's respective row and column to mark it unavailable for those row and columns.
  • Before creating any number, check if it is available in the jagged array(check for both column and row). If not available, make it try another number.

Note: You can reduce the limits of random number you generate to available numbers. If you do that the random number x you generate would mean xth available number for that cell. That way you would not get a number that is not available and thus it works significantly faster.

Edit: As Lex82 pointed out in the comments and in his answer, you will also need a backtracking to avoid dead ends or you need to go deeper in mathematics. I'm just going to keep my answer in case it gives you an idea.

Upvotes: 0

Related Questions