Google interview question

Design and write a sudoku solver.

Interview Answer

Anonymous

Apr 21, 2011

Take a cell which is not filled. Get a number from 1 to 9 which is not in the row or the column of that cell, and is not in the 3x3 square containing that cell either. If there is no such number, return. If there is such number, put it in that cell, and let this algorithm call itself for another empty cell. If there is more than one such number, repeat the algorithm for that number. In short, use backtracking. Iterate through all possible partial solutions gradually filling up each solution or returning to a less complete solution if a dead end is encountered.