Пристегнитесь, здесь мы собираемся решить судоку с несколькими петлями, поиском dfs и возвратом.
Я надеюсь, что все, кто читает этот блог, пытались решить судоку и почувствовали, как приятно, наконец, найти решение! Я решаю судоку довольно давно, и это до сих пор меня поражает.
Поэтому, пытаясь лучше понять методы решения судоку, я наткнулся на алгоритм для его программного решения. Выполнение простых шагов приводит нас к решению.
Вот как мы попробуем найти решение:
- Цикл для каждой пустой ячейки
- Попробуйте заполнить ячейку цифрой от 1 до 9
- Проверить правильность цифры (которой мы заполнили ячейку)
- Проверить, нет ли в строке и столбце ячейки этой цифры
- Проверить, что в поле 3*3 нет этой цифры
Но сначала давайте посмотрим, как будут выглядеть входные данные:
Если мы преобразуем эти данные изображения в виде массива:
Input: board = [ ["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"] ];
Здесь пустые ячейки обозначаются как “.”. Окончательный вывод должен выглядеть так:
Если мы преобразуем его в массив:
Output: [ [“5”,”3",”4",”6",”7",”8",”9",”1",”2"],[“6”,”7",”2",”1",”9",”5",”3",”4",”8"],[“1”,”9",”8",”3",”4",”2",”5",”6",”7"],[“8”,”5",”9",”7",”6",”1",”4",”2",”3"],[“4”,”2",”6",”8",”5",”3",”7",”9",”1"],[“7”,”1",”3",”9",”2",”4",”8",”5",”6"],[“9”,”6",”1",”5",”3",”7",”2",”8",”4"],[“2”,”8",”7",”4",”1",”9",”6",”3",”5"],[“3”,”4",”5",”2",”8",”6",”1",”7",”9"] ];
Решение
Давайте выясним, является ли новое число (от 1 до 9), помещенное в пустую ячейку, правильным или действительным. Эта часть проста, если новое число не сталкивается с существующими числами в этой конкретной строке/столбце, как догадка/предположение, мы можем продолжить с этим числом в этой конкретной ячейке. Затем мы можем попробовать с новым числом (1–9) в следующей пустой ячейке.
Чем дальше мы продвигаемся, тем меньше шансов, что число не столкнется, и если новое число сталкивается, наше предположение было неверным, мы возвращаемся к исходному предположению, возвращаясь к нашему пути (Обратный поиск ).
Код
- Переберите каждую строку и столбец и найдите непустые ячейки.
// loop over rows
for(let row = 0; row < n; row++){
// loop over cols
for(let col = 0; col < n; col++){
// if cell is already filled, skip it
if(board[row][col] != ".") continue;
}
}
2. Проверьте, не конфликтует ли новое значение ячейки с существующим значением. Он состоит из двух проверок: первая: она не должна конфликтовать с существующими значениями строк и столбцов. во-вторых:это не должно конфликтовать с существующими значениями блока 3*3.
function isValid(board, row, col, n, newVal){
// get box row number
let boxRow = Math.floor(row/3) * 3;
// get box col number
let boxCol = Math.floor(col/3) * 3;
// loop over board length
for(let i = 0; i < n; i++){
// stop if the newVal collides with existing row/col values
if(board[row][i] == newVal || board[i][col] == newVal) return false;
// get current row
const curRow = boxRow + Math.floor(i/3);
// get current col
const curCol = boxCol + Math.floor(i%3);
// stop if the newVal collides with 3*3 box values
if(board[curRow][curCol] == newVal) return false;
}
return true;
}
3. Если наше предположение верно, мы можем поместить это новое значение в выбранную ячейку и перейти к следующей пустой ячейке. И если предположение неверно (newVal сталкивается с существующими значениями rows/cols/box), мы можем снова пометить ячейку как пустую.
// try every number from 1-9
for(let i = 1; i <= 9; i++){
const c = i.toString();
// if that is a valid
if(isValid(board, row, col, n, c)){
board[row][col] = c;
// the number is valid, continue with next assumption
if(dfs(board, n)) return true;
}
}
// valid number couldn't be found
// set it back to "."
board[row][col] = ".";
Полный код
Мы поняли весь процесс, используя фрагменты кода. Теперь пришло время объединить фрагменты кода в один блок кода. Вот:
/** * @param {character[][]} board * @return {void} Do not return anything, modify board in-place instead. */ var solveSudoku = function(board) { const n = board.length; dfs(board, n); }; function dfs(board, n){ // loop over rows for(let row = 0; row < n; row++){ // loop over cols for(let col = 0; col < n; col++){ // if cell is already filled, skip it if(board[row][col] != ".") continue; // try every number from 1-9 for(let i = 1; i <= 9; i++){ const c = i.toString(); // if that is a valid number if(isValid(board, row, col, n, c)){ board[row][col] = c; if(dfs(board, n)) return true; } } // the number couldn't be found // set it back to "." board[row][col] = "."; // return false to signal dead end return false; } } // all cells filled, must be a solution return true; } function isValid(board, row, col, n, newVal){ // get box row number let boxRow = Math.floor(row/3) * 3; // get box col number let boxCol = Math.floor(col/3) * 3; // loop over board length for(let i = 0; i < n; i++){ // stop if the newVal collides with existing row/col values if(board[row][i] == newVal || board[i][col] == newVal) return false; // get current row const curRow = boxRow + Math.floor(i/3); // get current col const curCol = boxCol + Math.floor(i%3); // stop if the newVal collides with 3*3 box values if(board[curRow][curCol] == newVal) return false; } return true; }
Теперь мы можем вызвать метод solveSudoku(input), и он заполнит переменную input правильными данными, а если фактическое решение невозможно, он вообще не изменит переменную.
Я надеюсь, что каждый, кто читает это, узнал что-то об обратном поиске, DFS, и некоторых понятиях об алгоритме.
Если вы хотите узнать больше о программировании, бэкенд-инжиниринге, следите за мной на Medium, а также в Твиттере. Увидимся в следующей статье!
