A Sudoku solver implemented in Lua

Table of contents:

• Introduction

• The algorithm -- How and why it works

• The command-line run wrapper

Introduction

This post describes a Sudoku puzzle solver implemented in Lua.

The original Python code was copied from https://www.geeksforgeeks.org/dsa/sudoku-problem-in-python/.

I used the online code converter at https://pythonconvert.com/code-converter/convert-python-to-lua to translate the Python code to Lua, then prettied it up a bit.

I added the ability to read a Sudoku problem from a text file. See function read_grid.

I also added a solution checker that verifies that each digit (1 to 9) is used exactly once in each row, column, and 3 X 3 box.

Note that this is a brute-force solver. It uses backtracking to try every possible solution until one works. Still, it seems remarkably fast. On my not so new or powerful machine, it solves 10 puzzles in under 1 second. And, using luajit in place of lua to run this code speeds it up by a factor of 5 or more.

The source for sudoku01.lua and sudoku01run.lua is here sudoku01-source.zip

The source (zip file) also contains a number of sample Sudoku problem input data files. Take a look at any of them to learn the format. Then you can write your own sample Sudoku problems. Look at function read_grid to learn about the format. Note that lines that begin with "-- " are considered to be comments and are ignored.

The algorithm -- How and why it works

Let's look at the algorithm in more detail. Look at function solve_sudoku in file sudoku01.lua. Notice the following:

• Function solve_sudoku calls itself recursively.

• Each time solve_sudoku is called, it tries the next value of num over the range 1 through 9.

• And, as part of that attempt, it attempts to fill out the rest of the grid (through its nested, recursive calls to itself). In particular, it:

• Tries to find an empty cell, using function find_empty_location. If there is no empty cell, the grid has been filled and we've succeeded and are finished. So, it returns true.

• If it finds an empty location, it checks each of the values 1 through 9 attempting to see if that is safe in that location, using function check_location_is_safe, which checks to make sure that the digit does not already exist in that row or column or (3 by 3) box.

• If no number is safe in that location, it means that some location has been filled in with a bad number. So it fails (returns false) to force backtracking and an attempt with at alternative number.

The command-line run wrapper

The sudoku01.lua script can be either imported with require or can be executed from the command-line. In order to run it from the command-line set the environment variable LUACLI. On Linux I do this with the following:

$ LUACLI=1 ./sudoku01.lua {sudoku01.dat ...}

In order to make this more convenient, I created the sudoku01run.lua script. It calls the main function in sudoku01.lua. It also (1) eliminates the need to set the LUACLI environment variable and (2) supports a --silent command-line option. Run $ lua ./sudoku01run.lua -h for help.

sudoku01run.lua uses argparse, which you may want to look at. argparse can be installed from Luarocks. See https://luarocks.org/modules/argparse/argparse.