Is this Sudoku board valid so far?
You're given a 9 by 9 Sudoku board as nine strings of nine characters, where a digit from 1 to 9 is a filled cell and a dot is an empty one. I'd like you to say whether the filled cells break any rule so far, which means no digit may appear twice in the same row, the same column or the same 3 by 3 box.
You don't have to check whether the board can be solved, only whether what's on it already is consistent.
Examples
| Input | Output | Why |
|---|---|---|
the first test board, whose top row is "53..7...." | true | None of the filled cells repeats a digit in its row, its column or its box. |
the same board with its first row changed to "83..7...." | false | There's now an 8 at the top left, and its box already has an 8 two rows down while its column has another one in row 3. |
an empty board | true | With nothing filled in there's nothing that can clash. |
Constraints
- the board has exactly 9 rows of 9 characters
- each character is a digit from 1 to 9 or a dot
Hints
Hint 1
Each rule says the same thing about a different group of nine cells, which is that no digit is allowed to turn up in it twice, and there are 27 of those groups in all.
Hint 2
For one group you'd keep a set of the digits you've already met and say no as soon as a digit is already in it, so try doing that for all 27 groups in a single pass over the board.
Hint 3
The rows and columns are easy to index, and for the box you can use the row divided by 3 and the column divided by 3, which gives you a number from 0 to 8 when you combine them as 3 times the first plus the second.
Where people lose marks
- I've seen a lot of people get the box number wrong by writing r / 3 + c / 3, and then the box in the top middle and the box on the left in the middle row both come out as 1. You want 3 times the box's row plus the box's column so that all nine boxes get a number of their own.
- If you let the dot go into the sets as if it were a digit then any row with two empty cells in it looks like it breaks the rules, so skip the empty cells before you look anything up.
- Don't start trying to solve the puzzle, because the question never asks you to. A board can pass this check and still have no solution at all, and it's worth being ready to say that if the interviewer brings it up.
Dry run on ["83..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5row 08031.2.374.5.6.7.8sets27
We keep a set for each row and each column and each box, which makes 27 of them, and we go through the filled cells from the top row down.
-
Step 2 / 5row 080c31.2.374.5.6.7.8r0c0box0filled1
The 8 in the top left corner is the first digit we meet, so it goes straight into the sets for row 0 and column 0 and box 0.
-
Step 3 / 5row 08031c.2.374.5.6.7.8r0c1box0filled2
Nobody in row 0 or column 1 or box 0 has a 3 yet, so we write it into all three of those sets and carry on along the row.
-
Step 4 / 5row 08031.2.374c.5.6.7.8r0c4box1filled3
Nobody in row 0 or column 4 or box 1 has a 7 yet, so we write it into all three of those sets and carry on along the row.
-
Step 5 / 5row 2.09182c.3.4.5.667.8r2c2box0answerfalse
Now we reach the 8 in row 2 and column 2, which lives in box 0, and box 0 has already had a 8 in it, so that's a rule broken and we can stop with false.
How to think about it
You'll find this one called Valid Sudoku and I like it as a check on whether you can spot the same little pattern three times over. Each rule on the board says that some group of nine cells mustn't have a digit in it twice, and if you only had one group to look after you'd just keep a set of the digits you'd met and stop as soon as one came round again.
There are nine rows and nine columns and nine boxes, so I'd keep 27 of those sets and go over the 81 cells just
once. When you land on a filled cell at row r and column c you work out which box it's in
with 3 · ⌊r / 3⌋ + ⌊c / 3⌋ and look its digit up in the three sets it belongs to. If any of them has
it already you can say no there and then, and if none of them does you put it in all three and move on to the
next cell.
Because there are only nine digits you can make each set nine booleans or the low bits of a single integer, and that's what most people end up writing once the idea is working. The board never changes size so the work is constant, though on an n by n board with boxes of side √n you'd say the same pass takes O(n²) time.
Complexity. Time O(81), O(n²) on an n by n board · Space O(81) for the 27 sets of 9
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def is_valid_sudoku(board):
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for r in range(9):
for c in range(9):
d = board[r][c]
if d == '.':
continue
b = 3 * (r // 3) + c // 3 # which of the nine boxes
if d in rows[r] or d in cols[c] or d in boxes[b]:
return False
rows[r].add(d)
cols[c].add(d)
boxes[b].add(d)
return True#include <string>
#include <vector>
using namespace std;
bool solve(const vector<string>& board) {
int rows[9] = {0}, cols[9] = {0}, boxes[9] = {0}; // bit d set when digit d has been seen
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++) {
if (board[r][c] == '.') continue;
int bit = 1 << (board[r][c] - '0');
int b = 3 * (r / 3) + c / 3; // which of the nine boxes
if ((rows[r] | cols[c] | boxes[b]) & bit) return false;
rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit;
}
return true;
}class Solution {
public boolean isValidSudoku(String[] board) {
int[] rows = new int[9], cols = new int[9], boxes = new int[9]; // bit d set when digit d has been seen
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++) {
char ch = board[r].charAt(c);
if (ch == '.') continue;
int bit = 1 << (ch - '0');
int b = 3 * (r / 3) + c / 3; // which of the nine boxes
if (((rows[r] | cols[c] | boxes[b]) & bit) != 0) return false;
rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit;
}
return true;
}
}function isValidSudoku(board) {
const rows = Array.from({ length: 9 }, () => new Set());
const cols = Array.from({ length: 9 }, () => new Set());
const boxes = Array.from({ length: 9 }, () => new Set());
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
const d = board[r][c];
if (d === '.') continue;
const b = 3 * Math.floor(r / 3) + Math.floor(c / 3); // which of the nine boxes
if (rows[r].has(d) || cols[c].has(d) || boxes[b].has(d)) return false;
rows[r].add(d); cols[c].add(d); boxes[b].add(d);
}
}
return true;
}fn solve(board: &[&str]) -> bool {
let (mut rows, mut cols, mut boxes) = ([0u16; 9], [0u16; 9], [0u16; 9]); // bit d set when digit d has been seen
for (r, line) in board.iter().enumerate() {
for (c, ch) in line.bytes().enumerate() {
if ch == b'.' {
continue;
}
let bit = 1u16 << (ch - b'0');
let b = 3 * (r / 3) + c / 3; // which of the nine boxes
if (rows[r] | cols[c] | boxes[b]) & bit != 0 {
return false;
}
rows[r] |= bit;
cols[c] |= bit;
boxes[b] |= bit;
}
}
true
}import Data.List (nub)
-- Every row, column and box, as the list of its filled digits, must have no repeats.
solve :: [String] -> Bool
solve board = all noRepeat (rows ++ cols ++ boxes)
where
cell r c = board !! r !! c
rows = [[cell r c | c <- [0 .. 8]] | r <- [0 .. 8]]
cols = [[cell r c | r <- [0 .. 8]] | c <- [0 .. 8]]
boxes = [[cell r c | r <- [3 * br .. 3 * br + 2], c <- [3 * bc .. 3 * bc + 2]] | br <- [0 .. 2], bc <- [0 .. 2]]
noRepeat xs = let ds = filter (/= '.') xs in length ds == length (nub ds)
Variants to try
- Solve the board. (Backtracking over the empty cells, with the same 27 sets telling you which digits are still allowed in each cell.)
- Do the whole check with three arrays of nine integers used as bit masks. (Bit d of rows[r] says whether digit d is already in row r, and the same for columns and boxes.)
Next problems
Pair with a given sum in an unsorted array
Every pair is n² work. Remembering what you have already passed makes it n, and the order of two lines decides whether it is right.
Open the problem → Easy10 minA repeated value within k positions
Two equal values at most k apart. Keep the last index of every value and the check costs one lookup per element.
Open the problem → Medium15 minLongest run of consecutive integers
Sorting gives the answer in O(n log n). A set gives it in O(n), and the reason it is not O(n²) is the interesting part.
Open the problem →Write a solution and run it against the real test table.
Keep going
Pair with a given sum in an unsorted array
Every pair is n² work. Remembering what you have already passed makes it n, and the order of two lines decides whether it is right.
Open the problem → Easy10 minA repeated value within k positions
Two equal values at most k apart. Keep the last index of every value and the check costs one lookup per element.
Open the problem → Medium15 minLongest run of consecutive integers
Sorting gives the answer in O(n log n). A set gives it in O(n), and the reason it is not O(n²) is the interesting part.
Open the problem → Arrays and hashingThe pattern behind it
Trade memory for time: a hash map answers "have I seen this?" in O(1), and most array problems reduce to asking it the right question.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.