AlphaSudokuGo:
Ultimate Sudoku AI with Image Processing

AlphaSudokuGo is a C++ program designed to solve Sudoku puzzles using a Constraint Satisfaction Problem (CSP) approach. It features a graphical user interface (GUI) built with Qt5, which enables users to input their own puzzles and observe the solver in real-time. The primary goals of this project are to showcase the capabilities of Artificial Intelligence (AI) in tackling complex puzzles and to create cool visualizations of the search process.

BIG NEWS: The project now includes image processing capabilities, allowing users to input their own puzzles by uploading an image of the Sudoku puzzle - or even take a screenshot of a puzzle on their screen! The program is currently capable of recognizing most of the Sudoku puzzles, and can solve them in real-time.

In this video, not only is AlphaSudokuGo training on a Haaretz "hard" puzzle and tackling the hardest sudoku puzzle ever conceived, but you can also enjoy an original piece of music I composed and produced.

UPDATE: The project now deployed on the web, and you can try it out yourself!

Scroll down for more animations or jump to Interacting with the GUI

• Background
• Sudoku
  • Technical Details
  • Visualization
  • Area of Improvement
• Getting Started
  • Prerequisites
  • Compiling and Running the Project
  • Interacting with the GUI
• Contributing
• License

Background

CSP is a paradigm for representing and solving problems in a declarative manner. The type of problem that CSP is designed to solve is known as a Constraint Satisfaction Problem, which is a problem that involves finding a solution to a set of variables subject to constraints. Well known examples of CSPs include the N-Queens Problem, Map Coloring, and Sudoku. Even psychometric tests utilize CSPs, in questions such as:

Let A and B and C be digits from 1 to 9.

If A is greater than B, What is the value of C in the following equation:

AAA / BB = C

or:

Dana doesn't want to live next to a person who has a dog.

Dor has a dog.

Eva doesn't want to live next to a person who has a cat.

Fay has a cat.

Order the people from left to right in a way that satisfies all the conditions.

or:

If A is the father of B, B is the father of C, and C is the father of D,

who is the father of D?

Formally, CSP is a mathematical problem defined by the tuple (X, D, C). It consists of a set of variables (X), their respective domains (D), and a set of constraints (C). The objective is to assign a value from the domain to each variable in a way that all constraints are met. CSPs are a unique category of problems that can be effectively solved using search algorithms. They find extensive applications in various fields of artificial intelligence (AI), including but not limited to scheduling, planning, and decision-making.

To illustrate, consider the Australian map-coloring problem, a simpler instance of a CSP (see Map Coloring). The task here is to color each region of Australia in such a way that no two neighboring regions share the same color. This problem can be modeled as a CSP with four variables, each representing a region, and three constraints, each corresponding to a pair of neighboring regions. The aim is to discover a color assignment for the regions that fulfills all the constraints.

Australian map-coloring problem. Initial state (left) and a goal state (right)

As demonstrated in the examples.ipynb file, the CSP in this context is composed of the following elements:

• Variables: These are a collection of variables, each representing a region of Australia.
• X = {WA, NT, Q, NSW, V, SA, T}
• Domains: These are a collection of domains, each containing the potential colors that a region can be assigned.
• D = {red, green, blue}
• Constraints: These are a collection of constraints, each defining the permissible color combinations for a pair of adjacent regions.
• C = {(WA, NT), (WA, SA), (NT, SA), (NT, Q), (SA, Q), (SA, NSW), (SA, V), (NSW, Q), (NSW, V)}

It's important to note that a unary constraint is also applied to each variable, enforcing that each region must be assigned a color.

The fundamental concept of a CSP is to seek a solution that satisfies all constraints. The search space for a CSP is determined by the possible value assignments to the variables. The search algorithms employed to solve CSPs are designed to efficiently navigate this search space. There are many search algorithms that can be used to solve CSPs, including backtracking, local search, and constraint propagation. In this project, the backtracking algorithm is utilized to solve the Sudoku puzzle.

Backtracking algorithm is a general-purpose algorithm for finding all (or some) solutions to certain computational problems, notably CSPs. This algorithm incrementally constructs solution candidates and discards a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be extended to a valid solution. If the algorithm identifies a variable with no remaining possible values in its domain at any point, it backtracks to the most recent variable that has a changeable value. This process repeats until a solution is discovered or it is determined that no solution is possible. The general structure of the backtracking algorithm is based on versions of the Depth-First Search (DFS) algorithm, which explores as far as possible along each branch before backtracking.

Backtracking with AC-3 Algorithm

There are several strategies to enhance the backtracking algorithm, one of which is the AC-3 algorithm. This simple yet widely used algorithm enforces arc consistency in a CSP. The fundamental concept of the AC-3 algorithm is to iteratively eliminate values from the domains of the variables in a CSP until it becomes arc consistent. This is achieved by examining each constraint in the CSP and discarding values from the domains of the variables that fail to satisfy the constraint. The AC-3 algorithm is utilized to preprocess the CSP before applying the backtracking algorithm, thereby reducing the search space and enhancing the efficiency of the backtracking algorithm.

For more information on CSP you can read on the Wikipedia page.

Sudoku

The Sudoku puzzle serves as a classic instance of a CSP, because it involves finding a solution to a set of variables (the cells of the grid) subject to constraints.

It comprises a 9x9 grid of cells, each capable of holding a value from 1 to 9. The objective is to populate the grid so that each row, column, and 3x3 subgrid contains the numbers 1 to 9 with no repetitions. This can be modeled as a CSP with 81 variables (one for each cell), 81 domains (each containing the numbers 1 to 9), and 27 constraints (9 for the rows, 9 for the columns, and 9 for the subgrids).

My first encounter with the Sudoku puzzle was through the LeetCode problem Sudoku Solver, which is classified as a 'Hard' problem (see Sudoku Solver). The challenge is to develop a program that solves a Sudoku puzzle by filling the empty cells. A Sudoku solution must adhere to all the rules previously mentioned.

To represent the Sudoku puzzle as a CSP, I utilized the following components:

• Variables: A collection of variables, each representing a cell in the Sudoku grid X = {x11, x12, ..., x99}.
• Domains: A collection of domains, each containing the numbers 1 to 9 D = {1, 2, ..., 9}.
• Constraints: A collection of constraints, each defining the permissible combinations of numbers for a pair of cells C = {rows, columns, subgrids}.

Technical Details

To abstract the Sudoku puzzle grid, I created a hash table to store the available domains for each cell.

class pair_hash {
  template <class T1, class T2>
  std::size_t operator()(const std::pair<T1, T2> &pair) const {
    auto hash1 = std::hash<T1>{}(pair.first);
    auto hash2 = std::hash<T2>{}(pair.second);
    return hash1 ^ hash2;
  }
};

The pair_hash is then used inside an unordered_map to hold the available domains in the member variable domains of the class SudokuCSP.

class SudokuCSP {
public:
  void solve();  // Solve the Sudoku puzzle
  // ...
private:
  std::vector<std::vector<char>> board;
  std::unordered_map<std::pair<int, int>, std::unordered_set<int>, pair_hash>
      domains;
  bool isValidSudoku(std::vector<std::vector<char>> &board);
  bool is_consistent(std::pair<int, int> var, int value);
  bool backtrack();
};

The backtrack method carries out the backtracking process. This recursive function navigates the search space of the Sudoku puzzle by assigning values to the variables and verifying the satisfaction of constraints. If the algorithm encounters a variable with no remaining possible values in its domain at any point, it reverts to the most recent variable with a modifiable value. This procedure persists until a solution is identified or it is established that no solution is feasible.

bool SudokuCSP::backtrack() {
  std::pair<int, int> var = {-1, -1};
  for (int row = 0; row < 9; ++row) {
    for (int col = 0; col < 9; ++col) {
      if (board[row][col] == '.') {
        var = {row, col};
        goto found_unassigned;
      }
    }
  }
found_unassigned:
  if (var.first == -1)
    return true; // Puzzle solved

  for (int val : domains[var]) {
    if (is_consistent(var, val)) {
      board[var.first][var.second] = val + '0';
      if (backtrack())
        return true;
      board[var.first][var.second] = '.';
    }
  }
  return false;
}

Visualization

The program includes a graphical user interface (GUI) constructed with Qt5 and sfml, which allows users to input their own puzzles and watch the solver in real-time. The GUI is designed to be user-friendly and interactive, enabling users to alter the puzzle and observe the solver in action. The primary aim of the GUI is to offer an engaging and informative experience for users. The GUI employs advanced features of Qt5 and C++ to create a visually attractive and interactive environment for users. Here are some of the main features of the GUI.

class Sudoku : public sf::Drawable {
void Sudoku::draw(sf::RenderTarget &target, sf::RenderStates states) const {
  auto glowingColor = GlowingColor(Utility::analogousCyan).getShade();
  auto glowingBrighterColor =
      GlowingColor(Utility::analogousCyan).getBrighterShade();
  Utility::drawBackround(target, backgroundColor);
  Utility::drawLines(target, glowingColor, cellSize);
  Utility::drawNumbers(target, numbers, font, numberColor, cellSize);
  Utility::drawClosingLines(target, glowingBrighterColor, cellSize);
  saveScreenshot(target);
}

sf::Color GlowingColor::getBrighterShade() {
    float shadeFactorR = (std::sin(time) + 1) / 2; // Oscillates between 0 and 1
    float shadeFactorG = (std::sin(time + 1) + 1) / 2; // Phase shift of 1
    float shadeFactorB = (std::sin(time * 2) + 1) / 2; // Frequency of 2
    time += 0.001; // static variable to keep function state
    sf::Color shadedColor;
    shadedColor.r = std::min(static_cast<int>(baseColor.r * shadeFactorR + 50), 255);
    shadedColor.g = std::min(static_cast<int>(baseColor.g * shadeFactorG + 50), 255);
    shadedColor.b = std::min(static_cast<int>(baseColor.b * shadeFactorB + 50), 255);
    shadedColor.a = baseColor.a; // Keep the same alpha value
    return shadedColor;
}

The GUI supports moving-like animations, using the GlowingColor class to create a glowing effect on the numbers and the grid. The draw method is invoked every frame to update the screen and generate the animation. The GUI also supports screenshots, which can be saved using the saveScreenshot method, and adheres to best coding practices, such as clean code, SOLID principles, and the DRY principle.

The main thread of the program is tasked with managing the GUI and the user input. When the user clicks the middle mouse button, the program flow continues to update the window by passing a reference to the window to the draw method of the SudokuCSP class. The draw method is responsible for drawing the Sudoku grid and numbers, and the GlowingColor class is responsible for creating the glowing effect on the numbers and the grid.

Therefore, the main logic can be easily understood by reading the main loop of the program:

while (window.isOpen()) {
  handleEvents(window, sudoku);
  drawSudoku(window, sudoku);
}

Area of Improvement

• The primary objective of this project is to showcase the capabilities of AI and CSP in resolving complex puzzles and to generate engaging visualizations of the search process. In doing so, the algorithm neglects to incorporate advanced techniques such as forward checking and arc consistency to enhance the efficiency of the backtracking algorithm. These techniques can be employed to reduce the search space and enhance the performance of the algorithm, by eliminating values from the domains of the variables as soon as they are assigned, thereby reducing the search space.
• There are more effective approaches to backtracking in this scenario, such as selecting the order of the variables and the values to be assigned to the variables, which can be accomplished using the Minimum Remaining Values (MRV) and Least Constraining Value (LCV) heuristics. However, this would interfere with the proper functioning of the Cool Matrix visualization, as the visualization relies on the order of the variables and the values to be assigned to the variables.
• The current input format is hard-coded into the program. It could be useful to add a feature that allows users to input their own puzzles in a user-friendly manner, such as through a picture or hand-written input.