Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Book a call

Coding · Arrays and hashing

Is this Sudoku board valid so far?

Medium · Target 15 minutes · Arrays and hashing· Type asked at

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

InputOutputWhy
the first test board, whose top row is "53..7...."trueNone 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...."falseThere'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 boardtrueWith 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.
Console⌘/Ctrl + Enter runs

Write a solution and run it against the real test table.


Keep going

Preparing for a real process? Quant interview preparation, or book a free 20-minute call.