Pure JavaScript Sudoku generator/solver

Read all posts about "" game

Several years ago I already showed you a Sudoku generator/solver using PHP and another using AS3, today I am showing you the JavaScript version because I am going to create a visual Sudoku game using some popular frameworks.

Here it is what you are going to get:

You can start with an empty Sudoku, so it will generate a random one, or populate sudoku array to have it solved.

Here is the source code:

<html>
<head>

<script>

// we start with an empty sudoku...
var sudoku = new Array(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0);

// ... and we solve it!!
solve(sudoku);

// given a sudoku cell, returns the row
function returnRow(cell) {
	return Math.floor(cell / 9);
}

// given a sudoku cell, returns the column
function returnCol(cell) {
	return cell % 9;
}

// given a sudoku cell, returns the 3x3 block
function returnBlock(cell) {
	return Math.floor(returnRow(cell) / 3) * 3 + Math.floor(returnCol(cell) / 3);
}

// given a number, a row and a sudoku, returns true if the number can be placed in the row
function isPossibleRow(number,row,sudoku) {
	for (var i=0; i<=8; i++) {
		if (sudoku[row*9+i] == number) {
			return false;
		}
	}
	return true;
}

// given a number, a column and a sudoku, returns true if the number can be placed in the column
function isPossibleCol(number,col,sudoku) {
	for (var i=0; i<=8; i++) {
		if (sudoku[col+9*i] == number) {
			return false;
		}
	}
	return true;
}

// given a number, a 3x3 block and a sudoku, returns true if the number can be placed in the block
function isPossibleBlock(number,block,sudoku) {
	for (var i=0; i<=8; i++) {
		if (sudoku[Math.floor(block/3)*27+i%3+9*Math.floor(i/3)+3*(block%3)] == number) {
			return false;
		}
	}
	return true;
}

// given a cell, a number and a sudoku, returns true if the number can be placed in the cell
function isPossibleNumber(cell,number,sudoku) {
	var row = returnRow(cell);
	var col = returnCol(cell);
	var block = returnBlock(cell);
	return isPossibleRow(number,row,sudoku) && isPossibleCol(number,col,sudoku) && isPossibleBlock(number,block,sudoku);
}

// given a row and a sudoku, returns true if it's a legal row
function isCorrectRow(row,sudoku) {
	var rightSequence = new Array(1,2,3,4,5,6,7,8,9);
	var rowTemp= new Array();
	for (var i=0; i<=8; i++) {
		rowTemp[i] = sudoku[row*9+i];
	}
	rowTemp.sort();
	return rowTemp.join() == rightSequence.join();
}

// given a column and a sudoku, returns true if it's a legal column
function isCorrectCol(col,sudoku) {
	var rightSequence = new Array(1,2,3,4,5,6,7,8,9);
	var colTemp= new Array();
	for (var i=0; i<=8; i++) {
		colTemp[i] = sudoku[col+i*9];
	}
	colTemp.sort();
	return colTemp.join() == rightSequence.join();
}

// given a 3x3 block and a sudoku, returns true if it's a legal block 
function isCorrectBlock(block,sudoku) {
	var rightSequence = new Array(1,2,3,4,5,6,7,8,9);
	var blockTemp= new Array();
	for (var i=0; i<=8; i++) {
		blockTemp[i] = sudoku[Math.floor(block/3)*27+i%3+9*Math.floor(i/3)+3*(block%3)];
	}
	blockTemp.sort();
	return blockTemp.join() == rightSequence.join();
}

// given a sudoku, returns true if the sudoku is solved
function isSolvedSudoku(sudoku) {
	for (var i=0; i<=8; i++) {
		if (!isCorrectBlock(i,sudoku) || !isCorrectRow(i,sudoku) || !isCorrectCol(i,sudoku)) {
			return false;
		}
	}
	return true;
}

// given a cell and a sudoku, returns an array with all possible values we can write in the cell
function determinePossibleValues(cell,sudoku) {
	var possible = new Array();
	for (var i=1; i<=9; i++) {
		if (isPossibleNumber(cell,i,sudoku)) {
			possible.unshift(i);
		}
	}
	return possible;
}

// given an array of possible values assignable to a cell, returns a random value picked from the array
function determineRandomPossibleValue(possible,cell) {
	var randomPicked = Math.floor(Math.random() * possible[cell].length);
	return possible[cell][randomPicked];
}

// given a sudoku, returns a two dimension array with all possible values 
function scanSudokuForUnique(sudoku) {
	var possible = new Array();
	for (var i=0; i<=80; i++) {
		if (sudoku[i] == 0) {
			possible[i] = new Array();
			possible[i] = determinePossibleValues(i,sudoku);
			if (possible[i].length==0) {
				return false;
			}
		}
	}
	return possible;
}

// given an array and a number, removes the number from the array
function removeAttempt(attemptArray,number) {
	var newArray = new Array();
	for (var i=0; i<attemptArray.length; i++) {
		if (attemptArray[i] != number) {
			newArray.unshift(attemptArray[i]);
		}
	}
	return newArray;
}

// given a two dimension array of possible values, returns the index of a cell where there are the less possible numbers to choose from
function nextRandom(possible) {
	var max = 9;
	var minChoices = 0;
	for (var i=0; i<=80; i++) {
		if (possible[i]!=undefined) {
			if ((possible[i].length<=max) && (possible[i].length>0)) {
				max = possible[i].length;
				minChoices = i;
			}
		}
	}
	return minChoices;
}

// given a sudoku, solves it
function solve(sudoku) {
	var saved = new Array();
	var savedSudoku = new Array();
	var i=0;
	var nextMove;
	var whatToTry;
	var attempt;
	while (!isSolvedSudoku(sudoku)) {
		i++;
		nextMove = scanSudokuForUnique(sudoku);
		if (nextMove == false) {
			nextMove = saved.pop();
			sudoku = savedSudoku.pop();
		}
		whatToTry = nextRandom(nextMove);
		attempt = determineRandomPossibleValue(nextMove,whatToTry);
		if (nextMove[whatToTry].length>1) {
			nextMove[whatToTry] = removeAttempt(nextMove[whatToTry],attempt);
			saved.push(nextMove.slice());
			savedSudoku.push(sudoku.slice());
		}
		sudoku[whatToTry] = attempt;
	}
	showSudoku(sudoku,i);
}


// given a solved sudoku and the number of steps, prints out the sudoku
function showSudoku(sudoku,i) {
	var sudokuText = "";
	var solved = "\n\nSolved in "+i+" steps";
	for (var i=0; i<=8; i++) {
		for (var j=0; j<=8; j++) {
			sudokuText+=" ";
			sudokuText+=sudoku[i*9+j];
			sudokuText+=" ";
			if (j!=8) {
				sudokuText+="|";
			}
		}
		if (i!=8) {
			sudokuText+="\n---+---+---+---+---+---+---+---+---\n";
		}
	}
	sudokuText+=solved;
	document.write("<pre>"+sudokuText+"</pre>");
}

</script>
</head>
<body>
</body>
</html>

That was easy, but things will get interesting when I’ll show you this engine in a game, meanwhile download the source code.

Get the most popular Phaser 3 book

Through 202 pages, 32 source code examples and an Android Studio project you will learn how to build cross platform HTML5 games and create a complete game along the way.

Get the book

215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 100 rounds
// 10000000
// 2 Cars
// 2048
// A Blocky Christmas
// A Jumping Block
// A Life of Logic
// Angry Birds
// Angry Birds Space
// Artillery
// Astro-PANIC!
// Avoider
// Back to Square One
// Ball Game
// Ball vs Ball
// Ball: Revamped
// Balloon Invasion
// BallPusher
// Ballz
// Bar Balance
// Bejeweled
// Biggification
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Boom Dots
// Bouncing Ball
// Bouncing Ball 2
// Bouncy Light
// BoxHead
// Breakout
// Bricks
// Bubble Chaos
// Bubbles 2
// Card Game
// Castle Ramble
// Chronotron
// Circle Chain
// Circle Path
// Circle Race
// Circular endless runner
// Cirplosion
// CLOCKS - The Game
// Color Hit
// Color Jump
// ColorFill
// Columns
// Concentration
// Crossy Road
// Crush the Castle
// Cube Jump
// CubesOut
// Dash N Blast
// Dashy Panda
// Deflection
// Diamond Digger Saga
// Don't touch the spikes
// Dots
// Down The Mountain
// Drag and Match
// Draw Game
// Drop Wizard
// DROP'd
// Dudeski
// Dungeon Raid
// Educational Game
// Elasticity
// Endless Runner
// Erase Box
// Eskiv
// Farm Heroes Saga
// Filler
// Flappy Bird
// Fling
// Flipping Legend
// Floaty Light
// Fuse Ballz
// GearTaker
// Gem Sweeper
// Globe
// Goat Rider
// Gold Miner
// Grindstone
// GuessNext
// Helicopter
// Hero Emblems
// Hero Slide
// Hexagonal Tiles
// HookPod
// Hop Hop Hop Underwater
// Horizontal Endless Runner
// Hundreds
// Hungry Hero
// Hurry it's Christmas
// InkTd
// Iromeku
// Jet Set Willy
// Jigsaw Game
// Knife Hit
// Knightfall
// Legends of Runeterra
// Lep's World
// Line Rider
// Lumines
// Magick
// MagOrMin
// Mass Attack
// Math Game
// Maze
// Meeblings
// Memdot
// Metro Siberia Underground
// Mike Dangers
// Mikey Hooks
// Nano War
// Nodes
// o:anquan
// One Button Game
// One Tap RPG
// Ononmin
// Pacco
// Perfect Square!
// Perfectionism
// Phyballs
// Pixel Purge
// PixelField
// Planet Revenge
// Plants Vs Zombies
// Platform
// Platform game
// Plus+Plus
// Pocket Snap
// Poker
// Pool
// Pop the Lock
// Pop to Save
// Poux
// Pudi
// Pumpkin Story
// Puppet Bird
// Pyramids of Ra
// qomp
// Quick Switch
// Racing
// Radical
// Rebuild Chile
// Renju
// Rise Above
// Risky Road
// Roguelike
// Roly Poly
// Run Around
// Rush Hour
// SameGame
// SamePhysics
// Save the Totem
// Security
// Serious Scramblers
// Shrink it
// Sling
// Slingy
// Snowflakes
// Sokoban
// Space Checkers
// Space is Key
// Spellfall
// Spinny Gun
// Splitter
// Spring Ninja
// Sproing
// Stabilize!
// Stack
// Stairs
// Stick Hero
// String Avoider
// Stringy
// Sudoku
// Super Mario Bros
// Surfingers
// Survival Horror
// Talesworth Adventure
// Tetris
// The Impossible Line
// The Moops - Combos of Joy
// The Next Arrow
// Threes
// Tic Tac Toe
// Timberman
// Tiny Wings
// Tipsy Tower
// Toony
// Totem Destroyer
// Tower Defense
// Trick Shot
// Tunnelball
// Turn
// Turnellio
// TwinSpin
// vvvvvv
// Warp Shift
// Way of an Idea
// Whack a Creep
// Wheel of Fortune
// Where's my Water
// Wish Upon a Star
// Word Game
// Wordle
// Worms
// Yanga
// Yeah Bunny
// Zhed
// zNumbers