Coding interview Essentials

28. Sudoku

Sudoku

Introduction

The game of Sudoku[^24] has become hugely popular in the last 20 years to There are now countless websites and magazines dedicated to these mathematical-logic-based number-placement puzzles. The objective of this is to fill a nine-by-nine (9x9) grid (subdivided in \(3\times3\) subgrids) with digits so that each:

  • row,

  • column,

  • \(3\times3\) subsquare section

contains a number between \(1\) and \(9\), with the constraint that each number can appear only once in each section. The puzzle is given as a incomplete grid where only some of the cells are filled.

This chapter describes how to write a very basic and simple sudoku solver based on backtracking that can be implemented fast enough for a programming interview. Having played this puzzle before might help during the interview but it is not essential as the rules are easy enough to understand in a few minutes.

Problem statement

Write a function that takes as an input a sudoku grid and returns its solution. The input sudoku grid is given as a string of length \(81\) representing the grid in a row-major manner[^25] where empty cells are represented by the character ‘0’.


Given the input string the function returns . See Figures [fig:sudoku:sudo1unsolved] and [fig:sudoku:sudo1solved] for their 2D representation.

Clarification Questions

Is the input string guaranteed to only contains numeric characters and be the right size?

Yes the string is guaranteed to be encoding a valid sudoku

Discussion

The general problem of solving a sudoku (of size \(n\times m\)) is NP-complete[^26] and thus an efficient (polynomial-time) solution is not yet known. The simple bruteforce algorithm would have to try each available number across all empty cells and therefore would have a runtime complexity of \(O(N^{(N^2)})\), where \(N\) is size of the Sudoku puzzle. For a classic \(9 \times 9\) puzzle \(N = 9\) and the number of operations required would be at most \(2 \times 10^{77}\) operations to find a solution which would make this approach impractical.

In practice the number of operations varies hugely according to the difficulty of the puzzle itself and especially according to the number of given clues which, in turn, limit the options for each empty cell. Clues reduce the number of possible states the grid can be and in which the rules of the puzzle are not violated. The more clues the are, the higher the number of invalid states. An algorithm can take advantage of that fact to avoid those invalid states. For example, a \(17\)-clue puzzle with diagonal symmetry is one of the hardest to solve due to the large number of candidates and branches[^27].

Backtacking

Backtracking is a good approach to use to solve this problem considering that it has the following characteristics:

  • potentially large puzzle-states search space

  • many invalid states we can skip visiting

For a more detailed explanation of backtracking see [@backtracking].

In a nutshell the solution proposed in this section works by visiting the empty cells starting from the first one from the lest, filling it in with a feasible digit (i.e. a digit that does not take the grid to an invalid state) and then doing the same for every other empty cell. If at any point there is no available digit for an empty cell then a backtracking step occurs. The choice for the previous cell is then changed and the whole process repeats until either all the empty cells are filled (in this case we have a valid solution) or there are no more options for the first cell (in this case the puzzle has no solution and it is invalid). A backtracking solution would solve a puzzle by placing the digit ‘1’ in the first empty cell and checking if it is allowed to be there (i.e. that no rules are broken). If there are no violations (checking row, column, and box constraints) then the algorithm advances to the next cell and places a ‘1’ in the next empty cell. When checking for violations, if it is discovered that the is not allowed, the value is advanced to . If a cell is discovered where none of the 9 digits is allowed, then the algorithm leaves that cell blank and moves back to the previous cell. The value in that cell is then incremented by one and the whole process repeats. Clearly, this method will eventually find a solution if the puzzle is valid because all possible valid states for the grid will be tested.

Listing [list:sudoku] shows a possible implementation of the backtracking idea described above. The public interfact of the SudokuSolver class consists only of a constructor SudokuSolver::SudokuSolver(std :: string taking a a sole input a std::string, the problem input, and the std::strings SudokuSolver::solve() function that is responsible for returning the solution. The constructor is responsible for analyzing the input and storing the indices of all the empty cells (i.e. the cells the backtracking function is going to try to fill) in a vector(std :: vector < int >blankCells).

The core implementation function is the bool solve\_helper(const int i) recursive function that takes as input an integer cell representing the index of an empty cell in the input string. The base case for this function is when i >= blankCells . size () i.e. there are no more empty cells to be filled. The rest of the function is straightforward because it only consists of a loop trying all possible numbers for that cell from ‘1’ to ‘9’. The canInsert(char x, int pos) function is responsible for deciding whether a character x can be placed in a certain cell pos. The check is performed by examining whether any of the rules described above would be broken by having x at cell pos. If no rules are broken then the function solve_helper calls itself recursively on the next empty cells i.e. cell+1. If none of the values tried in the loop yield a valid solution then the function returns false (no value can be inserted at this location without violating one or more rules).

Because the input is a linear representation of a grid, which is a 2D structure, and the constraints of the puzzle are for the 2D portion of the grid itself, the code is further complicated by calculations that are necessary for the functions canInsertInRow, canInsertInCol and canInsertInSquare to be able to map the cells belonging to the same row, column or subsquare to the input 1D input string. The functions getRow, getCol, getSubsquare are used to - given a index in the 1D input string - retrieve the corrensponding row, column and subsquare index in the 2D grid. These functions are used in the canInsertInRow, canInsertInCol and canInsertInSquare functions that are responsible for verifying that the constraints on the row, column and subsquare, respectively, are not violated when we try to insert a certain value in a cell. In order to do this they need to be able to calculate the indices of all cells belonging to the same row, columns and subsquare. Specifically:

  • the canInsertInRow function checks all the cells belonging to the same row. Given a row \(r\) then all \(9\) cells belonging to it have indices in the range \([9r,9(r+1)]\)(See Figure [fig:sudoku:getRow]).

  • It becomes more complex when it comes to checking cells in the same column, in the function canInsertInRow. The column \(c\) to which a cell in the input string with index \(x\) belongs can be found by using the following formula: \(c = x \Mod{9}\). This means that the very first cells in the input belonging to column \(c\) is located at index \(c\) and all subsequent cells of the column are distanced \(9\) cells from each other. More formally, the index for the \(k^{th}\) cell of the column in the input string is: \(P(k,c) = 9k+c\).

  • The hardest check is the one for subsquares in the canInsertInSquare(char x, int s) function because, in order to check whether it is possible to insert the value \(x\) in the subsquare \(s\), it has to compare \(x\) to all the other non-empty cells of the same subsquare. This goal is accomplished in two steps:

    1. First, the index of the \(F(s)\) top left corner of the subsquare \(s\) is calculated by using the following formula: \(F(s) = (27 \lfloor \frac{s \rfloor{3}}) + (3\times (s \mod{3}))\). In order to understand the formula, we need first to note that the subsquares are organized into \(3\) rows each of size \(3\) (for a total of 9 subsquares, see Figure [fig:sudoku:]). Clearly each subsquare contains \(9\) cells, and thus, a full row of subsquares contains \(3\times9 =27\) cells. \(\frac{s}{3}\) is a value representing how many full subsquare rows come before \(s\). Clearly we can skip all the cells belonging to those subsquares, because all cells in them come before \(F(s)\). The value \((27 \lfloor \frac{s \rfloor{3}})\) is thus an index pointing to a cell at the beginning of the row where \(F(s)\) is located. All we need to do now is to advance to the correct subsquare in the row and we can do that by looking at the position of the subsquare in the row which clearly is \((s \Mod{3})\); \(s\) can either be either on the left (\((s \Mod{3})=0\)), center (\((s \Mod{3})=1\)) or on the right side of the row (\((s \Mod{3})=2\)). Given each subsequare has width of \(3\) we can jump to the correct location by using \(3\times (s \Mod{3}))\).

    2. once \(F(s)\) is known then is it easy to retrieve the indices of all the cells in the subsquare by using the ideas adopted for canInsertInRow and canInsertInCol.

Listing 1: Backtracking solution to the Sudoku problem.

#include <optional>
class SudokuSolver
{
 public:
  SudokuSolver(std::string _problem) : problem(std::move(_problem))
  {
    assert(problem.size() == 81);
  }
  auto solve()
  {
    printSudoku();
    getBlankCells();
    solve_helper(0);
    printSudoku();
    return problem;
  }

 private:
  void getBlankCells()
  {
    for (int i = 0; i < problem.size(); i++)
      if (problem[i] == '0')
        blankCells.push_back(i);
  }

  char intToChar(const char num)
  {
    assert(num >= '0' && num <= '9');
    return num;
  }

  bool canInsertInRow(const auto x, const auto row)
  {
    assert(row >= 0 && row < 9);
    auto start = std::begin(problem) + 9 * row;
    auto end   = start + 9;
    return find(start, end, intToChar(x)) == end;
  }

  bool canInsertInCol(const auto x, const auto column)
  {
    int curr = column;
    while (curr < 81)
    {
      if (problem[curr] == intToChar(x))
        return false;
      curr += 9;
    }
    return true;
  }

  bool canInsertInSquare(const auto x, const auto square)
  {
    int start_cell = (3 * 9 * (square / 3)) + (3 * (square % 3));
    for (int i = 0; i < 3; i++)
    {
      const bool found = (problem[start_cell + i * 9] == intToChar(x))
                         || (problem[start_cell + i * 9 + 1] == intToChar(x))
                         || (problem[start_cell + i * 9 + 2] == intToChar(x));
      if (found)
        return false;
    }
    return true;
  }
  bool canInsert(const auto x, const auto pos)
  {
    const auto row    = pos / 9;
    const auto col    = pos % 9;
    const auto square = (row / 3) * 3 + (col / 3);
    return canInsertInRow(x, row) && canInsertInCol(x, col)
           && canInsertInSquare(x, square);
  }

  void printSudoku()
  {
    for (int i = 0; i < 9; i++)
    {
      for (size_t j = 0; j < 9; j++)
      {
        cout << problem[i * 9 + j] << " ";
      }
      cout << endl;
    }
  }

  bool solve_helper(const int i)
  {
    if (i >= blankCells.size())
    {
      return true;
    }
    auto pos = blankCells[i];
    cout << pos << " +++++++   " << endl;
    // printSudoku();
    //  cout<<endl;
    for (char x = '1'; x <= '9'; x++)
    {
      problem[pos] = '0';
      /* if(pos == 27)
           cout<<"here";*/
      if (canInsert(x, pos))
      {
        problem[pos] = x;
        if (solve_helper(i + 1))
          return true;
      }
    }
    problem[pos] = '0';
    return false;
  }

  std::string problem;
  std::vector<int> blankCells;
};

std::string solve_sudoku_backtracking(std::string& sudoku)
{
  SudokuSolver solver(sudoku);
  solver.solve();
  return solver.solve();
}

Conclusion