Skip to content

Instantly share code, notes, and snippets.

@nathanleclaire
Last active August 29, 2015 13:56
Show Gist options
  • Save nathanleclaire/9283652 to your computer and use it in GitHub Desktop.
Save nathanleclaire/9283652 to your computer and use it in GitHub Desktop.
This will take in a Sudoku possible solution as a string and validate it.
var solutions = [
'192356847643817952875429631584173296761592384239684175458231769926748513317965428',
'359784612821369745764251839247893561698517324513426987485932176976148253132675498',
'359784612821369745764251839547823961698517324213496587485932176976148253132675498'
];
function isValidSolution(grid) {
if (typeof grid !== 'string' || grid.length !== 81) {
return false;
} else {
return testRows(grid) && testColumns(grid) && testBoxes(grid);
}
}
function getEmptyBitmap() {
var bitmap = [];
for(var i=1; i <= 9; i++) {
bitmap[i] = 0;
}
return bitmap;
}
function checkBitmap(bitmap) {
for(var i=1; i <= 9; i++) {
if (bitmap[i] !== 1) {
return false;
}
}
return true;
}
function testRows(grid) {
var isValid = true;
var i, j, bitmap;
for(i=0; i < 81; i += 9) {
bitmap = getEmptyBitmap();
for(j=0; j < 9; j++) {
bitmap[parseInt(grid[i+j], 10)] += 1;
}
isValid = isValid && checkBitmap(bitmap);
}
return isValid;
}
function testColumns(grid) {
var isValid = true;
for(var i=0; i < 81; i += 9) {
var bitmap = getEmptyBitmap();
for(var j=0; j < 9; j++) {
bitmap[parseInt(grid[i+j], 10)] += 1;
}
isValid = isValid && checkBitmap(bitmap);
}
return isValid;
}
function breakIntoBoxes(grid) {
var boxes = [];
var i, j, k;
for(i=0; i < 81; i += 27) {
for(j=i; j < (i+9); j += 3) {
var box = '';
for(k=0; k < 27; k += 9) {
box += grid[k+j];
box += grid[k+j+1];
box += grid[k+j+2];
}
boxes.push(box);
}
}
return boxes;
}
function testBoxes(grid) {
var isValid = true;
var boxes = breakIntoBoxes(grid);
boxes.forEach(function(box) {
var bitmap = getEmptyBitmap();
for(var i=0; i < box.length; i++) {
bitmap[parseInt(box[i], 10)] += 1;
}
isValid = isValid && checkBitmap(bitmap);
});
return isValid;
}
solutions.forEach(function(solution) {
console.log(isValidSolution(solution));
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment