Appendix A
Solution to the Last Homework:
Sudoku Generator
The following code implements the Sud okuGenerator class used for generating a
Sudoku puzzle, which is not guaran te ed to have a unique solution. At the end of the
code there is a deļ¬nition of the ra nd() function used for ge nerating integer random
numbers.
/*
* Constructs a SudokuGenerator object instance. After constructing
* an object instance, you should call the methods reset(),
* shuffle(), removeNumbers(), and getClues().
*
* Example:
* var clues, g = new SudokuGenerator();
* g.reset();
* g.shuffle();
* g.removeNumbers(30);
* clues = g.getClues();
*/
var SudokuGenerator = function() {
this.clues = null;
};
/*
* Resets a SudokuGenerator object. Whenever you want to re-create
* a puzzle, this method should be called first.
*/
SudokuGenerator.prototype.reset = function() {
this.clues = [
[8, 2, 7, 1, 5, 4, 3, 9, 6],
[9, 6, 5, 3, 2, 7, 1, 4, 8],
[3, 4, 1, 6, 8, 9, 7, 5, 2],
[5, 9, 3, 4, 6, 8, 2, 7, 1],
[4, 7, 2, 5, 1, 3, 6, 8, 9],
[6, 1, 8, 9, 7, 2, 4, 3, 5],
265
[7, 8, 6, 2, 3, 5, 9, 1, 4],
[1, 5, 4, 7, 9, 6, 8, 2, 3],
[2, 3, 9, 8, 4, 1, 5, 6, 7],
];
};
/*
* Shuffles the numbers in the puzzle grid.
*/
SudokuGenerator.prototype.shuffle = function() {
var i;
for (i = 0; i < 500; i++) {
this.swapBlockCols(rand(3), rand(3));
this.swapBlockRows(rand(3), rand(3));
this.swapColsInBlock(rand(3), rand(3), rand(3));
this.swapRowsInBlock(rand(3), rand(3), rand(3));
}
};
/*
* Swaps two rows.
* Parameters:
* r1, r2: the indexes of rows to be swapped (indexes between
* zero and eight)
*/
SudokuGenerator.prototype.swapRows = function(r1, r2) {
var i, tmp;
for (i = 0; i < 9; i++) {
tmp = this.clues[r1][i];
this.clues[r1][i] = this.clues[r2][i];
this.clues[r2][i] = tmp;
}
};
/*
* Swaps two columns.
* Parameters:
* c1, c2: the indexes of columns to be swapped (indexes between
* zero and eight)
*/
SudokuGenerator.prototype.swapCols = function(c1, c2) {
var i, tmp;
for (i = 0; i < 9; i++) {
tmp = this.clues[i][c1];
this.clues[i][c1] = this.clues[i][c2];
this.clues[i][c2] = tmp;
}
};
266 Appendix A. Solution to the Last Homework: Sudoku Generator
/*
* Swaps two rows within a row of 3x3 blocks.
* Parameters:
* br: the index of a row of 3x3 blocks (an integer between zero
* and two)
* r1, r2: the indexes of rows to be swapped. Indexes are
* relative to the given row of 3x3 blocks and can be
* integers between zero and two.
*/
SudokuGenerator.prototype.swapRowsInBlock = function(br, r1, r2) {
this.swapRows(br * 3 + r1, br * 3 + r2);
};
/*
* Swaps two columns within a column of 3x3 blocks.
* Parameters:
* bc: the index of a column of 3x3 blocks (an integer between
* zero and two)
* c1, c2: the indexes of columns to be swapped. Indexes are
* relative to the given column of 3x3 blocks and can be
* integers between zero and two.
*/
SudokuGenerator.prototype.swapColsInBlock = function(bc, c1, c2) {
this.swapCols(bc * 3 + c1, bc * 3 + c2);
};
/*
* Swaps two rows of 3x3 blocks.
* Parameters:
* r1, r2: the indexes of rows to be swapped (integers between
* zero and two)
*/
SudokuGenerator.prototype.swapBlockRows = function(r1, r2) {
for (i = 0; i < 3; i++) {
this.swapRows(r1 * 3 + i, r2 * 3 + i);
}
};
/*
* Swaps two columns of 3x3 blocks.
* Parameters:
* c1, c2: the indexes of columns to be swapped (integers between
* zero and two)
*/
SudokuGenerator.prototype.swapBlockCols = function(c1, c2) {
for (i = 0; i < 3; i++) {
this.swapCols(c1 * 3 + i, c2 * 3 + i);
}
};
Appendix A. Solution to the Last Homework: Sudoku Gen erator 267
/*
* Randomly removes numbers from the puzzle grid by setting them to
* null.
* Parameters:
* numClues: the number of clues to be left in the grid
*/
SudokuGenerator.prototype.removeNumbers = function(numClues) {
var i, j;
var remain = 81;
while (remain > numClues) {
i = rand(9);
j = rand(9);
if (this.clues[i][j] != null) {
this.clues[i][j] = null;
remain--;
}
}
};
/*
* Returns a two-dimensional array of clues. Empty cells are set to
* null.
*/
SudokuGenerator.prototype.getClues = function() {
return this.clues;
};
/*
* Returns a non-negative random integer.
* Parameters:
* n: the upper limit of a returned number
* Returns:
* A random integer between zero and n - 1
*/
var rand = function(n) {
return Math.floor(Math.random() * n);
}
The following two metho ds are additions to the Sudoku class. They are u sed to check
whether a puzzle has a unique solution:
/*
* Checks whether a puzzle has a unique solution.
* Returns:
* If the puzzle has a single solution, then the method returns
* true.
*/
268 Appendix A. Solution to the Last Homework: Sudoku Generator
Sudoku.prototype.isSolutionUnique = function() {
var i, j;
this.empty = [];
this.solutions = 0;
//Search for all the empty cells:
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
if (this.board[i][j].getNumber() == null) {
//Store the row and column indexes of the cell into the array
//empty:
this.empty.push({row: i, col: j});
}
}
}
this.checkCell(0);
//The checkCell() recursive function stores the number of
//solutions in the property solutions. If there is more than one
//solution, then solutions is set to two.
if (this.solutions == 1) {
return true;
}
else {
return false;
}
};
/*
* This is a recursive function used by the isSolutionUnique()
* method.
*/
Sudoku.prototype.checkCell = function(n) {
var number;
for (number = 1; number < 10; number++) {
//Try to insert numbers from one to nine, one at a time.
if (this.setNumber(number, this.empty[n].row,
this.empty[n].col)) {
//If the insertion was successful.
if (n == this.empty.length - 1) {
//If the last of the empty cells was filled, we have a
//solution.
this.solutions++;
}
else {
//Otherwise, go and check the next of the empty cells
//recursively.
this.checkCell(n + 1);
}
}
Appendix A. Solution to the Last Homework: Sudoku Gen erator 269
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.