I am currently trying to learn about backtracking Algorithms and have been working on a Sudoku game. I understand the basic working of the algorithm and have written a Sudoku solver using it.
My current problem is related to removing a set amount of numbers from a completed Sudoku grid to create a valid Sudoku with a unique solution.
I have checked similar questions on here but have found no answers.
Here is an example of a solved Sudoku grid:
solvedSudokuGrid =
[["8","6","1","3","4","2","9","5","7"],
["2","5","3","8","7","9","4","6","1"],
["4","9","7","6","5","1","2","3","8"],
["6","7","2","5","1","8","3","9","4"],
["9","1","4","7","2","3","6","8","5"],
["5","3","8","4","9","6","7","1","2"],
["3","4","6","2","8","5","1","7","9"],
["7","8","9","1","3","4","5","2","6"],
["1","2","5","9","6","7","8","4","3"]];
Here is the function to remove a set amount of numbers from the grid:
function removeNrs(grid, nrsToBeRemoved) {
//check if enough numbers have been removed
if (nrsToBeRemoved <= 0) {
return true;
}
//find the next random full cell and set the grid to "" on that cell to remove a number
var nextNr = shuffle(findFullCells(grid))[0];
var row = nextNr[0];
var column = nextNr[1];
var value = grid[row][column];
grid[row][column] = "";
nrsToBeRemoved--;
//check if the sudoku grid has only 1 solution if yes start recursion
if (countAllSolutions(grid) < 2){
if(removeNrs(grid, nrsToBeRemoved)){
return grid;
}
}
//if the sudoku grid has more than 1 possible solution return the grid to the previous state and backtrack
grid[row][column] = value;
return false;
}
Here is the problem: If I enter a low amount of numbers to be removed the function works. ex:
removeNrs(solvedSudokuGrid, 5); //returns a valid grid
If I enter a higher amount of numbers to be removed the function simply returns false. ex:
removeNrs(solvedSudokuGrid, 50); //returns false
From the basic debugging that I have tried I can see that the function works as long as it does not have to backtrack. If the function has to backtrack it seems to return all the way to the beginning and finish with the original grid before returning false.
Any help, explenations or things to read are much appreciated.
Edit:
https://jsfiddle.net/mg57u0mv/
Here is the complete code but some of the names of functions and variables have been changed to fit better with the whole code.
function createTable() {
var tbl = document.createElement("table");
var tbdy = document.createElement("tbody");
for (var row = 0; row < 9; row++) {
var tr = document.createElement("tr");
for (var column = 0; column < 9; column++) {
var td = document.createElement("td");
var input = document.createElement("input");
input.type = "text";
input.id = "r"+row+"c"+column;
input.className = "grid-inputs grid-inputs-row-" + row;
//input.placeholder = "[" + row + " , " + column + "]";
//input.placeholder = input.id;
if ((row+1) % 3 === 0) {
td.style.borderBottom = "3px solid black";
}
if ((column+1) % 3 === 0) {
td.style.borderRight = "3px solid black";
}
tr.appendChild(td);
td.appendChild(input);
}
tbdy.appendChild(tr);
}
tbl.appendChild(tbdy);
document.body.appendChild(tbl);
}
function createButton(text, func) {
var button = document.createElement("button");
var t = document.createTextNode(text);
button.onclick = func;
button.appendChild(t);
document.body.appendChild(button);
}
function shuffle(array) {
var counter = array.length;
var temp, index;
while (counter) {
index = Math.floor(Math.random() * counter);
counter--;
temp = array[counter];
array[counter] = array[index];
array[index] = temp;
}
return array;
}
function retrieveGrid() {
var result = [];
var rowContents = [];
for (var row = 0; row < 9; row++) {
for (var column = 0; column < 9; column++) {
rowContents.push(document.getElementsByClassName("grid-inputs-row-"+row)[column].value);
}
result.push(rowContents);
rowContents = [];
}
return result;
}
function printGrid(grid) {
for (var row = 0; row < 9; row++) {
for (var column = 0; column < 9; column++) {
document.getElementsByClassName("grid-inputs-row-"+row)[column].value = grid[row][column];
}
}
}
function checkRowColumnBlock(grid, row, column, value) {
//create row, column and block lists to be checked for doubles
var rowList = grid[row];
var columnList = [];
for (var columnCounter = 0; columnCounter < 9; columnCounter++) {
columnList.push(grid[columnCounter][column]);
}
var blockList = [];
for (var startRow = Math.floor(row/3) * 3, endRow = startRow + 3; startRow < endRow; startRow++) {
for (var startColumn = Math.floor(column/3) * 3, endColumn = startColumn + 3; startColumn < endColumn; startColumn++) {
blockList.push(grid[startRow][startColumn]);
}
}
//check row, column and block list for value
if (rowList.indexOf(value.toString()) === -1 &&
columnList.indexOf(value.toString()) === -1 &&
blockList.indexOf(value.toString()) === -1) {
return true;
} else {
return false;
}
}
function checkGrid(grid) {
for (var row = 0; row < 9; row++) {
for (var column = 0; column < 9; column++) {
if (grid[row][column] !== "") {
var value = grid[row][column];
grid[row][column] = "";
if (!checkRowColumnBlock(grid, row, column, value)) {
console.log("Invalid Grid");
return false;
}
grid[row][column] = value;
}
}
}
console.log("Valid Grid");
return true;
}
function findEmptyCells(grid) {
var result = [];
for (var row = 0; row < 9; row++){
for (var column = 0; column < 9; column++) {
if (grid[row][column] === "") {
result.push([row , column]);
}
}
}
if (result.length == 0) {
result = false;
}
return result;
}
function sortPossibilties(grid) {
var result = [];
var listOfEmptyCells = findEmptyCells(grid);
if (listOfEmptyCells === false) {
return false;
}
var listOfPossibilities = findPossibilitiesForGrid(grid);
var counter = listOfEmptyCells.length;
for (var cell = 0; cell < counter; cell++) {
result.push({"cell": listOfEmptyCells[cell], "possibilities": listOfPossibilities[cell]});
}
result.sort(function (first, second) {
return first.possibilities.length - second.possibilities.length;
});
return result;
}
function findNextEmptyCell(grid) {
var sortedEmptyCells = sortPossibilties(grid);
if (sortedEmptyCells === false) {
return false;
}
return sortedEmptyCells[0];
}
function findFullCells(grid) {
var result = [];
for (var row = 0; row < 9; row++){
for (var column = 0; column < 9; column++) {
if (grid[row][column] !== "") {
result.push([row , column]);
}
}
}
if (result.length == 0) {
result = false;
}
return result;
}
function findRandomFullCell(listOfFullCells) {
if (listOfFullCells === false) {
return false;
}
var result = listOfFullCells[Math.floor(Math.random() * listOfFullCells.length)];
return result;
}
function createEmptyGrid() {
//create grid 9x9 fill with blankspace
var grid = [];
for (var gridCounter = 0; gridCounter < 9; gridCounter++) {
grid.push(new Array(9).fill(""));
}
return grid;
}
function createIncRandomGrid(numberOfRandomCells) {
var grid = createEmptyGrid();
for (var counter = 0; counter < numberOfRandomCells; counter++) {
grid[Math.floor(Math.random() * 9)][Math.floor(Math.random() * 9)] =
Math.floor(Math.random() * 9 + 1).toString();
}
return grid;
}
function createCorRandomGrid(numberOfRandomCells) {
var grid;
do {grid = createIncRandomGrid(numberOfRandomCells);}
while (checkGrid(grid) === false);
return grid;
}
function findPossibilitiesForCell(grid, row, column) {
var possibilities = [];
for (var value = 1; value < 10; value++) {
if (checkRowColumnBlock(grid, row, column, value)) {
possibilities.push(value.toString());
}
}
return possibilities;
}
function findPossibilitiesForGrid(grid) {
var result = [];
var listOfEmptyCells = findEmptyCells(grid);
var amountOfEmptyCells = listOfEmptyCells.length;
for (var cell = 0; cell < amountOfEmptyCells; cell++) {
var row = listOfEmptyCells[cell][0];
var column = listOfEmptyCells[cell][1];
result.push(findPossibilitiesForCell(grid, row, column));
}
return result;
}
function solveSudoku(grid) {
var emptyCell = findNextEmptyCell(grid);
if (emptyCell === false) {
return true;
}
var row = emptyCell.cell[0];
var column = emptyCell.cell[1];
var valueList = shuffle(emptyCell.possibilities);
var valueListLength = valueList.length;
for (var valueIndex = 0; valueIndex < valueListLength; valueIndex++) {
if (checkRowColumnBlock(grid, row, column, valueList[valueIndex])) {
grid[row][column] = valueList[valueIndex].toString();
if (solveSudoku(grid)) {
return grid;
}
grid[row][column] = "";
}
}
return false;
}
function countAllSolutions(grid) {
var nrOfSolutions = 1;
function solveAll(grid) {
var emptyCell = findNextEmptyCell(grid);
if (emptyCell === false || nrOfSolutions > 1) {
return true;
}
var row = emptyCell.cell[0];
var column = emptyCell.cell[1];
var valueList = shuffle(emptyCell.possibilities);
var valueListLength = valueList.length;
for (var valueIndex = 0; valueIndex < valueListLength; valueIndex++) {
if (checkRowColumnBlock(grid, row, column, valueList[valueIndex])) {
grid[row][column] = valueList[valueIndex].toString();
if (solveAll(grid)) {
nrOfSolutions++;
}
grid[row][column] = "";
}
}
return false;
}
solveAll(grid);
return nrOfSolutions-1;
}
function findPossibilitiesForFullCell(grid, row, column) {
var possibilities = [];
var originalValue = grid[row][column];
grid[row][column] = "";
for (var value = 1; value < 10; value++) {
if (checkRowColumnBlock(grid, row, column, value)) {
possibilities.push(value.toString());
}
}
grid[row][column] = originalValue;
return possibilities;
}
function findPossibilitiesForFullGrid(grid) {
var result = [];
var listOfFullCells = findFullCells(grid);
var amountOfFullCells = listOfFullCells.length;
for (var cell = 0; cell < amountOfFullCells; cell++) {
var row = listOfFullCells[cell][0];
var column = listOfFullCells[cell][1];
result.push(findPossibilitiesForFullCell(grid, row, column));
}
return result;
}
function sortFullCells(grid) {
var result = [];
var listOfFullCells = findFullCells(grid);
if (listOfFullCells === false) {
return false;
}
var listOfPossibilities = findPossibilitiesForFullGrid(grid);
var counter = listOfFullCells.length;
for (var cell = 0; cell < counter; cell++) {
result.push({"cell": listOfFullCells[cell], "possibilities": listOfPossibilities[cell]});
}
result.sort(function (first, second) {
return first.possibilities.length - second.possibilities.length;
});
return result;
}
function findNextFullCells(grid) {
var sortedFullCells = sortFullCells(grid);
if (sortedFullCells === false) {
return false;
}
var result = [];
result.push(sortedFullCells[0]);
for (var cell = 1, length = sortedFullCells.length; cell < length; cell++){
if(sortedFullCells[cell].possibilities.length === sortedFullCells[0].possibilities.length) {
result.push(sortedFullCells[cell]);
}
}
return result;
}
function removeCells(grid, cellsToBeRemoved) {
if (cellsToBeRemoved <= 0) {
return grid;
}
var nextCell = shuffle(findFullCells(grid))[0];
var row = nextCell[0];
var column = nextCell[1];
var value = grid[row][column];
grid[row][column] = "";
cellsToBeRemoved--;
if (countAllSolutions(grid) < 2) {
grid = removeCells(grid, cellsToBeRemoved);
return grid;
} else {
grid[row][column] = value;
grid = removeCells(grid, cellsToBeRemoved);
}
return grid;
}
createTable();
createButton("Solve Sudoku", function () {
console.time("Solved");
printGrid(solveSudoku(retrieveGrid()));
console.timeEnd("Solved");
});
createButton("Remove Cells", function () {
console.time("Removed");
printGrid(removeCells(retrieveGrid(),55));
console.timeEnd("Removed");
});
createButton("Count Solutions", function () {
console.time("Counting");
console.log(countAllSolutions(retrieveGrid()));
console.timeEnd("Counting");
});
createButton("Create Random Grid", function () {
printGrid(createIncRandomGrid(100));
});
createButton("Create Correct Random Grid", function () {
printGrid(createCorRandomGrid(17));
});
createButton("Check Grid", function () {
checkGrid(retrieveGrid());
});
createButton("Count Full Cells", function () {
console.log(findFullCells(retrieveGrid()).length);
});
createButton("Count Empty Cells", function () {
console.log(findEmptyCells(retrieveGrid()).length);
});
createButton("Sort Empty Cells", function () {
console.log(sortPossibilties(retrieveGrid()));
});
createButton("Sort Full Cells", function () {
console.log(sortFullCells(retrieveGrid()));
});
createButton("Reset Grid", function () {
printGrid(createEmptyGrid());
});
