JS中的数独求解器

Question

我正在尝试编写一个可以解决数独的算法。现在，我的代码一直有效，直到supplyGrid超出数字。当它发生时它应该回去尝试另一个号码，对吧？说实话，我不知道如何实现。

var grid = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0]
],
    supplyGrid = [1, 2, 3, 4, 5, 6, 7, 8, 9],
    row = 0,
    col = 0,
    value = 0,
    index = 0;


var solveSudoku = function (grid, row, col) {
    if (col > 8) {
        row++;
        col = 0;
        if (row > 8 && col > 8) {
            console.log(grid);
            return;
        }
    }
    if (grid[row][col] === 0) { //
        index = Math.floor(Math.random() * supplyGrid.length);
        value = supplyGrid[index];
        if (isValid(row, col, value)) {
            grid[row][col] = value;
            col++;
            supplyGrid = [1, 2, 3, 4, 5, 6, 7, 8, 9];
            solveSudoku(grid, row, col);
        } else {
            supplyGrid.splice(index, 1);
            console.log(supplyGrid);
            if (supplyGrid.length < 1) { 
                //backtrack();
                console.log('Out of numbers');
                return;
            }
            solveSudoku(grid, row, col);
        }
    } else { //row = 3, col = 5
        solveSudoku(grid, row, ++col);
    }
    return this;
}

function isValid(row, col, value) {
    if ((validateColumn(row, col, value)) || (validateRow(row, col, value)) || (validateBox(row, col, value))) {
        return false;
    } else {
        return true;
    }
}

function validateBox(row, col, value) {
    row = Math.floor(row / 3) * 3;
    col = Math.floor(col / 3) * 3;
    var isFound = false;
    for (var i = 0; i < 3; i++) {
        for (var j = 0; j < 3; j++) {
            if (grid[row + i][col + j] == value) isFound = true;
        }
    }
    return isFound;
}

function validateRow(row, col, value) { 
    var isFound = false;
    for (var i = 0; i < 9; i++) {
        if (grid[row][i] === value) isFound = true;
    }
    return isFound;
}

function validateColumn(row, col, value) { 
    var isFound = false;
    for (var i = 0; i < 9; i++) {
        if (grid[i][col] === value) isFound = true;
    }
    return isFound;
}

Answer 1

这是一个开源存储库，它提供了javascript解决方案：

https://github.com/pocketjoso/sudokuJS

以下是详细说明其解决方案的代码：

https://github.com/pocketjoso/sudokuJS/blob/master/sudokuJS.js

Answer 2

我用回溯算法解决了这个问题：

const _board = [
    ['.', '9', '.', '.', '4', '2', '1', '3', '6'],
    ['.', '.', '.', '9', '6', '.', '4', '8', '5'],
    ['.', '.', '.', '5', '8', '1', '.', '.', '.'],
    ['.', '.', '4', '.', '.', '.', '.', '.', '.'],
    ['5', '1', '7', '2', '.', '.', '9', '.', '.'],
    ['6', '.', '2', '.', '.', '.', '3', '7', '.'],
    ['1', '.', '.', '8', '.', '4', '.', '2', '.'],
    ['7', '.', '6', '.', '.', '.', '8', '1', '.'],
    ['3', '.', '.', '.', '9', '.', '.', '.', '.'],
];
sodokoSolver(_board);
console.log(_board);

function isValid(board, row, col, k) {
    for (let i = 0; i < 9; i++) {
        const m = 3 * Math.floor(row / 3) + Math.floor(i / 3);
        const n = 3 * Math.floor(col / 3) + i % 3;
        if (board[row][i] == k || board[i][col] == k || board[m][n] == k) {
          return false;
        }
    }
    return true;
}


function sodokoSolver(data) {
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      if (data[i][j] == '.') {
        for (let k = 1; k <= 9; k++) {
          if (isValid(data, i, j, k)) {
            data[i][j] = `${k}`;
          if (sodokoSolver(data)) {
           return true;
          } else {
           data[i][j] = '.';
          }
         }
       }
       return false;
     }
   }
 }
 return true;
}

Answer 3

这就是我现在所拥有的。

var grid = [
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [8, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0]
    ],
        invalidGrid = [
          [[], [], [], [], [], [], [], [], []],
          [[], [], [], [], [], [], [], [], []],
          [[], [], [], [], [], [], [], [], []],
          [[], [], [], [], [], [], [], [], []],
          [[], [], [], [], [], [], [], [], []],
          [[], [], [], [], [], [], [], [], []],
          [[], [], [], [], [], [], [], [], []],
          [[], [], [], [], [], [], [], [], []],
          [[], [], [], [], [], [], [], [], []]
        ],
        supplyGrid = [1, 2, 3, 4, 5, 6, 7, 8, 9],
        row = 0,
        col = 0,
        value = 0,
        index = 0,
        z = 0;


    var solveSudoku = function (grid, row, col) {
        if (row > 8 && col > 8) return;
        if (col > 8) {
            row++;
            col = 0;
        }
        if (grid[row][col] === 0) {
            index = Math.floor(Math.random() * supplyGrid.length);
            value = supplyGrid[index];
            if (isValid(row, col, value)) {
                grid[row][col] = value;
                var iArr = invalidGrid[row][col];
                iArr.push(value)
                col++;
                supplyGrid = [1, 2, 3, 4, 5, 6, 7, 8, 9];
                solveSudoku(grid, row, col);
            } else {
                supplyGrid.splice(index, 1);
                if (supplyGrid.length < 1) { 
                    col--;
                    if (col < 0) col = 8;
                    supplyGrid = [1, 2, 3, 4, 5, 6, 7, 8, 9];
                    for (var i = 0; i < invalidGrid[row][col].length; i++) {
                        supplyGrid.splice(supplyGrid.indexOf(invalidGrid[row][col][i]), 1)
                    }
                    grid[row][col] = 0;
                    solveSudoku(grid, row, col);
                }
                solveSudoku(grid, row, col);
            }
        } else { //row = 3, col = 5
            col++;
            solveSudoku(grid, row, col);
        }
        return this;
    }

    function displaySudoku() {
        var string = '';
        for (var i = 0; i < 9; i++) {
            string += '<tr>';
            for (var j = 0; j < 9; j++) {
                string += '<td>';
                string += `${grid[i][j]}`;
                string += '</td>';
            }
            string += '</tr>';
        }
        document.write('<table>' + string + '</table>')
    }

    function isValid(row, col, value) {
        if ((validateColumn(row, col, value)) || (validateRow(row, col, value)) || (validateBox(row, col, value))) {
            return false;
        } else {
            return true;
        }
    }

    function validateBox(row, col, value) {
        row = Math.floor(row / 3) * 3;
        col = Math.floor(col / 3) * 3;
        var isFound = false;
        for (var i = 0; i < 3; i++) {
            for (var j = 0; j < 3; j++) {
                if (grid[row + i][col + j] == value) isFound = true;
            }
        }
        return isFound;
    }

    function validateRow(row, col, value) {
        var isFound = false;
        for (var i = 0; i < 9; i++) {
            if (grid[row][i] === value) isFound = true;
        }
        return isFound;
    }

    function validateColumn(row, col, value) {
        var isFound = false;
        for (var i = 0; i < 9; i++) {
            if (grid[i][col] === value) isFound = true;
        }
        return isFound;
    }

有时我会生成有效的数独。有时..我认为这与删除以前的号码有关。但我不确定..

Answer 4

我希望有人会回答..哦......我的代码工作得很好。有时我会得到'无法读取未定义'的属性'长度'。还在努力..

我有另一个问题。我有2个网格。一个是原始网格，用户放置数字（其余部分用0填充），第二个网格用于完成所有操作。

这是一个问题。它可以解决游戏，但它会改变用户填充的数字。 1到3个数字被更改。剩下的很好。我不知道为什么会这样。

function createCopy() { //create copy of original grid
    var copyGrid = [9];
    for (var i = 0; i < 9; i++) {
        copyGrid[i] = []
        for (j = 0; j < 9; j++) {
            if (originalGrid[i][j] === 0) {
                copyGrid[i][j] = undefined; //put undefined instead of 0
            } else {
                copyGrid[i][j] = originalGrid[i][j];
            }
        }
    }
    return copyGrid;
}

var solveSudoku = function (grid, row, col) { //solver
    if (row > 7 && col > 8) return; //end function when it reaches the end
    if (col > 8) {
        row++;
        col = 0;
    }
    if (grid[row][col] === undefined) { //if there's no number
        index = Math.floor(Math.random() * supplyGrid.length);
        value = supplyGrid[index];
        if (isValid(row, col, value)) { //validate row, col and box
            grid[row][col] = value; //assigns the value
            if (backward) { //checking if the algorithm went back to change the previous value
                z = 1;
                backward = false;
            };
            var iArr = invalidGrid[row][col];
            iArr.push(value)
            col++; //if value is fine, increase column by 1
            supplyGrid = [1, 2, 3, 4, 5, 6, 7, 8, 9]; //reset supply gird 
            solveSudoku(grid, row, col); 
        } else { //if the number is invalid (cannot be placed in a row, column or box)
            supplyGrid.splice(index, 1); //delete the number from supply grid. I dont want to use the same value again in the same field.
            //console.log(supplyGrid);
            if (supplyGrid.length < 1) { //if there's no number left (all numbers are invalid for this field)
                changePreviousValue(grid, row, col); //go back to the previous field
            }
            solveSudoku(grid, row, col);
        }
    } else { //if number exist in this field
        col++; //increase the col value
        solveSudoku(grid, row, col);
    }
    return this;
}

function changePreviousValue(grid, row, col) {
//    var lastRowIndex = row;
//    var lastColIndex = col;
    col--; //go back one field
    if (col < 0) {
        col = 8;
        row--; 
    }
    if (originalGrid[row][col] === grid[row][col]) { //here im checking the value in this field. If it's in originalGrid that means I dont want to do anything with it. I dont want to change that number.
        changePreviousValue(grid, row, col); // callin function again with decreased col value (so we went back by 2 field)
        z++;
    }
    backward = true;
    if (z > 1) { //whether the algorithm went back by at least 2 fields
        if (col > 7) {
            row++; 
            col = -1;
        }
        var iArr = invalidGrid[row][col + 1];
        iArr.splice(0, invalidGrid[row][col + 1].length); //delete used values in the next field. 
    }
    z++;

    supplyGrid = [1, 2, 3, 4, 5, 6, 7, 8, 9]; //reset supply grid
    //col = -1;

    for (var i = 0; i < invalidGrid[row][col].length; i++) { 
        supplyGrid.splice(supplyGrid.indexOf(invalidGrid[row][col][i]), 1) //here im getting UNDEFINED sometimes. Its resposible for deleting used numbers in ACTUAL field. f.e I used 6 before, in the next field it couldn't fit any number so it went back to the same field. I dont want use 6 again cuz it wasnt working. 
    }
    grid[row][col] = undefined; //set field value to undefined, so we can assign new number.
    solveSudoku(grid, row, col);
}

相当凌乱，我知道：|