logo标签列表

JavaScript数独求解器

javascriptsolversudoku
9

我正在尝试编写一个可以解决数独的算法。目前，我的代码可以一直运行到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;
}

1
这听起来像是“我想写一本有趣故事的书，但我没有好故事的想法……”。请访问http://stackoverflow.com/help/mcve了解如何创建最小化、完整和可验证的示例。 - Psi
我觉得你想做一些回溯算法。 - Erwin Kalvelagen
就像我说的那样。当supplyGrid中没有数字时，算法会停止。我该如何返回，重试另一个数字（最后一个不应该被选中）？ - Xaoo
如果你已经回溯并且没有找到解决方案，那么你的代码中有一个错误。 - Erwin Kalvelagen
7个回答
20

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

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;
}
3
3

我想到了这个解决方案，请看:

function sudoku(grid: number[][]): boolean {
  const rows: Set<number>[] = [];
  const cols: Set<number>[] = [];
  const miniGrids: Set<number>[] = [];

  for (let i = 0; i < 9; ++i) {
    rows.push(new Set());
    cols.push(new Set());
    miniGrids.push(new Set());
  }

  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const gridId: number = Math.trunc(i / 3) * 3 + Math.trunc(j / 3);
      const n: number = grid[i][j];
      if (rows[i].has(n) || cols[j].has(n) || miniGrids[gridId].has(n)) return false;

      rows[i].add(n);
      cols[j].add(n);
      miniGrids[gridId].add(n);
    }
  }

  return true;
}
2
我已经编写了一个解决任何9x9数独问题的解决方案，但答案只适用于9x9的正方形。算法始终是回溯算法，但它经过优化以减少迭代（即时间），忽略默认单元并使用随机统计数据来选择值（即随机）。与第一个答案相比，该解决方案的迭代次数从3.556（非常幸运的运行）到31.824（不太幸运），平均100次测试中迭代19.592次。当然，与相同的输入进行比较。以下是代码：https://github.com/Eomm/grokking/blob/master/games/sudoku/play-sudoku.js。
const gameSet = [
  new Uint8Array([0, 0, 1, 5, 0, 0, 0, 7, 0]),
  new Uint8Array([0, 0, 4, 0, 6, 0, 0, 0, 9]),
  new Uint8Array([0, 3, 0, 0, 0, 4, 0, 0, 0]),
  new Uint8Array([6, 2, 0, 0, 0, 5, 1, 0, 0]),
  new Uint8Array([0, 4, 0, 0, 0, 0, 5, 2, 0]),
  new Uint8Array([0, 0, 0, 0, 4, 8, 0, 0, 3]),
  new Uint8Array([4, 1, 0, 0, 7, 0, 0, 0, 0]),
  new Uint8Array([0, 0, 6, 8, 0, 0, 0, 0, 1]),
  new Uint8Array([8, 0, 0, 0, 0, 9, 0, 3, 0])
]

process.nextTick(() => {
  const sudoku = new Sudoku({ squareRegion: 3 })
  sudoku.play(gameSet)
  console.log(sudoku.printable())
})

function Sudoku (opts = {}) {
  // TODO improve to support different sudoku types
  this.region = opts.squareRegion || 3 // default classic
}

Sudoku.prototype.play = function (gameSet) {
  const allCells = buildCellStructure(gameSet, this.region)

  this.valueSet = Array(gameSet[0].length).fill(0).map((_, i) => (i + 1))

  // to reduce the calculation, we can just ignore the default game cells
  const cells = allCells.filter(c => c.init === 0)
  let iter = 0
  for (let i = 0; i < cells.length; i++) {
    const cell = cells[i]
    iter++
    if (!solveCell.call(this, cell)) {
      cell.history.clear() // out tries are invalid

      let backTrack = i - 1
      for (; backTrack >= 0; backTrack--) {
        if (assignValue.call(this, cells[backTrack], 0)) {
          break
        }
      }
      i = backTrack - 1
    }
  }

  this.lastGame = gameSet
  this.lastResult = allCells.map(_ => _.value)

  console.log(iter)
  return this.lastResult
}

function solveCell (cell) {
  const chooseNewValue = chooseValue.call(this, cell)
  if (chooseNewValue === 0) {
    return false
  }
  assignValue.call(this, cell, chooseNewValue)
  return true
}

function assignValue (cell, value) {
  cell.rows[cell.x] = value
  cell.columns[cell.y] = value
  cell.square[(cell.x % this.region) + ((cell.y % this.region) * this.region)] = value
  cell.value = value

  if (value > 0) {
    cell.history.add(value)
  }
  return true
}

Sudoku.prototype.printable = function (result) {
  const print = result || this.lastResult
  if (!print) {
    // nothing to print
    return
  }

  return print.flatMap((val, i) => {
    if ((i + 1) % this.region === 0) {
      if ((i + 1) % (this.region ** 2) === 0) {
        if ((i + 1) % (this.region ** 3) === 0) {
          return [val, '|', '\n', '-'.repeat(this.region ** 2), '--|\n']
        } else {
          return [val, '|', '\n']
        }
      } else {
        return [val, '|']
      }
    }
    return val
  }).join('')
}

function chooseValue (cell) {
  const values = this.valueSet
    .filter(_ => !cell.rows.includes(_))
    .filter(_ => !cell.columns.includes(_))
    .filter(_ => !cell.square.includes(_))
    .filter(_ => !cell.history.has(_))
  if (values.length === 0) {
    return 0
  }
  // stochastic hope
  return values[Math.floor(Math.random() * values.length)]
}

// this structure point always to the same arrays
function buildCellStructure (gameSet, squareLength) {
  const cells = []

  const columnMap = new Map()
  const squareMap = new Map()

  gameSet.forEach((row, y) => {
    row.forEach((cellValue, x) => {
      if (!columnMap.has(x)) {
        columnMap.set(x, [])
      }
      columnMap.get(x).push(cellValue)

      const squareId = `${Math.floor(x / squareLength)}-${Math.floor(y / squareLength)}`
      if (!squareMap.has(squareId)) {
        squareMap.set(squareId, [])
      }
      squareMap.get(squareId).push(cellValue)

      cells.push({
        x,
        y,
        value: cellValue,
        init: cellValue,
        rows: row,
        columns: columnMap.get(x),
        squareId,
        square: squareMap.get(squareId),
        history: new Set(),
        iter: 0
      })
    })
  })

  return cells
}
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', '.', '.', '.', '.'],
];

function isValidSudoku(grid) {
    let seenRow = {},
        seenCol = {},
        seenSubBox = {},
        seen = {}

    for (let row = 0; row < 9; row++) {
        for (let col = 0; col < 9; col++) {
            let value = grid[row][col];
            if (!(value === '.')) {
                let rowKey = `${row}-${value}`,
                    colKey = `${col}-${value}`,
                    boxKey = `${Math.floor(row/3)}-${value}-${Math.floor(col/3)}`

                if (seenRow[rowKey] || seenCol[colKey] || seenSubBox[boxKey]) {
                    return false;
                }               
                seenRow[rowKey] = true;
                seenCol[colKey] = true;
                seenSubBox[boxKey] = true;
            }
        }
    }

    return true;
}

console.log(isValidSudoku(_board));
这里的重点是解决问题，而不仅仅是验证板子。 - fedeghe
1

using backtrack and search. also, you can visualise your solved board little better. Check this out. 

const b = null;

//test cases

const bd1 = [
    [1, b, b, b, b, b, b, b, 7],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, 5, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, 1, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, 2, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, 6],
] 

const bd2 = [
    [1, b, 5, b, b, b, b, b, 3],
    [3, b, b, b, b, b, b, b, b],
    [b, b, b, b, 8, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, 4, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, 3, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, 9],
]

const bd3 = [
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
] 

//words toughest 2012
const bdTf = [
    [8, b, b, b, b, b, b, b, b],
    [b, b, 3, 6, b, b, b, b, b],
    [b, 7, b, b, 9, b, 2, b, b],
    [b, 5, b, b, b, 7, b, b, b],
    [b, b, b, b, 4, 5, 7, b, b],
    [b, b, b, 1, b, b, b, 3, b],
    [b, b, 1, b, b, b, b, 6, 8],
    [b, b, 8, 5, b, b, b, 1, b],
    [b, 9, b, b, b, b, 4, b, b],
] 



function solveSudoku(board) {
    if (solveSudokud(board)) {
        return board
    } else {
        const possibilities = nextBoards(board)
        const validBoards = keepOnlyValid(possibilities) //filterFunction
        return searchForSolution(validBoards) //helperFunction :backtracking
    }
}

function searchForSolution(boards) {    
    if (boards.length < 1) {        //checking the board is empty
        return false
    } else {        
        var first = boards.shift()  //tak̉es the first board off and stores in the variable
        const tryPath = solveSudoku(first)   
        if (tryPath != false) { //checking if tryPath is false or not. if it is not false, we wil return the solved board
            return tryPath
        } else {
            return searchForSolution(boards)    
        }        
    }
}
function solveSudokud(board) {
    for (var i = 0; i < 9; i++) {       
        for (var j = 0; j < 9; j++) {
            if (board[i][j] === null) {
                return false
            }
        }
    }
    return true
}
//nextBoardFunction will generate 9 possiblities for a pissible sudoku board
function nextBoards(board) { 
    var res = [];       
    const firstEmpty = findEmptySquare(board) 
    if (firstEmpty != undefined) {     //if firstEmpty = not defined , then we will start generating possiblities 
        const y = firstEmpty[0]     
        const x = firstEmpty[1]
        for (var i = 1; i < 10; i++) {
            var newBoard = [...board]
            var row = [...newBoard[y]]
            row[x] = i
            newBoard[y] = row
            res.push(newBoard)
        }
    }
    return res // if firstEmpty does =  undefined that means there are no possibilities left and return res.
}

function findEmptySquare(board) {
    // board --> [int, int] | represents the x and y coordinates of the empty sq
    for (var i = 0; i < 9; i++) {
        for (var j = 0; j < 9; j++) {
            if (board[i][j] == null) {
                return [i, j]
            }
        }
    }
}
//filter funtion
function keepOnlyValid(boards) {
    return boards.filter(b => validBoard(b))    //filtered version of the board array will be returned
}   
function validBoard(board) {
    
    // check each row
    for(let i=0; i<9; i++) {
        if(!validate(board[i])) return false
    }
    //check each col
    for(let i=0; i<9; i++) {
        var arr = []
        for(let j=0; j<9; j++) {
            arr.push(board[j][i]);
        }
        if(!validate(arr)) return false;
    }
    //check each 3*3
    let row = [[0,1,2], [3,4,5], [6,7,8]]
    let col = [[0,1,2], [3,4,5], [6,7,8]]
    for(let i of row) {
        for(let j of col) {
            let arr = [];
            for(let num1 of i) {
                for(let num2 of j){
                    arr.push(board[num1][num2]);
                }
            }
            if(!validate(arr)) return false;
        }
    }
    return true
}



function validate(arr) {
    //check duplicates
    let set1 = new Set();
    for(let i=0; i< arr.length; i++) {
        if(arr[i] === b) continue;
        if(set1.has(arr[i])) return false
        set1.add(arr[i]);
    }
    return true
}


//for better visualisation and able to check manually

function get_row(board, row) {
    
    return board[row]
    
}
function print_cell(value) {
    if (Array.isArray(value)) {
        return '.'
    } else if (value == null) {
        return '.'
    } else {
        return value
    }
}
function print_board(board) {
   
    console.log()
    for (i = 0; i < 9; i++) {
        let row = get_row(board, i)
        if (i % 3 == 0) {
            console.log("|=======|=======|=======|")
        }
        console.log("|",
            print_cell(row[0]), print_cell(row[1]), print_cell(row[2]), "|",
            print_cell(row[3]), print_cell(row[4]), print_cell(row[5]), "|",
            print_cell(row[6]), print_cell(row[7]), print_cell(row[8]), "|")
    }
    console.log("|=======|=======|=======|")
}

console.log('testcase 1')
print_board(bd1)
print_board(solveSudoku(bd1))
console.log('testcase 2')
print_board(bd2)
print_board(solveSudoku(bd2))
console.log('testcase 3')
print_board(bd3)
print_board(solveSudoku(bd3))
console.log('testcase 4')
print_board(bdTf)
print_board(solveSudoku(bdTf))

0

我使用了array.some，它在条件不满足时立即终止程序，从而提高了性能。而且不需要额外的循环来初始化3*3子矩阵，我只需在some方法中检查矩阵数组是否已存在即可。


function sudoku2(grid) {
    let arrCol = [0,0,0,0,0,0,0,0,0];
    let arrRow = [0,0,0,0,0,0,0,0,0];
    let matrix = [];
    const result = grid.some((element, index) => {
        let internalResult = element.some((item, i) => {
            // matrix
            const gridId = Math.trunc(i/3)*3 + Math.trunc(index/3);
            if(!matrix[gridId]) {
                matrix[gridId] = [];
            }
            if(matrix[gridId].indexOf(item) != -1 && item != '.') {
                return true;
            } else if(item != '.'){
                matrix[gridId].push(item);
            }
            
            // column
            if (arrCol.indexOf(grid[i][index]) === -1 && (grid[i][index] != '.')) { 
                arrCol[Number(grid[i][index])] = grid[i][index];
            }
            else if (grid[i][index] != '.'){
                return true;
            }   
            
            // row
            if (arrRow.indexOf(grid[index][i]) === -1 && (grid[index][i] != '.')) { 
                arrRow[Number(grid[index][i])] = grid[index][i];

            } else if (grid[index][i] != '.') {
                return true;
            }
            if(i === 8) {
                arrRow = [0,0,0,0,0,0,0,0,0];   
                arrCol = [0,0,0,0,0,0,0,0,0];             
            }
        });
        
        // true means duplicate found in some method
        if(internalResult === true) {
            console.log('outer');
            return internalResult;
        } else if (index === 8) {
            return false // false means no duplicate found
        }
    });
    return !result;  
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接