{"id":9211,"date":"2023-05-09T13:15:15","date_gmt":"2023-05-09T17:15:15","guid":{"rendered":"https:\/\/blogs.mathworks.com\/community\/?p=9211"},"modified":"2024-01-07T17:07:02","modified_gmt":"2024-01-07T22:07:02","slug":"solving-sudoku-with-matlab","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/community\/2023\/05\/09\/solving-sudoku-with-matlab\/","title":{"rendered":"Solving Sudoku with MATLAB"},"content":{"rendered":"
\n
Today's guest article is by Wesley Hamilton, a STEM Outreach engineer here at MathWorks. Wesley's roles involve popularizing the use of MATLAB and Simulink for younger folk, especially towards mathematical topics, and this blog is an accompanying piece to a workshop<\/a> being run by the National Museum of Math<\/a> in New York City.<\/span><\/em><\/div>\n
Sudoku is a popular puzzle in which puzzlers fill in a 9x9 grid with the digits 1-9 such that a number of conditions are met: each 3x3 subgrid, row, and column must contain all digits. While Sudoku is usually referred to as a logic puzzle, it is actually possible to recast these puzzles as a (mathematical) constrainted optimization problem, wherein the optimal solution gets interpreted as the inputs for a completed Sudoku puzzle. What's crazy about this formulation though is that the function we optimize will be the zero function, so that any<\/span> input is optimal; all of the legwork is in satisfying the optimization problem's constraints. Interested? Read on to learn more!<\/div>\n
The presentation and code in this blog are adapted from a workshop developed by Dr. Tim Chartier, based on code developed in collaboration with Dr. Amy Langville of the College of Charleston and her students.<\/div>\n
\n
Table of Contents<\/span><\/div>\n
Rules and History of Sudoku
\n<\/a>Solving Sudoku Puzzles, part 1
\n<\/a>Linear Programming
\n<\/a>Sudoku as a Linear Program
\n<\/a> Box constraints
\n<\/a> Row constraints
\n<\/a> Column constraints
\n<\/a> Subgrid constraints
\n<\/a>Solving Sudoku Puzzles, part 2
\n<\/a> Ordering of decision variables
\n<\/a> Box constraints
\n<\/a> Row constraints
\n<\/a> Column constraints
\n<\/a> Subgrid constraints
\n<\/a> The givens
\n<\/a>Further directions
\n<\/a>Just the code<\/a><\/div>\n<\/div>\n
<\/div>\n

Rules and History of Sudoku<\/h2>\n
The classic version of Sudoku most people are familiar with consists of a 9x9 grid divided into nine 3x3 subgrids. The grid will start with some boxes filled in with the digits 1-9, and the goal of the puzzle is to fill in each box with one of the 9 digits in a way that the following three conditions are satisfied:<\/div>\n
    \n
  1. Every row of the grid contains each of the digits 1-9, and each digit only appears once,<\/li>\n
  2. Every column of the grid contains each of the digits 1-9, and each digit only appears once,<\/li>\n
  3. Every 3x3 subgrid contains each of the digits 1-9, and each digit only appears once.<\/li>\n<\/ol>\n
    Here is an example of a 9x9 Sudoku puzzle, retrieved from websudoku.com<\/a> on May 3, 2023.<\/div>\n
    \"sudoku_example.png\"<\/div>\n
    One variation of the puzzle is the 4x4 version, in which a 4x4 grid is split into four 2x2 subgrids and the three conditions are modified so that only the digits 1-4 are used. This version is often used as an easier version than the 9x9, and makes visualizing what happens in the computational side of things a bit more tractable as well.<\/div>\n
    Here is an example of a 4x4 Sudoku puzzle, generated by Dr. Tim Chartier<\/a>, MoMath's 2022\u20132023 Distinguished Visiting Professor for the Public Dissemination of Mathematics.<\/div>\n
    \"sudoku_4x4_puzzle.png\"<\/div>\n
    Sudoku was popularized in Japan in the late 1980s, before grabbing worldwide attention in the early 2000s. Unbeknownst to many, very early versions of Sudoku appeared in France in the late 1800s as puzzle-variations of magic squares<\/a>; see the Wikipedia page<\/a> and its references for more information.<\/div>\n
    The next section walks through the basics of solving Sudoku puzzles. If you're already very familiar with Sudoku, feel free to skip down to the text right after the completed 4x4 puzzle<\/a>.<\/div>\n

    Solving Sudoku Puzzles, part 1<\/h2>\n
    So how does one solve a Sudoku puzzle? In practice, we iteratively apply the three conditions to identify which numbers go in which boxes until all boxes are filled in. In harder puzzles we may be forced to make a choice between two equally likely entries; in these situations we'll often try writing in one of the options and seeing what other numbers can get filled in based on that, and then either run into a contradiction, or solve the board.<\/div>\n
    Let's see this process in action with Tim's 4x4 puzzle. For clarity, the three conditions we'll be iteratively checking are:<\/div>\n
      \n
    1. Every row of the grid contains each of the digits 1-4, and each digit only appears once,<\/li>\n
    2. Every column of the grid contains each of the digits 1-4, and each digit only appears once,<\/li>\n
    3. Every 2x2 subgrid contains each of the digits 1-4, and each digit only appears once.<\/li>\n<\/ol>\n
      First we'll focus on the upper-right 2x2 subgrid and identify where we may be able to fill in a number, in either the red circle or the blue square.<\/div>\n
      \"sudoku_4x4_puzzle_options_2.png\"<\/div>\n
      Applying condition 3., we know that the digits in these empty grid boxes have to be 2 and 3. So which digit goes where? By condition 2., each column of the grid can only contain each digit exactly once, and the fourth column (containing the blue square) already contains a 2, so it is not possible to write the digit 2 in the blue square (similarly, by condition 1. the row with the blue square already has the digit 2 somewhere in the row). Thus, the digit 2 goes in the square with the red circle.<\/div>\n
      \"sudoku_4x4_puzzle_first_write-in.png\"<\/div>\n
      Applying condition 3. to the same subgrid, we conclude the remaining grid box must contain the digit 3.<\/div>\n
      \"sudoku_4x4_puzzle_second_write-in.png\"<\/div>\n
      Continuing in this way we'll eventually be able to fill in every box; for example, the next move might be writing in the digit 4 in the only remaining box in the second row. Feel free to try solving this 4x4 on your own, and check your solution against ours:<\/div>\n
      \"sudoku_4x4_puzzle_solution.png\"<\/div>\n
      Awesome! But what if we want to have MATLAB solve the puzzle for us? An initial approach might be to code (in some way) these three constraints and have our computer iterate through each row, column, and subgrid writing in digits one-by-one. What happens if there are two digits that might work in a grid box? Are there other logical steps that might occur in a harder puzzle that we can't anticipate?<\/div>\n
      Instead of taking this approach, we'll take a very different, and possibly cleverer, approach making use of some deep and powerful computational mathematics known as Linear Programming.<\/div>\n

      Linear Programming<\/h2>\n
      Linear programming is, simply put, an optimization problem in which the objective function and constraints are all linear. Let's break down what each of these pieces mean:<\/div>\n