Checking validity of NxN Sudoku

Question

Given a multi-dimensional array representing a board in Sudoku, the function should be able to return whether the sudoku is valid or not.

Examples:

var goodSudoku = [
  [7,8,4, 1,5,9, 3,2,6],
  [5,3,9, 6,7,2, 8,4,1],
  [6,1,2, 4,3,8, 7,5,9],

  [9,2,8, 7,1,5, 4,6,3],
  [3,5,7, 8,4,6, 1,9,2],
  [4,6,1, 9,2,3, 5,8,7],

  [8,7,6, 3,9,4, 2,1,5],
  [2,4,3, 5,6,1, 9,7,8],
  [1,9,5, 2,8,7, 6,3,4]
];

var badSudoku = [
  [1,1,1, 1,1,1,  2,2,2],
  [5,3,9, 6,7,2, 8,4,1],
  [6,1,2, 4,3,8, 7,5,9],

  [9,2,8, 7,1,5, 4,6,3],
  [3,5,7, 8,4,6, 1,9,2],
  [4,6,1, 9,2,3, 5,8,7],

  [8,7,6, 3,9,4, 2,1,5],
  [2,4,3, 5,6,1, 9,7,8],
  [1,9,5, 2,8,7, 6,3,4]
];

validSudoku(badSudoku); // false;
validSudoku(goodSudoku); // true;

Specific questions

• How can I improve my function? What am I doing bad/good?
• Is my algorithm efficient? Advice on it?

Here is my code

function validSudoku(data) {
    var valid = true, 
        temp = [], 
        data,
        side,
        slot;


    // Check wrong size
    if (data[0].length !== data.length) valid = false;

    // slot*slot
    slot = Math.sqrt(data.length);

    // Verifiy horizontal
    data.forEach(function(arr) {
        valid = valid && arr.every(function(val, i) { return arr.indexOf(i + 1) > -1; });
    });

    // Verifiy vertical lines
    data.forEach(function(arr, i) {
        temp  = data.map(function(val) { return val[i]; });
        valid = valid && arr.every(function(val, i) { return temp.indexOf(i + 1) > -1; });
    });

    // Verifiy boxes
    for (var i = 0; i < slot; i++) {

        data.forEach(function(val, e) {
            side  = val.slice(slot * i, slot * i + slot);
            temp  = temp.concat(side);

            if ((e+1) % slot == 0 && e > 0) {
                for (var j = 1; j <= data.length; j++)
                    if (temp.indexOf(j) < 0) valid = false;                 
                temp = [];
            }

        });

    }
    return valid;
}

Answer 1

There are a few problems with your validation, and the code itself could be a bit neater.

First up, your code will try to validate impossible puzzles. Sudoku puzzles need to be square-sided You check that the puzzle is square, but your slot-size is not valid. It assumes a side that is a perfect square (4, 9, 16, etc.).

Additionally, you only check the first row is the right length, I suspect your code will validate as true if one of the rows has an extra element (with a carefully-chosen value).

In multiple places you set valid = false, and in those places you should just return false. You know the puzzle is not valid, so why continue checking?

Finally, it would be nice if you could make the checking generic. There are 3 things to check:

1. all expected elements in each row are present
2. all expected elements in each column are present
3. all expected elements in each mini-square are present.

I would try to put that together as a collection of functions for each check:

var extractions = [
    {   name: "rows",
        get:  function(data,span,block,member){
                  return data[block][member];
              }
    },
    {   name: "cols",
        get:  function(data,span,block,member) {
                  return data[member][block];
              }
    },
    {   name: "minis",
        get:  function(data,span,block,member) {
                  var coloff = (block % span) * span;
                  var rowoff = (block / span) * span;
                  return data[rowoff + (member / span)][coloff + (member % span)];
              }
    },
]

function isvalid(data) {
    var size = data.length;
    var slot = Math.sqrt(size);
    for (var block = 0; block < size; block++) {
        if (data[block].length != size) {
            return false;
        }
        for (var ext = 0; ext < extractions.length; ext++) {
            var tmp = [];
            for (var member = 0; member < size; member++) {
                tmp.push(extractions[ext].get(data, slot, block, member));
            }
            for (var i = 1; i <= size; i++) {
                if (tmp.indexOf(i) < 0) {
                    return false;
                }
            }
        }
    }
    return true;
}

Answer 2

Checking that the board's square is pretty simple:

function isSquare(board) {
  return board.every(function (row) {
    return row.length === board.length;
  });
}

You'll might still want to check that its sides are themselves perfect squares. E.g. a 7x7 sudoku board is hard to divide into boxes. I'll leave that up to you though.

To check the rows and columns, I'd suggest adding a transpose function, just to make things easier. It'll "flip" the board from an array or rows to an array of columns, like so:

function transpose(board) {
  return board.map(function (_, index) {
    return board.map(function (row) {
      return row[index];
    });
  });
}

And to find the boxes, here's a fairly naïve implementation (note that it assumes the sides are perfect squares):

function boxes(board) {
  var size = Math.sqrt(board.length),
      boxes = [];

  for(var r = 0, rl = board.length ; r < rl ; r++) {
    var row = board[r];
    for(var c = 0, cl = row.length ; c < cl ; c++) {
      var box = (r / size | 0) * size + (c / size | 0);
      boxes[box] || (boxes[box] = []);
      boxes[box].push(row[c]);
    }
  }

  return boxes;
}

With that you can write three simple functions:

function validateRows(board) {
  return board.every(isSequential);
}

function validateColumns(board) {
  return transpose(board).every(isSequential);
}

function validateBoxes(board) {
  return boxes(board).every(isSequential);
}

Now, as for that isSequential function. Here's one way to go about it: Sort the "group" (row, column, or box) in ascending order, and loop through it to check that it's sequential, starting at 1:

function isSequential(group) {
  var sorted = group.slice().sort(function (a, b) {
    return a - b;
  });

  for(var i = 0, l = sorted.length ; i < l ; i++) {
    if(sorted[i] !== i + 1) {
      return false;
    }
  }

  return true;
}

I'm slicing the group to get a copy, because sort modifies the array it's called on, so it'd modify the board itself, and we don't want that. I'm also supplying a comparison callback, because the default comparator is lexicographic (i.e. it'll sort [1, 2, 10] as [1, 10, 2]).

However, there's also a "clever" way, using some bitwise operations:

function isSequential(group) {
  var sum = group.reduce(function (sum, digit) {
    return sum | 1 << (digit - 1);
  }, 0);

  return sum === (1 << group.length) - 1;
}

What's happening here is that each digit sets a bit in the sum. A 1 will set the 1st (least significant) bit, a 2 will set the 2nd bit and so on.

So, taking the first row of the goodSudoku, here's what happens:

Digit | Sum (in binary)
-------------------------
7     | 001000000
8     | 011000000
4     | 011001000
1     | 011001001
5     | 011011001
... and so on

If all the digits 1-9 are present in the row/column/box, the sum should be 111111111 (nine 1s) in binary. And that just happens to be equal to \$2^9 - 1\$. This will work as long as no digit goes above 30 (since JS bitwise operations treat stuff as signed 32-bit integers). So it's not quite NxN, but it'll work up to 30x30.

Regardless of which implementation you pick, you end up with something like:

function validSudoku(board) {
  return isSquare(board) && validateRows(board) && validateColumns(board) && validateBoxes(board);
}