sudoku-solver-IA-fatec-americana.js

"use strict";

var lines = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];

function resolver(game) {
    var t0 = performance.now();
    var solved = solveSudoku(convertToLineArray(game), 0, 0);
    var t1 = performance.now();
    console.log("Call to solveSudoku took " + (t1 - t0) + " milliseconds.");
    return solved;
}

function solveSudoku(game, row, column) {
    var cell = findUnassignedLocation(game, row, column);
    row = cell[0];
    column = cell[1];

    // if there is no empty cell, the sudoku is solved
    if (row == -1) {
        console.log("solved");
        return true;
    }

    for (var num = 1; num <= 9; num++) {

        if (isCorrectNumber(game, row, column, num)) {
            game[row][column] = num;

            if (solveSudoku(game, row, column)) {
                return convertToJson(game);
            }

            game[row][column] = 0;
        }
    }

    return false;
}

function findUnassignedLocation(game, row, column) {
    for (; row < 9; column = 0, row++) {
        for (; column < 9; column++) {
            if (game[row][column] == 0) {
                return [row, column];
            }
        }
    }
    return [-1, -1];
}

function isCorrectNumber(game, row, column, num) {
    return isRowOk(game, row, num) && isColumnOk(game, column, num) && isSquareOk(game, row, column, num);
}

function isRowOk(game, row, num) {
    for (var column = 0; column < 9; column++)
        if (game[row][column] == num) {
            return false;
        }
    return true;
}

function isColumnOk(game, column, num) {
    for (var row = 0; row < 9; row++) {
        if (game[row][column] == num) {
            return false;
        }
    }
    return true;
}

function isSquareOk(game, row, column, num) {
    row = Math.floor(row / 3) * 3;
    column = Math.floor(column / 3) * 3;

    for (var r = 0; r < 3; r++) {
        for (var c = 0; c < 3; c++) {
            if (game[row + r][column + c] == num) {
                return false;
            }
        }
    }

    return true;
}

function convertToLineArray(game) {
    var gameBoard = Array();

    for (var letter = 0; letter < 9; letter++) {
        var line = Array();
        for (var number = 1; number < 10; number++) {
            if (game[lines[letter] + number] != undefined) {
                line.push(game[lines[letter] + number]);
            } else {
                line.push(0);
            }
        }
        gameBoard.push(line);
    }
    return gameBoard;
}

function convertToJson(game) {
    var gameBoard = {};

    for (var letter = 0; letter < 9; letter++) {
        for (var number = 0; number < 9; number++) {
            var key = lines[letter].toString() + (number + 1);
            gameBoard[key] = game[letter][number];
        }
    }
    return gameBoard;
}