Challenge - 5 Problems
Sudoku Solver Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of Partial Sudoku Board After One Backtracking Step
Given the initial Sudoku board and one step of backtracking filling the first empty cell, what is the state of the board?
DSA Javascript
const 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'] ]; function isValid(board, row, col, c) { for (let i = 0; i < 9; i++) { if (board[row][i] === c) return false; if (board[i][col] === c) return false; if (board[3 * Math.floor(row / 3) + Math.floor(i / 3)][3 * Math.floor(col / 3) + i % 3] === c) return false; } return true; } // Fill first empty cell with first valid number for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { if (board[r][c] === '.') { for (let num = 1; num <= 9; num++) { const ch = num.toString(); if (isValid(board, r, c, ch)) { board[r][c] = ch; break; } } r = 9; // break outer loop break; } } } console.log(board);
Attempts:
2 left
💡 Hint
Check the first empty cell and try numbers 1 to 9 to find the first valid placement.
✗ Incorrect
The first empty cell is at position (0,2). The first valid number that can be placed there without breaking Sudoku rules is '1'. So the board updates that cell to '1'.
🧠 Conceptual
intermediate1:30remaining
Understanding Backtracking in Sudoku Solver
What is the main reason backtracking is used in solving Sudoku puzzles?
Attempts:
2 left
💡 Hint
Think about how the solver handles wrong guesses.
✗ Incorrect
Backtracking tries numbers in empty cells one by one. If a number causes a conflict later, it goes back (backtracks) and tries a different number.
🔧 Debug
advanced1:30remaining
Identify the Bug in Sudoku Validity Check
What error will this code cause when checking validity in Sudoku solver?
DSA Javascript
function isValid(board, row, col, c) {
for (let i = 0; i < 9; i++) {
if (board[row][i] === c) return false;
if (board[i][col] === c) return false;
if (board[3 * Math.floor(row / 3) + Math.floor(i / 3)][3 * Math.floor(col / 3) + i % 3] === c) return false;
}
return true;
}
// Call with row=0, col=0, c='5' on a board where board[0][0] === '5'Attempts:
2 left
💡 Hint
Check the loop and index calculations carefully.
✗ Incorrect
The function correctly checks row, column, and 3x3 subgrid for the character. It returns false if the character is found. No error occurs.
🚀 Application
advanced1:30remaining
Number of Recursive Calls in Sudoku Backtracking
If a Sudoku board has 3 empty cells and each empty cell can be filled with 2 possible numbers, what is the maximum number of recursive calls the backtracking solver might make?
Attempts:
2 left
💡 Hint
Think about the tree of choices for each empty cell.
✗ Incorrect
Each empty cell has 2 choices, so total combinations are 2 * 2 * 2 = 8. The solver may try all these in worst case.
❓ Predict Output
expert3:00remaining
Final Solved Sudoku Board Output
What is the final solved Sudoku board after running the complete backtracking solver on this board?
DSA Javascript
const 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'] ]; function isValid(board, row, col, c) { for (let i = 0; i < 9; i++) { if (board[row][i] === c) return false; if (board[i][col] === c) return false; if (board[3 * Math.floor(row / 3) + Math.floor(i / 3)][3 * Math.floor(col / 3) + i % 3] === c) return false; } return true; } function solve(board) { for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { if (board[r][c] === '.') { for (let num = 1; num <= 9; num++) { const ch = num.toString(); if (isValid(board, r, c, ch)) { board[r][c] = ch; if (solve(board)) return true; board[r][c] = '.'; } } return false; } } } return true; } solve(board); console.log(board);
Attempts:
2 left
💡 Hint
Check carefully the last row and column for duplicates.
✗ Incorrect
Option D is the correct solved Sudoku board with no duplicates in rows, columns, or 3x3 boxes. Other options have duplicates or errors.