solver.js

// Blank
puzzle = [
			[" "," "," "," "," "," "," "," "," "],
			[" "," "," "," "," "," "," "," "," "],
			[" "," "," "," "," "," "," "," "," "],
			[" "," "," "," "," "," "," "," "," "],
			[" "," "," "," "," "," "," "," "," "],
			[" "," "," "," "," "," "," "," "," "],
			[" "," "," "," "," "," "," "," "," "],
			[" "," "," "," "," "," "," "," "," "],
			[" "," "," "," "," "," "," "," "," "],
];



// Easy
puzzle = [
			["6","1","7","3","4"," ","8","5"," "],
			["8"," ","3"," "," ","9"," ","7"," "],
			[" "," ","2"," ","8"," "," "," "," "],
			[" ","2"," ","7"," "," "," "," "," "],
			["7"," ","5"," ","9"," ","6"," ","3"],
			[" "," "," "," "," ","4"," ","9"," "],
			[" "," "," "," ","6"," ","4"," "," "],
			[" ","7"," ","8"," "," ","9"," ","6"],
			[" ","6","1"," ","7","3","5","8","2"]
];

// easy solution for verification of checker
solution = [
			["6","1","7","3","4","2","8","5","9"],
			["8","5","3","6","1","9","2","7","4"],
			["4","9","2","5","8","7","3","6","1"],
			["3","2","9","7","5","6","1","4","8"],
			["7","4","5","1","9","8","6","2","3"],
			["1","8","6","2","3","4","7","9","5"],
			["2","3","8","9","6","5","4","1","7"],
			["5","7","4","8","2","1","9","3","6"],
			["9","6","1","4","7","3","5","8","2"]
];


// Medium
puzzle = [
			["9"," ","3","8"," "," "," "," "," "],
			[" ","8","4"," ","9"," "," ","6","2"],
			["2"," "," "," "," "," "," "," "," "],
			[" "," ","1","9"," ","7"," "," "," "],
			[" ","6"," ","2","3","8"," ","9"," "],
			[" "," "," ","5"," ","1","7"," "," "],
			[" "," "," "," "," "," "," "," ","3"],
			["6","7"," "," ","1"," ","2","8"," "],
			[" "," "," "," "," ","5","9"," ","1"],
];

// Hard
puzzle = [
			[" ","8"," ","1"," "," ","4","3"," "],
			["4"," "," "," ","3"," "," "," "," "],
			[" "," "," ","4"," ","7","9"," "," "],
			["5"," ","3"," "," "," "," ","2"," "],
			[" "," ","2"," ","7"," ","6"," "," "],
			[" ","4"," "," "," "," ","7"," ","9"],
			[" "," ","8","2"," ","6"," "," "," "],
			[" "," "," "," ","9"," "," "," ","8"],
			[" ","3","5"," "," ","1"," ","6"," "]
];


// Evil
puzzle = [
			["2","7","6","3"," "," "," "," "," "],
			[" "," "," "," "," "," ","2"," "," "],
			[" ","3"," "," "," ","4"," "," ","6"],
			[" ","6","9","8","4"," "," "," "," "],
			[" ","4"," "," "," "," "," ","5"," "],
			[" "," "," "," ","6","1","7","9"," "],
			["3"," "," ","9"," "," "," ","6"," "],
			[" "," ","7"," "," "," "," "," "," "],
			[" "," "," "," "," ","2","9","7","3"]
];

// Evil Puzzle 3,867,101,930
puzzle = [
			[" "," "," ","6"," "," "," "," ","7"],
			[" "," "," "," ","8"," "," ","1","5"],
			[" ","3","2"," "," "," "," "," ","9"],
			[" "," "," ","8"," "," "," ","6"," "],
			["8","9"," ","2"," ","3"," ","5","4"],
			[" ","7"," "," "," ","5"," "," "," "],
			["4"," "," "," "," "," ","1","7"," "],
			["1","5"," "," ","7"," "," "," "," "],
			["9"," "," "," "," ","6"," "," "," "],
];

// Evil Puzzle 3,867,101,930 with extra hints
puzzle = [
			[" "," "," ","6"," "," "," "," ","7"],
			["7"," "," "," ","8"," "," ","1","5"],
			[" ","3","2","7"," "," "," "," ","9"],
			[" "," "," ","8"," "," "," ","6"," "],
			["8","9"," ","2"," ","3"," ","5","4"],
			[" ","7"," "," "," ","5"," "," "," "],
			["4"," "," "," "," "," ","1","7"," "],
			["1","5"," "," ","7"," "," "," "," "],
			["9"," "," "," "," ","6"," "," "," "],
];

total = 45;

console.log("Puzzle:")
console.log(puzzle)

for(r=0;r<=10;r++){
	if(!check(puzzle)){
		solver(puzzle);
		console.log("Progress Puzzle:")
		console.log(puzzle)

	}else{
		console.log("Solution Found");
		break;
	}

}

// https://stackoverflow.com/questions/15052702/count-unique-elements-in-array-without-sorting
function countUnique(iterable) {
  return new Set(iterable).size;
}

// https://www.w3schools.com/jsref/jsref_reduce.asp
function getSum(total, num) {
    return parseInt(total) + parseInt(num);
}

function check(solution){

	var valid = true;

	for(i=0;i<solution.length;i++){
		// each row adds up to total
		if( solution[i].reduce(getSum) != total){
				valid = false;
				break;
			}

		// check for 9 unique digits
		if( countUnique(solution[i]) != 9){
			valid = false;
			break;
		}

		// add up each column			
		columnTotal = 0
		column = [];
				
		for(j=0;j<solution[i].length;j++){
			// check for valid digits in each space
			if( ! ( solution[i][j] >= 1 && solution[i][j] <= 9) ){
				valid = false;
				break;
			}

			columnTotal += parseInt(solution[i][j]);
			column.push(solution[j][i]);
		} // end j loop

		if(!valid){
			break;
		}

		// each column adds up to total
		if( columnTotal != total){
			valid = false;
			break;
		}

		// check for 9 unique digits
		if( countUnique(column) != 9){
			valid = false;
			break;
		}	

	} // end i loop

	// only test if still valid
	if(valid){
		for(i=0;i<solution.length/3;i++){
			// console.log(i);
			for(j=0;j<solution.length/3;j++){
				// console.log(j);
				grid = [];
				for(k=0;k<solution.length/3;k++){
					//console.log(solution[j][k+(3*j)]);
					for(m=0;m<solution.length/3;m++){
						// console.log(solution[k+(3*j)][m+(3*i)]);
						grid.push(solution[k+(3*j)][m+(3*i)]);
					}
				}

				// check for unique digits in each space	
				if( countUnique(grid) != 9){
					valid = false;
					break;
				}

				// each grid adds up to total
				if( grid.reduce(getSum) != total){
					valid = false;
					break;
				}

			} // end j loop
		} // end i loop
	} // end 2nd set of tests


	return valid;
}

function possibleValues(i,j){

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

	// return empty array is square is already played
	if( puzzle[i][j] != ' ' ){
		return []; // puzzle[i][j];
	}

	for(k=0;k<solution.length;k++){
		possibles = possibles.filter(function(e) { return e != puzzle[i][k] });
		possibles = possibles.filter(function(e) { return e != puzzle[k][j] });		
	}

	kStart = Math.floor(i/3)*3;
	kEnd = kStart + 3;

	mStart = Math.floor(j/3)*3;
	mEnd = mStart + 3;

	for(k=kStart;k<kEnd;k++){
		for(m=mStart;m<mEnd;m++){
			possibles = possibles.filter(function(e) { return e != puzzle[k][m] });
		}
	}

	return possibles;
}

function solver(puzzle){

	for(i=0;i<puzzle.length;i++){
		for(j=0;j<puzzle[i].length;j++){
			if( puzzle[i][j] != ' ' ){
				continue;
			}
			// if only 1 possible move, play move
			if( possibleValues(i,j).length == 1 ){
				puzzle[i][j]= possibleValues(i,j)[0].toString();
			}

		}
	}

	for(n=1;n<=9;n++){
	
		ngrid = [];
		// build up empty grid
		for(k=0;k<puzzle.length;k++){
			row = []
			for(m=0;m<puzzle.length;m++){
				if( puzzle[k][m] == ' ' ){
					row.push(n.toString());	
				}else{
					row.push(' ');	
				}
			}
			ngrid.push(row);
		}
	
		// search columns and rows for n
		for(k=0;k<puzzle.length;k++){
			for(m=0;m<puzzle.length;m++){
				if( puzzle[k][m] == n ){
					for(x=0;x<puzzle.length;x++){
						ngrid[x][m] = ' ';
						ngrid[k][x] = ' ';
					}
				}
			}
		}

		// search 9 grids for matches
		for(i=0;i<puzzle.length/3;i++){
			for(j=0;j<puzzle.length/3;j++){
				nfound = false;
				for(k=0;k<puzzle.length/3;k++){
					for(m=0;m<puzzle.length/3;m++){
						if( puzzle[k+(3*j)][m+(3*i)] == n ){
							nfound = true;
							break;
						}
					}					
				}
				// empty out grid if number is found
				if(nfound){
					for(k=0;k<puzzle.length/3;k++){
						for(m=0;m<puzzle.length/3;m++){
							ngrid[k+(3*j)][m+(3*i)] = ' ';
						}					
					}
				}
			}
		}	

		// place any number which only exists once in row or column
		for(k=0;k<puzzle.length;k++){
			row = 0;
			column = 0;
			for(m=0;m<puzzle.length;m++){
				if(ngrid[k][m] == n){row++}
				if(ngrid[m][k] == n){column++}
			}
			// if only 1 match play number
			if(row == 1){
				for(m=0;m<puzzle.length;m++){
					if(ngrid[k][m] == n){
						puzzle[k][m] = n.toString();
					}
				}
			}else if(column == 1){
				for(m=0;m<puzzle.length;m++){
					if(ngrid[m][k] == n){
						puzzle[m][k] = n.toString();
					}
				}
			}
		}
	}

}