Why is random order slow in my Sudoku backtracking solving algorithm compared to "in order&quot-CodePudding

When running my sudoku backtracking algorithm using random ordering for finding new available locations, it takes way longer than when finding the available locations, left to right, top to bottom. Why? How should I change the code to have quick random ordering?

//Taking forever
let posOrder = [[4, 4], [4, 0], [7, 0], [4, 8], [2, 3], [0, 8], [6, 0], [0, 6], [0, 5], [5, 4], [8, 2], [7, 7], [5, 1], [6, 3], [3, 2], [3, 3], [1, 2], [6, 2], [0, 7], [4, 2], [1, 4], [0, 1], [1, 1], [7, 1], [5, 2], [0, 2], [3, 7], [1, 6], [0, 4], [8, 1], [5, 6], [2, 1], [8, 3], [6, 4], [8, 6], [2, 7], [6, 6], [8, 7], [1, 8], [7, 4], [4, 7], [4, 5], [8, 4], [6, 1], [2, 2], [1, 5], [7, 6], [3, 6], [5, 0], [4, 1], [2, 8], [6, 8], [3, 1], [5, 3], [3, 4], [7, 2], [2, 5], [8, 5], [5, 5], [7, 8], [8, 8], [6, 5], [6, 7], [4, 6], [2, 6], [3, 5], [2, 0], [5, 7], [1, 0], [0, 3], [2, 4], [7, 5], [8, 0], [7, 3], [0, 0], [3, 8], [5, 8], [3, 0], [1, 7], [1, 3], [4, 3]]

//Goes quickly
//let posOrder = [[0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [0, 8], [1, 0], [1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [2, 0], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [3, 0], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [3, 7], [3, 8], [4, 0], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [4, 7], [4, 8], [5, 0], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [5, 8], [6, 0], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6], [6, 7], [6, 8], [7, 0], [7, 1], [7, 2], [7, 3], [7, 4], [7, 5], [7, 6], [7, 7], [7, 8], [8, 0], [8, 1], [8, 2], [8, 3], [8, 4], [8, 5], [8, 6], [8, 7], [8, 8]]

const backtrack = (board) => {
    const pos = posOrder.find(p => board[p[0]][p[1]] === 0)
    if(!pos)
        return true
    const [row, col] = pos
    return (shuffleArray([1, 2, 3, 4, 5, 6, 7, 8, 9]).some(number => {
        if (!numberExists(board, number, row, col)) {
            board[row][col] = number
            if (backtrack(board))
                return true
            else {
                board[row][col] = 0
                return false
            }
        }
    }))
}

const shuffleArray = (array) => {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i   1)); // This ; is necessary... apparently
        [array[i], array[j]] = [array[j], array[i]]
    }
    return array
}

const numberInRow = (board, number, row) => board[row].some(col => col === number)
const numberInCol = (board, number, col) => board.some(row => row[col] === number)
const numberInRegion = (board, number, row, col) => {
    const r = 3*Math.floor(row/3)
    const c = 3*Math.floor(col/3)
    return [board[r], board[r 1], board[r 2]].some(arr=> [arr[c], arr[c 1], arr[c 2]].some(nbr => nbr === number))
}
const numberExists = (board, number, row, col) => (
    numberInRow(board, number, row) ||
    numberInCol(board, number, col) ||
    numberInRegion(board, number, row, col)
)

const sudokuBoard = [
  [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]
]
backtrack(sudokuBoard)

Note that I'd prefer to randomize the order every time, just kept one randomized order to rerun the example.

CodePudding user response：

In the non-random order, after 9 placements all combinations for the first row that would have duplicates, have already been eliminated. After 27 placements, there are already 3 lines and three 3x3 boxes completed. That means already some alternatives had to be considered at an early stage to make it work. For instance, there was only one possible digit to place at move 9.

The random order will in a first phase allow the placement of digits with much more liberty, as a lot of initial coordinates are not directly related, and so fewer choices have to be redone at an early stage. This means more wrong moves are left on the board for a longer time and will therefore take much more time before they are eventually undone and replaced by a different choice.

To get the better performance it is of utmost importance that early choices are good and don't have to be redone. So that means that the sudoku constraints have to be eagerly sought.

I would therefore say that the best order is to fill lines, columns and boxes as soon as possible. For instance, this seems to be a promising order:

The first line
The top-left box (so completing it with 6 more positions)
The second line (completing the 6 remaining positions)
The top-center box (completing 3 remaining positions)
The third line & top-right box (completing 3 remaining positions)
The first column (completing 6 remaining positions)
The second column (completing 6 remaining positions)
... etc