JavaScript Sudoku Puzzle Solver
JavaScript Sudoku Puzzle Solver
Sudoku, for the uninitiated, is a puzzle craze that has recently swept the globe, particularly in commuter circles. In the mornings each day on my way into town, I'm almost certain to spot several people furiously scribbling down numbers in a nine by nine grid in order to decipher the one magic pattern that fits. While I'm as much a puzzle fan as the next person, I prefer the challenge of finding a way to get the computer to work it all out for me.
In this article I've created a small JavaScript application that will allow users to enter the starting position of a Sudoku puzzle and then sit back and watch as the solution appears in front of them.
Sudoku Refresher
Sudoku is a style of puzzle originating from Japan where the object is to complete a square grid using a set of symbols (most commonly the symbols are the digits 1 to 9 but they can be anything). The rules are simple; any symbol must appear only once in any row, column and within its local group (see diagram).
Sudoku puzzles can come in a variety of configurations. The most common is the 3x3 form where each group is 3 cells wide by 3 cells high, The whole puzzle is made up of 3 groups wide by 3 groups high for a total of 81 cells.
Below is an example of a 3x2 form. Each 3x2 group is shown using alternating background colors and the groups themselves are arranged in a 2x3 pattern to complete a 6x6 square grid.
|
|
|
|
2 |
|
5 |
|
|
|
6 |
|
|
|
|
1 |
4 |
|
|
2 |
6 |
|
|
5 |
|
|
3 |
|
|
|
3 |
|
|
1 |
|
|
|
|
|
3 |
|
4 |
A 3x2 Sudoku puzzle. Each column, row and 3x2 group will contain one of each of the digits from 1 to 6.
Structure of a JavaScript Application
The Sudoku solver I developed has three separate screens or pages:
The Puzzle Specification page takes the dimensions of the groups and the symbols to use.
The Grid Entry page draws the entire grid on the page with text boxes in each cell. This is where the starting values are entered.
The Solver page is where the puzzle gets solved.
To separate the three pages, I've placed each one’s HTML in its own <DIV> element…
<body>
<div id="start" style="position:static; visibility:visible">
<h2>Puzzle Specification</h2>
...
</div>
<div id="details" style="position:absolute; visibility:hidden">
<h2>Grid Entry</h2>
...
</div>
<div id="solver" style="position:absolute; visibility:hidden">
<h2>Solver</h2>
...
</div>
<div id="debug"></div><button onclick="clrDebug();">Clear</button>
</body>
The three sections separate the HTML and provides a simple mechanism to display each page. Notice how only one of the three <DIV> elements has its style set to visible. An extra <DIV> element at the end provides a convenient place to print out alert messages and debug statements.
Switching pages is done using a function called setPage()…
function showPage(sPage, bShow)
{
var div = document.getElementById(sPage);
div.style.visibility = bShow ? 'visible' : 'hidden';
div.style.position = bShow ? 'static' : 'absolute';
}
function setPage(sPage)
{
showPage('start', sPage == 'start');
showPage('details', sPage == 'details');
showPage('solver', sPage == 'solver');
}
The function setPage accepts the string ID of the <DIV> element and ensures that only the requested page is visible. Hidden pages must also have their position style set to absolute to stop the browser allocating page-space for them.
Puzzle Specification Page
<div id="start" style="position:static; visibility:visible">
<h2>Puzzle Specification</h2>
Enter group dimensions:<br>
Width: <input id="startWidth" value="3" onchange="startResize();"
onfocus="this.select();"><br>
Height: <input id="startHeight" value="3" onchange="startResize();"
onfocus="this.select()"><br>
Symbols: <input id="startSymbols" value="123456789"><br>
<button onclick="detailsInit();">Grid Entry</button>
</div>
The puzzle specification page asks the user to enter the width and height of the groups. A default set of symbols is supplied but the user may change them if desired. When the dimensions of the groups are modified, the number of cells in each group change and the list of symbols must also change. As a convenience, this is handled automatically in the startResize() function…
function startResize()
{
// get dimensions of group
var w = document.getElementById('startWidth').value;
var h = document.getElementById('startHeight').value;
// choose a suitable selection
var s = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".substring(0, w*h);
// insert it into the textbox
document.getElementById('startSymbols').value = s;
}
With 36 symbols to chose from, this function will provide a symbol set for anything up to a 6x6 Sudoku puzzle.
Created: March 27, 2003
Revised: October 21, 2005
URL: https://webreference.com/programming/javascript/gr/column16/1
Find a programming school near you