Name: Towards AI Legal Name: Towards AI, Inc. Description: Towards AI is the world's leading artificial intelligence (AI) and technology publication. Read by thought-leaders and decision-makers around the world. Phone Number: +1-650-246-9381 Email: [email protected]
228 Park Avenue South New York, NY 10003 United States
Website: Publisher: https://towardsai.net/#publisher Diversity Policy: https://towardsai.net/about Ethics Policy: https://towardsai.net/about Masthead: https://towardsai.net/about
Name: Towards AI Legal Name: Towards AI, Inc. Description: Towards AI is the world's leading artificial intelligence (AI) and technology publication. Founders: Roberto Iriondo, , Job Title: Co-founder and Advisor Works for: Towards AI, Inc. Follow Roberto: X, LinkedIn, GitHub, Google Scholar, Towards AI Profile, Medium, ML@CMU, FreeCodeCamp, Crunchbase, Bloomberg, Roberto Iriondo, Generative AI Lab, Generative AI Lab Denis Piffaretti, Job Title: Co-founder Works for: Towards AI, Inc. Louie Peters, Job Title: Co-founder Works for: Towards AI, Inc. Louis-François Bouchard, Job Title: Co-founder Works for: Towards AI, Inc. Cover:
Towards AI Cover
Logo:
Towards AI Logo
Areas Served: Worldwide Alternate Name: Towards AI, Inc. Alternate Name: Towards AI Co. Alternate Name: towards ai Alternate Name: towardsai Alternate Name: towards.ai Alternate Name: tai Alternate Name: toward ai Alternate Name: toward.ai Alternate Name: Towards AI, Inc. Alternate Name: towardsai.net Alternate Name: pub.towardsai.net
5 stars – based on 497 reviews

Frequently Used, Contextual References

TODO: Remember to copy unique IDs whenever it needs used. i.e., URL: 304b2e42315e

Resources

Unlock the full potential of AI with Building LLMs for Productionβ€”our 470+ page guide to mastering LLMs with practical projects and expert insights!

Publication

Solving SUDOKU with Binary Integer Linear Programming(BILP)
Latest

Solving SUDOKU with Binary Integer Linear Programming(BILP)

Last Updated on September 17, 2022 by Editorial Team

Author(s): Harjot Kaur

Originally published on Towards AI the World’s Leading AI and Technology News and Media Company. If you are building an AI-related product or service, we invite you to consider becoming an AI sponsor. At Towards AI, we help scale AI and technology startups. Let us help you unleash your technology to the masses.

SUDOKU with Binary Integer Linear Programming(BILP)

Background

Sudoku is a logic-based puzzle that first appeared in the U.S. under the title β€œNumber Place” in 1979 in the magazine Dell Pencil Puzzles & Word Games [6]. The game was designed by Howard Garns, an architect who, upon retirement, turned to puzzle creation. In the 1980s, the game grew in popularity in Japan and was renamed by publisher Nikoli to β€œsuji wa dokushin ni kagiru,” which translates as β€œthe digits must remain single.” This was eventually shortened to β€œsudoku” or β€œsingleΒ number.”

Heads upβ€Šβ€”β€Šassuming readers already know the basics of Linear Programming

Is Sudoku an optimization problem?

No. Mostly not. Because there is no objective function we want to maximize or minimize. The sudoku problem can be called a satisfiability or feasibility problem.

Let’s begin with theΒ rules…

Sudoku most commonly appears in its 9 Γ—9 matrix form. The rules are simple: fill in the matrix so that every row, column, and 3 Γ—3 submatrix contains the digits 1 through 9 exactly once. Each puzzle appears with a certain number of givens. The number and location of these determine the game’s level of difficulty.

As we know, each ILP problem is composed of an objective function(not applicable in the case of Sudoku unless there are alternate solutions), decision variables, and constraints.

The good news is that we don’t write constraints for this, we just mathematically put up the rules of the puzzle as constraints!

Integer Programming mathematical model of the SudokuΒ puzzle

For ease of explanation, I’ll be using a 4×4 matrix up ahead. Let us consider the following puzzle to be solved usingΒ BILP.

Figure 1: 4×4 sudokuΒ puzzle

More specifically, we will formulate a binary integer program (BILP) for a general nΓ—n puzzle. Once the program is developed to solve the BILP for Figure 1, it can be easily adapted to solve any SudokuΒ puzzle.

To begin, we define our decision variables:

Generic Binary Decision Variables

When the values of the decision variables are determined, we will know whether each integer k(1 ≀k≀4) appears in each element (i, j) of the nΓ—n Sudoku matrix. That is, the solution to the corresponding Sudoku puzzle will beΒ defined.

We now turn to the ever-important objective function and set of constraints. Notice how the constraints require only a knowledge of the rules of Sudoku puzzles (with the addition of one implicit constraint, which is a constraint (6) below) and do not require a proficiency with the logic necessary to solve such puzzles by hand. A BILP formulation suitable for Sudoku puzzles is as follows:

Min 0 (let us define this as a constant, as there is no function to minimize or maximize)

Subject to

Constraint 1: Each cell contains a single integerΒ k

Constraint 2: Each integer k appears once in eachΒ row

Constraint 3: Each integer k appears once in eachΒ column

Constraint 4: Each integer k appears once in each submatrix

Constraint 5: Given elements G in the matrix are setΒ β€œon”

Constraint 6: Defining the possible value ofΒ integers

And, that’sΒ that!

Let’s solve the above 4×4 Sudoku puzzle(Figure1) using the Excel Solver. The simulation template for a 4×4 puzzle with 64 binary decision variables will look something likeΒ this.

Sudoku Simulation template with 64 Binary Decision Variables

Now, let’s interpret the aforementioned constraints:

Constraint 1: Each cell contains a single integer k. Tabs colored in green(Sum of i,j = 1) will make sure that every position is filled with an integerΒ value.

Constraint 2: Each integer k appears once in each row. Tabs colored in brick red(Sum of row 1:4 >= 1) will ensure that each k appears just once in everyΒ row.

Constraint 3: Each integer k appears once in each column. Tabs colored in olive (Sum of column 1:16 >= 1) will ensure that each k appears just once in everyΒ column.

Constraint 4: Each integer k appears once in each submatrix. Tabs colored in turquoise(Sum of quadrant 1:4 >= 1) will ensure that each k appears just once in every 2×2Β matrix.

Constraint 5: Given elements G in the matrix are set β€œon”. The given value of k is hardΒ coded.

The last step is to convert the Integer Program solution as given in the 64 yellow, peach, grey and blue decision variable cells to the required 4 by 4 Sudoku grid. Each binary cell is then multiplied by the possible set of values a β€œk” can take(which is {1,2,3,4}).

Now let’s get the solution…

This is how the Excel Solver shall lookΒ like

Excel Solver

…and Voila! The solution to the 4×4 puzzle shall look likeΒ this.

The solution to the puzzle inΒ Figure1

Last words

The above logic can be used not just to solve any Sudoku puzzle but also to create one. I hope, you folks found it easy to grasp and fun too! Connect with me on Linkedin to talk more about optimization.


Solving SUDOKU with Binary Integer Linear Programming(BILP) was originally published in Towards AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

Join thousands of data leaders on the AI newsletter. It’s free, we don’t spam, and we never share your email address. Keep up to date with the latest work in AI. From research to projects and ideas. If you are building an AI startup, an AI-related product, or a service, we invite you to consider becoming aΒ sponsor.

Published via Towards AI

Feedback ↓