/*
****************
* Introduction *
****************
* Welcome to my Sudoku Solver. This world implements a recursive backtracking algorithm to solve
* a randomized Sudoku puzzle of varying difficulty.
*
* The Sudoku puzzle is NP-complete with an enormous search space. There are a total of
* 6670903752021072936960 valid boards, and a total of 81! (or 5.797126e+120) possible board
* combinations overall, invalid boards included. To put this into perspective, the most advanced
* variant of the Nazi Enigma machine "only" allowed for a possible of 6.5592937e+79 combinations.
*
* Some of the information above was quoted from the following research paper, which seems to be
* recognized as the go-to sudoku mathematics paper:
* http://www.afjarvis.staff.shef.ac.uk/sudoku/felgenhauer_jarvis_spec1.pdf
*
* Clearly this is not a problem which can be solved by brute-force.
*
* By instead using a recursive backtracking algorithm, my solution can solve most puzzles in under
* 100 easily computed moves, thus leaving us with a tiny time complexity. Obviously it feels much
* slower when viewing my world because it is slowed down to a clock speed of 13Hz. In reality, the
* solution takes on average under 16 milliseconds to complete (on my cpu). I originally had this
* down to 5 milliseconds, but the resulting solution was far slower with an average of 1500 moves.
*
* A Sudoku puzzle of maximum difficulty contains only 17 "hints" (pre-solved cells). This means
* that even in a worst-case scenario, the algorithm only needs a maximum recursive depth of 64
* (81 - 17). Therefore this algorithm also has a relatively small space complexity.
*
****************
* Shortcomings *
****************
* As my solution is recursive, it solves the entire puzzle in a single function call. This makes it
* impossible to make use of the Mind. I understand the idea of having a World/Mind environment is
* that on each clock cycle, the Mind is provided with a limited view of the World, allowing it to
* calculate the next move. This is not possible in my case - all of the computational work is done
* as soon as the World begins.
*
* In an attempt to emulate how the World/Mind interaction should work each change made to the board
* attempting to find a solution is recorded in the moves list. Then on each clock tick, each move
* is replayed back to the World so it can display how the algorithm worked at a human-readable
* speed.
*
*****************
* External code *
*****************
* As explained in an email I sent to you some time ago, my World makes use of code written by
* David J. Rager, found in the file "/uploads/conroc25/sudoku.js". This code is used to generate
* the puzzle as it's pretty complicated stuff.
*
************
* Solution *
************
* The algorithm first finds the cell with the fewest possible values. It then fills the selected
* cell with each valid value that it could be, then moves on the next cell. If a cell cannot be
* found with any possible values, we have made a mistake so we need to backtrack. The solution
* simply continues in this manner until the board is solved.
*/
var moves = {} /* A list of arrays which stores each move taken the solve the puzzle */
var move = 0; /* The index of current move being recorded or replayed */
var time = 0; /* Time taken to solve puzzle */
const show3d = false;
const GRID_SIZE = 9;
const SQUARE_SIZE = 100;
const SQUARE_HEIGHT = 1;
const MAX_POS = GRID_SIZE * SQUARE_SIZE;
const START_RADIUS = 1000;
const MAX_RADIUS = MAX_POS * 3;
/* A sample of Google's "web-safe" colors */
const COLOR_AMBER = 0xFFC107;
const COLOR_BLACK = 0x000000;
const COLOR_BLUE = 0x2196F3;
const COLOR_BLUE_GREY = 0x607D8B;
const COLOR_BLUE_LIGHT = 0x03A9F4;
const COLOR_BROWN = 0x795548;
const COLOR_CYAN = 0x00FFFF;
const COLOR_GREEN = 0x4CAF50;
const COLOR_GREEN_LIGHT = 0x8BC34A;
const COLOR_GREY = 0x9E9E9E;
const COLOR_INDIGO = 0x3F51B5;
const COLOR_LIME = 0xCDDC39;
const COLOR_ORANGE = 0xFF9800;
const COLOR_ORANGE_DEEP = 0xFF5722;
const COLOR_PINK = 0xE91E63;
const COLOR_PURPLE = 0x9C27B0;
const COLOR_PURPLE_DEEP = 0x673AB7;
const COLOR_RED = 0xF44336;
const COLOR_TEAL = 0x009688;
const COLOR_WHITE = 0xFFFFFF;
const COLOR_YELLOW = 0xFFEB3B;
const COLOR_DEFAULT = 0xFFFFCC;
var GRID = new Array(GRID_SIZE); /* A matrix of meshes to store graphical objects */
var NUMBERS = new Array(GRID_SIZE); /* A matrix of the numerical values on board */
var SOLVED = new Array(GRID_SIZE); /* Another matrix used when calculating solution */
var CLOCKTICK = 75;
var MAXSTEPS = Number.MAX_SAFE_INTEGER; /* Run until board is solved */
const SCREENSHOT_STEP = 50;
function World() {
var self = this;
var score = 0;
/* Initialize the 3 empty matrices */
function initGrid() {
for (var x = 0; x < GRID_SIZE; x++) {
GRID[x] = new Array(GRID_SIZE);
NUMBERS[x] = new Array(GRID_SIZE);
SOLVED[x] = new Array(GRID_SIZE);
for (var y = 0; y < GRID_SIZE; y++) {
GRID[x][y] = null;
NUMBERS[x][y] = 0;
SOLVED[x][y] = 0;
}
}
}
/*
* Paints a numerical value to a coordinate on the board
* n = value to display
* c = color to display
*/
function paint(x, y, n, c) {
/* No point re-painting the same value */
if (NUMBERS[x][y] === n) {
return;
}
/* If we want to make square blank */
if (n === 0 && GRID[x][y] !== null) {
threeworld.scene.remove(GRID[x][y]);
GRID[x][y] = null;
return;
} else if (n === 0) {
return;
}
/* Remove whatever is at x,y */
if (GRID[x][y] !== null) {
threeworld.scene.remove(GRID[x][y]);
GRID[x][y] = null;
}
var loader = new THREE.TextureLoader();
loader.load(getFileName(n, c), function(thetexture) {
thetexture.minFilter = THREE.LinearFilter;
var tmpX = x * SQUARE_SIZE + 10; /* +10 to compensate for border width */
var tmpY = y * SQUARE_SIZE + 10;
GRID[x][y] = drawSquare(tmpX, tmpY, SQUARE_SIZE - 10, COLOR_GREEN);
GRID[x][y].material = new THREE.MeshBasicMaterial({
map: thetexture
});
});
}
/* Draw a rectangle of specified size on the scene and return the mesh */
function drawRectangle(x, y, width, height, color) {
var shape = new THREE.BoxGeometry(width, SQUARE_HEIGHT, height);
var mesh = new THREE.Mesh(shape);
mesh.material.color.setHex(color);
mesh.position.x = translate(x, width);
mesh.position.y = 0;
mesh.position.z = translate(y, height);
threeworld.scene.add(mesh);
return mesh;
}
/* Draw a horizontal line on the scene and return the mesh */
function drawHorizontalLine(y, width, color) {
return drawRectangle(0, y, 900, width, color);
}
/* Draw a vertical line on the scene and return the mesh */
function drawVerticalLine(x, width, color) {
return drawRectangle(x, 0, width, 900, color);
}
/* Draw a square on the scene and return the mesh */
function drawSquare(x, y, size, color) {
return drawRectangle(x, y, size, size, color);
}
/* Draw the empty board with all borders etc. */
function draw() {
/* Draw outer borders */
drawSquare(-10, -10, 920, COLOR_BLACK);
/* Draw background */
drawSquare(0, 0, 900, COLOR_WHITE);
/* Draw inner borders */
for (var i = 1; i < GRID_SIZE; i++) {
var width = (i % 3 == 0) ? 10 : 5;
drawVerticalLine(i * SQUARE_SIZE, width, COLOR_BLACK);
drawHorizontalLine(i * SQUARE_SIZE, width, COLOR_BLACK);
}
}
this.endCondition;
this.newRun = function() {
this.endCondition = false;
initGrid();
updateStatus('Generating', move);
/*
* getScript() is a JQuery function which allows you to run JavaScript located in an
* external file. Unfortunately, the foreign codebase only lives inside the anonymous
* function passed to it. If you wanted to allow students to do this globally, you could
* probably use the information found in the function's documentation, as internally it
* seems to be a simple AJAX call: https://api.jquery.com/jquery.getscript/
*/
$.getScript('/uploads/conroc25/sudoku.js', function() {
/*
* The Sudoku class is stored in the sudoku.js file referred to above. This class was
* NOT designed or even modified by myself whatsoever
*/
var su = new Sudoku();
su.newGame(); /* Creates a new board */
var matrix = su.matrix; /* Returns an array of 81 integers representing the board */
/* Convert the array to a 9x9 matrix, and paint each value on our board */
var i = 0;
for (var x = 0; x < 9; x++) {
for (var y = 0; y < 9; y++) {
if (matrix[i] != 0) {
paint(x, y, matrix[i], 'g');
NUMBERS[x][y] = matrix[i];
SOLVED[x][y] = matrix[i];
}
i++;
}
}
var t0 = performance.now();
solve(getSmallestCell()[0], getSmallestCell()[1]);
var t1 = performance.now();
time = parseFloat((t1 - t0).toFixed(5));
});
if (true) {
threeworld.init2d(START_RADIUS, MAX_RADIUS, COLOR_DEFAULT);
draw();
}
};
this.getState = function() {
return NUMBERS;
};
this.nextStep = function() {
/* Check if there are any more moves to display */
if (moves[move] == null) {
this.endCondition = true;
updateStatus('Finished in ' + time + 'ms' + ' (actual computation time)', move);
} else {
/* If there are, paint the next move and continue on */
var x = moves[move][0];
var y = moves[move][1];
var n = moves[move][2];
updateStatus(
(n === 0) ? 'Backtracking' : ('Letting (' + x + ',' + y + ') = ' + n), move);
if (true) {
paint(x, y, n, 'r');
}
NUMBERS[x][y] = n;
move++;
}
};
this.endRun = function() {
};
this.getScore = function() {
return score;
};
}
function debug(x) {
console.log(x);
}
/* A simple function to get an image file's full path name */
function getFileName(n, type) {
return '/uploads/conroc25/' + n + (type == 'g' ? 'g' : 'r') + '.png';
}
/* Returns a list of all the possible values that can be placed in a specific cell */
function getOptions(i, j) {
var options = {}
/* Initialize the list with keys 1-9 */
for (var x = 1; x < 10; x++) {
options[x] = 0;
}
/* Check which values 1-9 are allowed horizontally */
for (x = 0; x < 9; x++) {
if (SOLVED[x][j] !== 0) {
options[SOLVED[x][j]] = 1;
}
}
/* Do the same vertically */
for (var y = 0; y < 9; y++) {
if (SOLVED[i][y] !== 0) {
options[SOLVED[i][y]] = 1;
}
}
/*
* A Sudoku board is filled with 3x3 smaller sub-grids. We need to check what values are allowed
* within whatever grid i,j falls inside. k, l is the top-left cell of the the sub-grid i,j
* lives inside
*/
var k = 0;
var l = 0;
/* Find x-coordinate of top-left of cell of 3x3 sub-grid */
if (i >= 0 && i <= 2) {
k = 0;
} else if (i >= 3 && i <= 5) {
k = 3;
} else {
k = 6;
}
/* Find y-coordinate of top-left of cell of 3x3 sub-grid */
if (j >= 0 && j <= 2) {
l = 0;
} else if (j >= 3 && j <= 5) {
l = 3;
} else {
l = 6;
}
/* Check which values i,j could be, now taking into account values in 3x3 sub-grid */
for (x = k; x < (k + 3); x++) {
for (y = l; y < (l + 3); y++) {
if (SOLVED[x][y] !== 0) {
options[SOLVED[x][y]] = 1;
}
}
}
for (x = 1; x < 10; x++) {
if (options[x] === 0) {
options[x] = x;
} else {
options[x] = 0;
}
}
return options;
}
/*
* This function begins with a matrix SOLVED which is identical to NUMBERS (initially unsolved). We
* recursively "solve" one cell with a valid value, then jump to the next.
*/
function solve(x, y) {
if (isFull()) {
move = 0;
return true;
}
var newX = getSmallestCell()[0];
var newY = getSmallestCell()[1];
/* If the cell value is not 0 then assume it is already a solved cell */
if (SOLVED[x][y] !== 0) {
return solve(newX, newY);
}
/* For values 1-9, check if the value is allowed in the current cell */
for (var i = 1; i < 10; i++) {
possibilities = getOptions(x, y);
var valid = possibilities[i] === i;
if (!valid) {
continue;
}
/*
* If it is legal, place the value in the cell. Then update the moves list so we can replay
* how the board was solved later
*/
SOLVED[x][y] = i;
moves[move] = [x, y, i];
move++;
/* Recursively solve the next cell */
var solved = solve(newX, newY);
/* If solved() returns true then we have finished solving the board */
if (solved) {
return true;
} else {
/* Otherwise, the current value will not work. We need to backtrack */
SOLVED[x][y] = 0;
moves[move] = [x, y, 0];
move++;
}
}
return false;
}
/* Checks if the board is full (solved) */
function isFull() {
for (var x = 0; x < 9; x++) {
for (var y = 0; y < 9; y++) {
if (SOLVED[x][y] === 0) {
return false;
}
}
}
return true;
}
/* Find the first, unsolved cell on the board */
function getFirstCell() {
for (var x = 0; x < 9; x++) {
for (var y = 0; y < 9; y++) {
if (SOLVED[x][y] === 0) {
return [x, y];
}
}
}
}
/* Returns the *amount* of values a specified cell could be */
function getNumOptions(x, y) {
var options = getOptions(x, y);
var num = 0;
for (var i = 0; i < 9; i++) {
if (options[i] !== 0) {
num++;
}
}
return num;
}
/* Find the next cell on the board with the fewest possible values */
function getSmallestCell() {
var newX = getFirstCell()[0];
var newY = getFirstCell()[1];
var val = getNumOptions(newX, newY);
for (var x = 0; x < 9; x++) {
for (var y = 0; y < 9; y++) {
if (SOLVED[x][y] !== 0) {
continue;
}
if (getNumOptions(x, y) < val) {
newX = x;
newY = y;
val = getNumOptions(x, y);
}
}
}
return [newX, newY];
}
/* Find the next cell on the board */
function getNextCell(x, y) {
x++;
if (x > 8) {
x = 0;
y++;
}
return [x, y];
}
/* A modified translate function with the same purpose as your original */
function translate(x, size) {
return x + (size / 2) - (MAX_POS / 2);
}
/* Self explanatory */
function updateStatus(x, y) {
var t = parseFloat((1000 / CLOCKTICK).toFixed(1));
var s1 = "Status: " + x + "<br/ >";
var s2 = "Moves: " + y + "<br />";
var s3 = "Displaying at ~" + t + "Hz";
var status = s1 + s2 + s3;
$("#user_span1").html(status);
}