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;
}

• Ismael Miguel: You can greatly simplify by summing the value of all the rows. For a 9*9 sudoku, you would have a total of 45 on each column and line. you sum them all and you are good to go! If the sum is different, just return false in the middle. If you finish the loop, return true.
• James Montagne: @IsmaelMiguel What good is summing? If you fill the entire board with nothing but 5s, all rows and columns will also sum to 45.
• Ismael Miguel: @JamesMontagne You are right. My bad. I should go back to math...

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;
}

• Afonso Matos: You have a little typo on extractions[e], there is no e variable (I suppose it's ext). Thanks for the advices.
• rolfl: You're welcome, and fixed, and the code is completely untested..... just a suggestion ;-)

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);
}

• justhalf: The assumption is definitely false. You can have all numbers in all rows and columns while having many duplicates in the mini-boxes. For example put 123456789 in the first row, then shift by 1 until the last row. Another way to look at this is that the mini-box rule won't be there if the rules on rows and columns are sufficient.
• Flambino: @justhalf D'oh! Of course you're right. I shouldn't try to be clever when I'm tired. I'll fix the answer. Thanks for the correction!