JavaScript Sudoku Puzzle Solver | 2
JavaScript Sudoku Puzzle Solver
Grid Entry Page
When the user has finished specifying the dimensions and symbols, they need to click the “Grid Entry” button which will activate the grid entry page.
<div id="details" style="position:absolute; visibility:hidden">
<h2>Grid Entry</h2>
<div id="detailsSymbols"></div>
<div id="detailsGrid"></div>
<button onclick="solverInit();">Solve</button>
</div>
This page contains two empty <div> elements which may only be filled in once the Puzzle Specification page has been completed. This is done in the detailsInit() function…
function detailsInit()
{
var w = parseInt(document.getElementById('startWidth').value);
var h = parseInt(document.getElementById('startHeight').value);
var s = document.getElementById('startSymbols').value;
if ( w*h > s.length )
{
debug("there are not enough symbols for this configuration");
return;
}
var oDetails = document.getElementById('detailsSymbols');
oDetails.innerHTML = w.toString() + 'x' + h.toString() + ', using ' + s;
The first step is to retrieve and validate the dimensions and symbols entered on the Puzzle Specification page. If there aren't enough symbols to complete the puzzle, an alert message is displayed at the bottom of the page and the function returns leaving the user still on the Puzzle Specification page.
Once validated a new SudokuPuzzle object is created to keep track of the state of the puzzle…
thePuzzle = new SudokuPuzzle(w, h, s);
thePuzzle.display(document.getElementById('detailsGrid'),true);
setPage('details');
}
The SudokuPuzzle class is first constructed using the dimensions of the puzzle; the width and height of the groups and a string containing all the symbols.
function SudokuPuzzle(width,height,tokens)
{
this.width = width;
this.height = height;
this.tokens = tokens.split('');
// create 2D grid to store initial state
this.grid = new Array();
var i,j, n = width*height;
for ( i = 0; i < n; i++ )
{
var row = new Array();
for ( j = 0; j < n; j++ ) row.push(' ');
this.grid.push(row);
}
// initialise iteration state variables
this.nIteration = 0;
this.nIdle = 0;
}
The constructor also initializes a two dimensional grid to store the starting position of the puzzle.
Once constructed, the puzzle is displayed on the Grid Entry page inside a <DIV> element. This is done using the display() method…
SudokuPuzzle.prototype.display = function(target, bInput)
{
// display the puzzle in the target <DIV>
if ( arguments.length < 2 ) bInput = false;
var n = this.width * this.height;
var i,j;
// generate <table> to display grid
var html = new Array();
html.push('<table border=2>');
for ( i = 0; i < n; i++ )
{
html.push('<tr>');
for ( j = 0; j < n; j++ )
{
var bColour = ((Math.floor(i/this.height)%2) ^
(Math.floor(j/this.width)%2)) != 0;
var sColour = bColour ? "white" : "lime";
var sStyle = 'background:' + sColour + ';';
sStyle += " width:35px; height:30px;";
html.push('<td align=center valign=middle style="' + sStyle + '">');
if ( bInput ) html.push(this.displayInputCell(i,j));
else html.push(this.displayCell(i,j));
html.push('</td>')
}
html.push('</tr>');
}
html.push('</table>');
target.innerHTML = html.join('');
}
The display() method generates the HTML for a table containing a cell for each cell in the puzzle grid. To distinguish the different groups within the grid, an alternating pattern of white and lime green backgrounds are set on the table cells (feel free to choose your own color scheme). The function actually performs two tasks, determined by the bInput argument; to generate the <INPUT> elements for the Grid Entry page and to display the grid state in the Solver page.
SudokuPuzzle.prototype.displayInputCell = function(i,j)
{
var value = this.grid[i][j];
if ( value == ' ' ) value = '';
var id = 'sudoku_' + i + '_' + j;
return '<input style="width:30px" id="' + id +
'" value="' + value +
'" onkeydown="gridKey(this,event);">';
}
The displayInputCell() method generates the HTML for a cell in the Grid Entry page. The grid of <INPUT> elements is organized using the “id” attribute with the row and column value encoded into the name. This will be used to read the values back just prior to showing the Solver page. As a convenience to the user, the <INPUT> elements handle the onkeydown event to allow navigation around the grid using the arrow keys (see the source code for details).
SudokuPuzzle.prototype.displayCell = function(i,j)
{
var value = this.grid[i][j];
var sStyle = "";
if ( value == ' ' )
{
// if no value supplied, display potential solutions
if ( this.solution )
{
value = this.solution[i][j].c;
if ( value.length > 1 ) sStyle += 'color:red';
}
else value = ' ';
}
else
{
// original values are displayed in bold.
sStyle += 'font-weight:bold';
}
return '<span style="' + sStyle + '">' + value + '</span>';
}
The displayCell() method generates a <SPAN> element with either the original value (from the Grid Entry page) or the proposed solution (or solutions). The SudokuPuzzle code works out the values of the cells by first proposing all possible values for each cell (stored as a string of the available symbols) and eliminating the ones that don’t fit. When the solution string has more than one character, it's not the final solution so it's colored red.
Solver Page
Once the starting position has been entered, the user can click the “Solve” button to move to the Solver Page…
<div id="solver" style="position:absolute; visibility:hidden">
<h2>Solver</h2>
<div id="solverGrid"></div>
<button onclick="reset(thePuzzle); nIteration=0; disp();">Reset</button>
<button onclick="nReturnCount = 0; solve();">Solve</button><br>
<button onclick="setPage('start');">New Puzzle</button>
<button onclick="setPage('details');">Grid Entry</button>
</div>
Like the Grid Entry page, the Solver page has an empty <DIV> element that must be filled in before the page is displayed. This happens in the solverInit() function…
function solverInit()
{
thePuzzle.initGrid();
thePuzzle.display(document.getElementById('solverGrid'));
setPage('solver');
}
The solverInit() function calls the initGrid() method on the SudokuPuzzle object and then displays it in the “solverGrid” section of the Solver page. This allows the SudokuPuzzle object to read the values entered by the user on the Grid Entry page.
SudokuPuzzle.prototype.initGrid = function()
{
var i,j;
var n = this.width * this.height;
for ( i = 0; i < n; i++)
{
var r = thePuzzle.grid[i];
for ( j = 0; j < n; j++)
{
var v = document.getElementById('sudoku_' + i + '_' + j).value;
if ( v != '' ) r[j] = v;
else r[j] = ' ';
}
}
}
The initGrid() method reads each <INPUT> element and inserts the value into the grid.
Now everything is in place for the program to solve the puzzle. The Solve button calls the function solve() which uses window.setTimeout() to call successive iterations in the puzzle solving logic with a half second pause between each iteration.
function solve()
{
if ( thePuzzle.iterate() ) window.setTimeout("solve();", 500);
thePuzzle.display(document.getElementById('solverGrid'));
}
The iterate() method on the SudokuPuzzle object executes a single iteration in the puzzle solving calculation. Its return value is a Boolean where true indicates that more iterations are required.
SudokuPuzzle.prototype.iterate = function()
{
if ( !this.solution )
{
this.initSolution();
return true;
}
var nReturn = this.strategies[this.nIteration++ % this.strategies.length](this);
if ( nReturn == -1 )
{
// error
return false;
}
else if ( nReturn == 0 )
{
// nothing changed
return (++this.nIdle < this.iterations.length);
}
else
{
// something changed
if ( this.isSolved() )
{
clrDebug();
debug("Finished");
return false;
}
this.nIdle = 0;
return true;
}
}
The algorithm used in the SudokuPuzzle object works by a process of elimination. Successive iterations work by eliminating potential symbols from each cell until there's only one left.
The first time the iterate() function is called, this.solution will be undefined so it calls initSolution() to prepare the puzzle object for the solving process…
SudokuPuzzle.prototype.initSolution = function()
{
// initialise the solution state
var sTokens = this.tokens.join('');
var w = this.width;
var h = this.height;
var n = this.tokens.length;
var i,j,k;
// build 2D array of potential solutions
var solution = this.solution = new Array();
// and an array of group members
var members = this.members = new Array();
for ( i = 0; i < n; i++ ) members.push(new Array());
After an initial setup, the function loops through each cell in the grid.
for ( i = 0; i < n; i++ )
{
var row = new Array();
solution.push(row);
for ( j = 0; j < n; j++ )
{
Each cell belongs to a group identified by a number from 0 to n-1.
// calculate the group number
var nGroup = Math.floor(i/h) * h + Math.floor(j/w);
Each element in this.solution is assigned to a new object. A property in this object called “c” is a string containing all the potential symbols for that cell.
var oChar;
if ( this.grid[i][j] != ' ' ) oChar = {c:this.grid[i][j]};
else oChar = {c:sTokens};
The object also records other useful information like the row and column numbers and to which group it belongs.
oChar.nRow = i;
oChar.nColumn = j;
oChar.nGroup = nGroup;
The object is then added to this.solution…
row.push(oChar);
And also added to a list of members for its group.
members[nGroup].push(oChar);
}
}
}
Created: March 27, 2003
Revised: October 21, 2005
URL: https://webreference.com/programming/javascript/gr/column16/1
Find a programming school near you