Categories: Game
Tags: JavaScript
This project has been the hardest for me yet! I got the idea of writing a sudoku game that can generate a board and check the user’s solution after trying a hard sudoku problem while having lunch with my math professor, Dr. Yasskin.
This project is the first time I used an HTML preprocessor (Haml) to simplify writing the HTML. Using Haml reduces the amount of markup by using loops and nesting selectors.
I began with the board, which is organized into 3 horizontal rows which each contain
3 squares, which each contain 9 cells. This requires a few nested do loops which
is written below:
.sudoku
-3.times do
.s-row
-3.times do
.square
-9.times do
.cell
%span.label 1
%span.valueThere is also a bar of numbers below the board which can be used to insert numbers into the board:
.row
.col
.numbers-bar
- (1..9).each do |i|
.number= iI used Sass as a preprocessor and first declared several variables:
$cell-size: 50px;
$hover-color: #BBDDFF;
$selected-color: #76A8FF;
$error-color: #E58080;
$valid-color: #95E595;
$bar-color: complement($hover-color);The markup for styling the board is shown below. Making the squares float: left and
every third square clear: both is important to get the board to display correctly.
When hovering over a cell, I highlight it with background-color: $hover-color. I
also added contextual classes .selected, .error, and .valid for cells that
have been clicked on, cells that have invalid input, and cells that have valid input.
.sudoku {
width: 475px;
margin: auto;
.square {
float: left;
border: 1px solid #000;
.cell {
float: left;
position: relative;
height: $cell-size;
width: $cell-size;
background: #fff;
border: 1px solid #000;
box-sizing: content-box;
&:hover {
background-color: $hover-color;
.label {color: #333;}
}
&.selected {
background-color: $selected-color;
.label {color: #333;}
}
&.error {
background-color: $error-color;
}
&.valid {
background-color: $valid-color;
}
.label {
position: absolute;
color: #aaa;
top: 1px;
left: 2px;
font-size: 12px;
}
.value {
display: block;
font-size: 30px;
color: #000;
width: 100%;
height: 100%;
text-align: center;
}
}
.cell:nth-child(3n+1) {
clear: both;
}
}
}After the UI was built to my satisfaction, I started thinking about the board
generation code. I decided to represent the board as a 2D array (although
later I realized I could have simply used an 81-item 1D array). Any value from the
board can be retrieved by its row index and column index: array[row-index][column-index].
I generated the starting board in two ways. For easy games, I took a solved board and removed either 4 or 5 numbers within each square. For more difficult games, I found a valid existing board that was not solved and permuted the numbers, the row groups, column groups, and the rows and columns within each group of three. This jumbles the board but ensures it remains valid.
Permuting all the numbers is conceptually simple: one way to implement a permutation is to increment each number on the board so that all 1’s become 2’s, all 2’s become 3’s, and so on until you reach 9’s which become 1’s. However, I wanted a slightly more complex method: randomly selecting a number instead of incrementing. The key to this method is making sure each number is only mapped to a single output number and ensuring that the same number is not used twice for different inputs. If that doesn’t make sense to you, take a look at the function I wrote:
permuteNumbers: function(board) {
var permutedBoard = util.clone(board);
var left = [1,2,3,4,5,6,7,8,9];
var linked = [1,2,3,4,5,6,7,8,9];
// generate permutation
for (var i=0;i<9;i++) {
var index=0; var replacement=0;
while (index==replacement) { // they can't be the same
index = util.getRand(0,left.length-1);
replacement = left[index]; // randomly select a replacement number
}
left.splice(index,1); // prevent number from being used again
linked[i] = replacement; // replace 1-9 with its replacement
}
// implement: switch board numbers
for (var j=0;j<9;j++) {
for (var k=0;k<9;k++) {
if (board[j][k]) { // if board cell not 0
permutedBoard[j][k] = linked[board[j][k]-1]; // replace numbers with their links
}
}
}
return permutedBoard;
}Note: this function is encapsulated within the puzzle object, so this function
is actually a method on that object, hence the method: function() syntax.
The permutation algorithm I wrote for swapping rows and columns in the same group works by iterating through rows/columns, randomly selecting two to swap, and continuing until all row and column groups have had a swap:
permuteRowCol: function(board) {
var pBoard = util.clone(board);
for (var i=0;i<3;i++) { // manipulate rows and cols in same group
var row1 = util.getRand(0,2) + 3*i; // 1st row to manipulate
var row2 = util.getRand(0,2) + 3*i; // 2nd row to manipulate
while (row2==row1) {
row2 = util.getRand(0,2) + 3*i; // make sure row2 !== row1
}
var temp = pBoard[row1]; // store first row
pBoard[row1] = pBoard[row2]; // swap rows
pBoard[row2] = temp; // swap rows
var col1 = util.getRand(0,2)+3*i; var col2 = util.getRand(0,2)+3*i;
while (col2==col1) {
col2 = util.getRand(0,2)+3*i; // column 2 cannot be same as column 1
}
for (var j=0;j<pBoard.length;j++) { // loop through rows
var temp = pBoard[j][col1]; // store col 1 current cell value
pBoard[j][col1] = pBoard[j][col2]; // swap col1 cell w/ col2 cell
pBoard[j][col2] = temp; // swap col2 cell w/ col1 cell
}
}
return pBoard;
}While similar in concept, permuting row and column groups of 3 is different than the algorithm above. For the row groups, two are swapped at random using a temporary variable (no iteration necessary). For the column groups, the rows are iterated over and a temporary variable inside the loop is used to swap all cells withing the columns. The complete function is shown below:
permuteRowColGroups: function(board) {
var pBoard = util.clone(board);
var rowGrp1 = util.getRand(0,2) * 3+1; // 1st row to manipulate
var rowGrp2 = util.getRand(0,2) * 3+1; // 2nd row to manipulate
while (rowGrp2==rowGrp1) {
rowGrp2 = util.getRand(0,2) * 3+1; // make sure rowGrp2 !== rowGrp1
}
var temp1 = [pBoard[rowGrp1-1], pBoard[rowGrp1], pBoard[rowGrp1+1]]; // store row group 1
pBoard[rowGrp1-1] = pBoard[rowGrp2-1];
pBoard[rowGrp1] = pBoard[rowGrp2];
pBoard[rowGrp1+1] = pBoard[rowGrp2+1];
pBoard[rowGrp2-1] = temp1[0];
pBoard[rowGrp2] = temp1[1];
pBoard[rowGrp2+1] = temp1[2];
var colGrp1 = util.getRand(0,2) * 3+1; var colGrp2 = util.getRand(0,2) * 3+1;
while (colGrp2==colGrp1) {
colGrp2 = util.getRand(0,2) * 3+1; // column 2 cannot be same as column 1
}
for (var j=0;j<9;j++) { // loop through rows
var temp2 = {
first: pBoard[j][colGrp1-1],
second: pBoard[j][colGrp1],
third: pBoard[j][colGrp1+1]
}; // store col group 1 current cell values
pBoard[j][colGrp1-1] = pBoard[j][colGrp2-1];
pBoard[j][colGrp1] = pBoard[j][colGrp2];
pBoard[j][colGrp1+1] = pBoard[j][colGrp2+1];
pBoard[j][colGrp2-1] = temp2.first;
pBoard[j][colGrp2] = temp2.second;
pBoard[j][colGrp2+1] = temp2.third;
}
return pBoard;
}Now came the really hard part: writing the board solver function. I actually ended
up writing two different solver functions, one as a brute force algorithm
and one as a “smarter” algorithm. One important concept that I learned to keep
in mind while writing these functions is to distinguish between mutable cells
and immutable cells. Mutable cells are open or blank cells which are initially set
to 0 and can be changed by the function. Immutable cells are hints already given
on the puzzle board - they cannot be changed by the function because they are a
known part of the solution.
The brute force method starts by assuming a 1 in the first mutable cell and checks for validity in ascending numerical order before moving onto the next mutable cell. If no number is valid for the cell, it retreats to the previous cell and increments the cell value. As you can imagine, this takes a long time for certain board configurations, but at least it guarantees to find a solution if one exists.
While conceptually simple, implementing the algorithm proved more difficult. I first
realized I would need a Boolean variable which indicates whether the the function
is proceeding forward or backwards at the moment - I named this variable goingBack.
Note that it is within the vars object where I stored many other variables.
Next, I needed a way to determine where the first mutable cell is located, which I
did with a simple nested for loop and two variables storing the row and column
indices.
To start the solver, a for loop is initiated to iterate over all cells. Variables
i and j are declared as row and column indices, respectively. Next, an if
statement determines whether we have a mutable or immutable cell. Immutable cells
are simple skipped while mutable cells are dealt with. Otherwise, if the cell is
immutable and we’re going backwards (checking vars.goingBack), we keep going
back by decreasing the counter by 2.
Inside the if statement, we determine the current square number (0-8), cell number
(also 0-8), and declare the initial value we’re using (1). If we’re backtracking,
we increment the current cell’s value and check if it is now above 9, in which case
we reset the value to 0 and keep going back. If we’re at the beginning and we reach
the value 9 with an invalid board, the function throws an error and a message is
displayed (although this shouldn’t happen with valid boards).
Next, if we’re not backtracking, we start with the value 1 and check whether the
board is valid in its current configuration (we’ll get to this checking function later).
If the board is not valid, we increment! If the value goes over 9, we start backtracking
(change vars.goingBack to false) and start over. Otherwise, we keep whatever value
is valid and go on to the next cell.
bruteSolve: function(board) {
vars.goingBack = false;
var solved = util.clone(board); // start with the board hints
var freeRow; var freeCol;
// get first mutable cell
for (var a=0;a<9;a++) {
for (var b=0;b<9;b++) {
if (!board[a][b]) {
freeRow = a; freeCol = b; a = 9; b = 9;
}
}
}
// start search algorithm
for (var a=0;a<81;a++) {
var i = Math.floor(a/9);
var j = a % 9;
// all cells we need to change (ones that have 0s)
if (!board[i][j]) {
var sqnum = Math.floor(i/3) * 3+Math.floor(j/3);
var cell = 3*(i%3)+(j%3);
var value = 1; // initial value tried for each cell
// if backtracking, increment current cell and check if >9
if (vars.goingBack) {
value = solved[i][j] + 1;
if (value > 9) {
// check if this is the first cell
if (i==freeRow && j==freeCol) {
console.log('Cannot be solved!');
return false;
}
// set cell to 0 and keep going back
solved[i][j] = 0;
a = a - 2;
}
}
// try values 1-9
while (value < 10) {
// if not valid, increment value
if (!puzzle.checkValid(value,solved,i,j,sqnum,cell)) {
value++;
// if value > 9, go back!
if (value > 9) {
solved[i][j] = 0;
if (i==freeRow && j==freeCol) {
console.log('Cannot be solved!');
return false;
}
vars.goingBack = true;
a = a - 2;
}
}
// otherwise, assume the value
else {
solved[i][j] = value;
vars.goingBack = false;
break;
}
}
}
// non-zero cells (immutables)
else if (vars.goingBack) {
// keep going back
a = a - 2;
}
}
return solved;
}The “smarter” algorithm uses essentially the same method as brute force, but it first eliminates some of the solution board possibilities by checking the adjacent row, square, and column cells for each cell.
solveBoard: function(board) {
vars.goingBack = false;
var solved = util.clone(board); // start with the board hints
var markedup = util.clone(vars.boards.empty); // empty 9x9
var bySquares = puzzle.rowsToSquares(board);
// check cols, rows, squares for hints
for (var i=0;i<9;i++) {
for (var j=0;j<9;j++) {
var avail = [1,2,3,4,5,6,7,8,9];
// total numbers available - we'll decrease this by checking rows, cols, boxes
for (var k=0;k<9;k++) {
var rnum = board[i][k];
var cnum = board[k][j];
var sqnum = Math.floor(i/3) * 3+Math.floor(j/3);
var cellnum = bySquares[sqnum][k];
if (rnum && avail.indexOf(rnum) >= 0) {
avail.splice(avail.indexOf(rnum),1);
// cell cannot have same value as another on the same row
}
if (cnum && avail.indexOf(cnum) >= 0) {
avail.splice(avail.indexOf(cnum),1);
// cell cannot have same value as another on the same column
}
if (cellnum && avail.indexOf(cellnum) >= 0) {
avail.splice(avail.indexOf(cellnum),1);
// cell cannot have same value as another on the same row
}
}
markedup[i][j] = avail; // populate
}
}
// now we have the values each cell cannot be, so we start our algorithm
var freeRow; var freeCol;
// get first mutable cell
for (var a=0;a<9;a++) {
for (var b=0;b<9;b++) {
if (!solved[a][b]) {
freeRow = a; freeCol = b; a = 9; b = 9;
}
}
}
// start search algorithm
for (var a=0;a<81;a++) {
var i = Math.floor(a/9);
var j = a % 9;
// all cells we need to change (ones that have 0s)
if (!board[i][j]) {
var sqnum = Math.floor(i/3)*3+Math.floor(j/3);
var cell = 3*(i%3)+(j%3);
var value = markedup[i][j][0]; // initial value tried for each cell
var index = 0;
// if backtracking
if (vars.goingBack) {
index = markedup[i][j].indexOf(solved[i][j]); // current index in markup
// if this is the last value available, keep going back
if (index + 1 == markedup[i][j].length) {
// check if this is the first cell in sudoku board
if (i==freeRow && j==freeCol) {
console.log('Cannot be solved!');
return false;
}
else { // set cell to 0 and keep going back
solved[i][j] = 0;
a = a - 2;
}
}
else { // otherwise start from next value in available
index++;
value = markedup[i][j][index];
vars.goingBack = false;
}
}
// try all values available in markup
while (index < markedup[i][j].length) {
// if not valid, increment index and value
if (!puzzle.checkValid(value,solved,i,j,sqnum,cell)) {
index++;
value = markedup[i][j][index];
if (index >= markedup[i][j].length) { // if no more values, go back!
if (i==freeRow && j==freeCol) {
console.log('Cannot be solved!');
return false;
}
solved[i][j] = 0;
vars.goingBack = true;
a = a - 2;
}
}
// otherwise, assume the value
else {
solved[i][j] = value;
vars.goingBack = false;
break;
}
}
}
// non-zero cells (immutables)
else if (vars.goingBack) {// keep going back
a = a - 2;
}
}
return solved;
}Remember that checkValid(num,solBoard,row,col,sq,cell) function we called in both
solving functions? It plays a vital role by checking whether the current configuration
is a valid board.
checkValid: function(num,solBoard,row,col,sq,cell) {
// num = number to check; solBoard = partially filled solution board;
// row = row of cell to check; col = column of cell to check (zero-indexed)
var asSquares = puzzle.rowsToSquares(solBoard);
for (var i=0;i<9;i++) {
if (num == solBoard[row][i] && i!== col) {
return false;
}
if (num == solBoard[i][col] && i!== row) {
return false;
}
if (num == asSquares[sq][i] && i!== cell) {
return false;
}
}
return true;
}I also added useful keyboard functionality, including:
delete key to clear a cellFor keyboard numerical input, the userPick function determines which cell is selected
and then performes the appropriate action based on the input:
userPick: function(number) {
var $curCell = $(".cell.selected");
var $curSq = $curCell.parent();
var cellNum = $curCell.index();
var colGroup = $curSq.index();
var srowNum = $curSq.parent().index();
var row = srowNum*3 + Math.floor(cellNum/3);
var col = colGroup*3 + (cellNum%3);
var $target = $curCell.find('.value');
if (!$target.hasClass('immutable')) {
// 0-9
if (number >= 1 && number <= 9) {
var correct = (number === vars.boards.solution[row][col]);
if (correct) {
$curCell.addClass('valid');
$curCell.removeClass('error');
}
else {
$curCell.addClass('error');
$curCell.removeClass('valid');
}
$target.text(number);
}
// backspace / delete
else if (number == (8-48) || number == (46-48)) {
$target.text("");
$curCell.removeClass("valid error");
}
}
}For board navigation using the arrow keys, some nested if/elseif statements are
required to test for the specific keys as well as handling behavior at the end of
rows and columns:
moveSelected: function(arrowKey) {
puzzle.storeDOMviewCells();
var $cellsInRows = vars.DOMview;
var $selCell = $(".cell.selected");
var $curSq = $selCell.parent();
var cellNum = $selCell.index();
var colGroup = $curSq.index();
var srowNum = $curSq.parent().index();
var row = srowNum*3 + Math.floor(cellNum/3);
var col = colGroup*3 + (cellNum%3);
$selCell.removeClass('selected');
// left
if (arrowKey == 37) {
if (col==0) {
if (row==0) {$selCell.addClass('selected');}
else {$cellsInRows[row-1][8].addClass('selected');}
}
else {$cellsInRows[row][col-1].addClass('selected');}
}
// up
else if (arrowKey == 38) {
if (row==0) {$cellsInRows[row][col].addClass('selected');}
else {$cellsInRows[row-1][col].addClass('selected');}
}
// right
else if (arrowKey == 39) {
if (col==8) {
if (row==8) {$selCell.addClass('selected');}
else {$cellsInRows[row+1][0].addClass('selected');}}
else {$cellsInRows[row][col+1].addClass('selected');}
}
// down
else if (arrowKey == 40) {
if (row==8) {$cellsInRows[row][col].addClass('selected');}
else {$cellsInRows[row+1][col].addClass('selected');}
}
}This took a LONG time. Like, it took a few weeks to get it right and fully complete.
One mistake I made which derailed me for a while was assuming that initiating a
variable and setting it equal to an existing array created a new array. Actually,
all that does is create a reference to the original array. I had to write a
function clone() that returns a copy of a given array.
Another difficulty was implementing the solving algorithms correctly. I can’t tell you how many hours I spent debugging my functions. But I persevered, pushed through, and now I can proudly present the finished product.
See the Pen [Dynamic Sudoku](https://codepen.io/acrenwelge/pen/bqybpv/) by Andrew ([@acrenwelge](https://codepen.io/acrenwelge)) on [CodePen](https://codepen.io).