Solving Sudoku Puzzles Using Logical Candidate Methods

In this article, I describe a basic algorithm that attempts to solve a sudoku problem using four main logical methods.  Sudoku problems can be solved using brute-force and back-tracking algorithms, however I decided I wanted to base my algorithm on logical techniques rather than guessing. This approach does not guarantee a solution, but when its techniques have been exhausted and the puzzle is still not solved, a backtracking algorithm can be used to finish the puzzle in perhaps a more efficient amount of time than a backtracking algorithm alone could.

Principles

Easy sudoku puzzle with 30 clues
Easy sudoku puzzle with 30 clues
  • The sudoku puzzle is divided into 9 rows, 9 columns, and 9 3x3 boxes.

  • A line is defined as a row or column of 9 squares.

  • The parent containers for a particular square are the row and column lines that the square lies on and the box that the square is part of.

  • One and only one of each integer in the interval [1, 9] is present in each row, column, and box.

  • The certain value of a square is the number that must be present because it has either been defined at the start to be in this position or all the other candidates for this position have been eliminated.

  • The candidates for a particular square are the possible values for this square as a consequence of the current certain values.  These are often represented using pencil marks when the puzzle is solved by a human.  The set of candidates for the current square will be denoted as X.

The following function, n(a, S), is also defined, which takes parameters a, an integer in the interval [1, 9], and S, a collection of the candidate sets for each square in a collection of squares, and returns the number of squares in S for which a is a candidate:

\[ n(a, S) := \sum\limits_{s \in S} \chi_s(a) = \sum\limits_{s \in S} \left\{ \begin{array}{ll} 1 & \mbox{if } a \in s \\ 0 & \mbox{if } a \notin s \end{array} \right. \]

This could perhaps be better be defined as the multiplicity of value a in a multiset of candidates of child squares in the collection of squares, however to my knowledge Python does not have support for multisets, and so collections of sets are used.

First Steps

First, the candidates for every blank square on the sudoku grid are found.  The candidates cannot be any of the certain values of the parent containers, so the set of candidates of the current square is the relative complement of the certain values of the parent containers, C, with respect to {1, 2, … , 8, 9} (the possible values for a square with no constraints).

\[ X = \{1, 2 ... 8, 9\} \setminus C \]

During this procedure and at any other time in the program, if a new certain value is found, the following methods are performed on the coordinates of the square.  The recalculating method is added to the front of the operation queue as it requires little calculation and has a very high utility.  The other methods are added to the back of the operation queue to be executed when recalculation due to this certain value and any consequential certain values has finished. If no certain values are found, the methods are called on each box and line in turn as appropriate.

These methods usually remove candidates for squares and result in certain values being found by elimination of candidates or deduction from the values of other candidates in the parent containers, however if this is fruitless, the program cannot solve the puzzle using its logic, so an alternate approach such as backtracking should be used.

Recalculating and Unique Candidates

When a new certain value is found, due to principle 4, the certain value cannot be a candidate for any other squares in the parent containers of this square.  Letting a be the certain value and P the set of the candidates of all the squares in the parent containers excluding the updated square:

\[ X = \{a\} \Longleftrightarrow a \notin P \]

Therefore, the recalculating algorithm removes the new certain value from the candidates of all the squares in the parent container excluding the updated square.  This sometimes leads to a new certain value being found due to elimination of other candidates for a square. This value is a unique candidate (also known as a hidden single), and the recalculate method is then performed with this new square, as stated above.

Single Appearance

This method assigns a value to a square by finding a value which appears as a candidate of only one square in a line or box.  Letting S be the squares within the parent line or box and the value *a *be a candidate:

\[ \text{ If } a \in X \land n(a, S) = 1 \text{ then } X = \{a\} \]

I accomplished this in the program using the following code:

def single_appearance_using_coords(self, square_coords):
    for i in range(1, 10):
        appearance = None
        for coords in square_coords:
            nums = self.nums_for_coords(coords)
            if i in nums:
                if len(nums) == 1 or appearance is not None:
                    appearance = None
                    break
                appearance = coords
        if not appearance:
            continue
        # If a value is only possible once in a box / line, then the position of this possibility is where it lies
        self.set_nums_for_coords(appearance, set([i]))
        self.calc_list.insert(0, lambda coords=appearance, i=i: self.recalc_due_to_update(coords, set([i])))

The single appearance and recalculation methods are often enough to solve “easy” and sometimes “medium” difficulty sudoku puzzles, however the next two methods have proved very useful in solving harder problems.

Locked Candidates

A Locked Pair Suppose a line with a set of child squares L, intersects a box with a set of child squares B.  Letting a represent a candidate:

\[ \text{ If } n(a, B)-n(a, L \cap B) = 0 \text{ then } \\ a \in L \cap B \text{ and so } \\ a \notin (L \setminus B) \]

The principle of this method is that if a candidate is “locked” into only one row or column in a box i.e. it only appears along one line in a particular box, it must appear in one of the squares on this line within the box. Therefore, this candidate cannot appear outside of the box on this line, so the candidate can be removed from all squares outside the box on this line.

For example, in this grid on the right, the candidate 4 only appears in the second column of the first box (shown in yellow), so 4 can be excluded as a candidate in the second column of the remaining two boxes (shown in red).

Here is my implementation:

def locked_candidates(self, s_coords=None, b_coords=None):
    box = SudokuBox(self, s_coords=s_coords, b_coords=b_coords)
    single_line_vals = box.single_line_vals()
    for line, val in single_line_vals:
        square_coords_not_in_box = set(line.square_coords()) - set(box.square_coords())
        for coord_pair in square_coords_not_in_box:
            nums = self.nums_for_coords(coord_pair)
            if val in nums:
                nums.discard(val)
                self.set_nums_for_coords(coord_pair, nums)
                if len(nums) == 1:
                    self.calc_list.insert(0, lambda coords=coord_pair, nums=nums: self.recalc_due_to_update(coords, nums))

And here is the box.single_line_vals() method:

def single_line_vals(self):
    # Note: excludes the certain numbers
    cert_numbers = self.cert_numbers()
    single_line_vals = []
    for orientation in [L_VERT, L_HORIZ]:
        possibility_list = []

        for i in range(3):
            line = SudokuLine(self.parent, (self.coords[0]*3+i%3, self.coords[1]*3+i%3), orientation)
            possibilities = self.possibilities_on_line(line) - cert_numbers
            possibility_list.append((line, possibilities))

        for i in range(3):
            line = possibility_list[i][0]
            line_possibilities = possibility_list[i][1]
            other_lines_possibilities = set()
            for possibilities in possibility_list[:i] + possibility_list[i+1:]:
                other_lines_possibilities |= possibilities[1]
            unique_line_possibilities = line_possibilities - other_lines_possibilities
            single_line_vals.extend([(line, val) for val in unique_line_possibilities])
    return single_line_vals

Conjugate Groups

Conjugate PairsSuppose a group of squares, G, exists in a line or box such that the cardinality of the set of candidates of the group, C, is equal to the cardinality of G. If this is the case, then the set of candidates of the other squares in the line or box, Q must not include any of the candidates in C.

\[ C := \bigcup G \\ \text{ If } |G| = |C| \text{ then } Q \cap C = \varnothing \]

In the example on the right, there is a conjugate pair {5, 6} (shown in yellow) in the first box and the first column, so 5 and 6 can be removed from the candidates of all other squares in the first box and the first column (shown in red).

This method works because if a group of squares exist in a line or box with the same number of shared candidates as the size of the group, then the values of the squares can only collectively be the shared candidates, as each square must be unique due the squares being in a shared line or box.  Consequently, other squares within the line or box that the group resides in cannot have these values as candidates.

Here is my implementation:

def conjugate_groups_using_coords(self, group_coords):
    group_squares = [(coords, self.nums_for_coords(coords)) for coords in group_coords]
    for n in range(2, 8):
        possible_conjugate_squares = [square for square in group_squares if len(square[1]) != 1 and len(square[1]) <= n]
        possible_conjugate_groups = itertools.combinations(possible_conjugate_squares, n)
        for poss_group in possible_conjugate_groups:
            nums_union = set()
            for square in poss_group:
                nums_union |= square[1]
                if len(nums_union) > n:
                    break
            if len(nums_union) != n:
                continue
            update_coords = [square for square in group_squares if square not in poss_group]
            for coord_pair, nums in update_coords:
                old_nums_len = len(nums)
                nums -= nums_union
                if old_nums_len == len(nums):
                    continue
                self.set_nums_for_coords(coord_pair, nums)
                if len(nums) == 1:
                    self.calc_list.insert(0, lambda coords=coord_pair, nums=nums: self.recalc_due_to_update(coords, nums))

Solver Demo

In this video, this sudoku is being solved.  The first pale green highlights show the grids for which the initial candidates are being calculated.  The orange squares are those that are currently being examined by either the single appearance, locked candidates, or conjugate groups method.  When candidates have been modified by one of these methods, the colour of their square changes: blue for the single appearance method, gold for the locked candidates method, and pink for the conjugate groups method.  If a certain value has been found by recalculation of possible candidates, its square turns green.  A delay of \( 100 + 200\log\left(1 + \frac{n}{100}\right) \) ms has been added between the methods, where n is the operation index.

Acknowledgements

The images used as examples for the Locked Pair and Conjugate Pair strategies are cropped versions of this image and this image respectively. The original images are sourced from sudopedia.enjoysudoku.com, a mirror of sudopedia.org (dead link at time of writing). The original images are available under the GFDL, so the cropped derivative images displayed are licensed by requirement under the GFDL.

The sudoku puzzle solved in the video, Sudoku Puzzle Hard For Brute Force, is available under the GFDL, and so the solution to this puzzle in the video is also licensed under the GFDL.

A Guessing Game

Lately I’ve been thinking about the best way of playing games, in particular, how one could write an algorithm to perform best in a game.  In the aptly-named “guessing game”, a person chooses a word from a predefined list, and the computer than attempts to guess this word using the fewest guesses possible.

Initially, I thought that the best way of tackling this would be to find a measure of how valuable each guess would be in reducing the number of words: a measure that would be dependent on firstly the entropy of the guess (how much each guess tells you about the word that has been chosen), but also the probability of this guess actually telling you anything.

Thinking about the probability of the guess telling you anything made me realise that however incorrect guesses could be just as useful as correct guesses.  Therefore, perhaps the best guess would be a guess that divides the word possibility space into two groups of equal size.  Consequently, no matter the result, the guess halves the possibility space.

I was feeling sarcastic, so I chose a list of motivating words (thanks dictionary-thesaurus.com!) as my predefined word collection.  Here is what I came up with in Python:

import string

def find_most_useful_guess(words):
    aim_occ = len(words)/2 # The ideal number of occurrences that would split the set of words in half
    best_guess, best_occ_diff = '', 26
    for ch in string.ascii_lowercase:
        occurences = sum(1 for word in words if ch in word)
        if (abs(aim_occ - occurences) < best_occ_diff):
            best_guess = ch
            best_occ_diff = abs(aim_occ - occurences)
    return best_guess

words = []
with open("motivating_words.txt", "r") as f:
    words = [line.strip().lower() for line in f]

while len(words) > 1:
    guess = find_most_useful_guess(words)
    in_word = input("Is " + guess + " in the word? [y] ") == "y"
    words = [w for w in words if guess in w] if in_word else [w for w in words if guess not in w]

print("I think your word was \"" + words[0] + "\".")

The program worked in limited testing using the set of motivating words. A potential improvement could be dealing with anagrams, which will currently leave the program in an infinite guessing loop.

Ideally, the program will produce a solution in \( \log_2 n \) guesses, as in an ideal scenario, each guess reduces the input size by half.

Flickr Flow

Ever since Socialite introduced the Explore section of Flickr to me, I had always been fascinated by the range of high-quality photos picked out by the Flickr community. However, I quickly grew tired of the unread-item guilt and the cluttered appearance of the app and left it behind in favour of Reeder and Twitter for Mac. There was no way of exploring Flickr on my iPod touch or iPad which was simple, clutter-free, and allowed me to easily favourite my favourite photos.

From this void, Flickr Flow was born.

Flickr Flow iPad screenshot

Flickr Flow is a refreshingly simple iOS app which solves this need. Photos can be browsed and favourited. The interface really gets out of the way: the description bar fades away automatically allowing you to just see the photo. The landscape iPhone view is a clear demonstration of this: it’s just about the pictures:

Flickr Flow iPhone landscape screenshot

To favourite the image, just tap on the image to display the description view and hit the favourite button:

Flickr Flow image description view

Flickr Flow has enabled me to explore the vibrant and interesting photos available on Flickr on my iOS devices without the clutter. If you’re interested, download it from the App Store for free. Flickr Flow is no longer available on the App Store.

Tracking Stats With Collectd

Collectd is a daemon which collects performance statistics from a wide variety of sources and stores them in several ways. You can configure every aspect of it in its configuration file. Getting started with collectd is easy with Homebrew:

brew install collectd

Once collectd is installed, you can configure it with plugins for reading and writing data. If your Homebrew installation is located in /usr/local, you can find the configuration file at /usr/local/etc/collectd.conf. To load a plugin, first find the plugin in the “LoadPlugin” section. This will look something like the following:1

##############################################################################
# LoadPlugin section                                                         #
#----------------------------------------------------------------------------#
# Lines beginning with a single `#' belong to plugins which have been built  #
# but are disabled by default.                                               #
#                                                                            #
# Lines begnning with `##' belong to plugins which have not been built due   #
# to missing dependencies or because they have been deactivated explicitly.  #
##############################################################################

##LoadPlugin amqp
#LoadPlugin apache
#LoadPlugin apcups
#LoadPlugin apple_sensors
#LoadPlugin ascent
#LoadPlugin battery
#LoadPlugin bind
##LoadPlugin conntrack
#LoadPlugin contextswitch
LoadPlugin cpu
##LoadPlugin cpufreq
#LoadPlugin csv
#LoadPlugin curl
##LoadPlugin curl_json
#LoadPlugin curl_xml
##LoadPlugin dbi
#LoadPlugin df
LoadPlugin disk
#LoadPlugin dns
#LoadPlugin email
##LoadPlugin entropy
#LoadPlugin exec
#LoadPlugin filecount
##LoadPlugin fscache
##LoadPlugin gmond
#LoadPlugin hddtemp
LoadPlugin interface
##LoadPlugin iptables
##LoadPlugin ipmi
##LoadPlugin ipvs
##LoadPlugin irq
##LoadPlugin java
##LoadPlugin libvirt
LoadPlugin load
##LoadPlugin lpar
##LoadPlugin madwifi
#LoadPlugin mbmon
##LoadPlugin memcachec
#LoadPlugin memcached
LoadPlugin memory
##LoadPlugin modbus
#LoadPlugin multimeter
##LoadPlugin mysql
##LoadPlugin netapp
##LoadPlugin netlink
LoadPlugin network
##LoadPlugin nfs
#LoadPlugin nginx
##LoadPlugin notify_desktop
##LoadPlugin notify_email
#LoadPlugin ntpd
##LoadPlugin nut
#LoadPlugin olsrd
##LoadPlugin onewire
#LoadPlugin openvpn
##LoadPlugin oracle
#LoadPlugin perl
##LoadPlugin pinba
##LoadPlugin ping
#LoadPlugin postgresql
#LoadPlugin powerdns
LoadPlugin processes
##LoadPlugin protocols
##LoadPlugin python
##LoadPlugin redis
##LoadPlugin routeros
##LoadPlugin rrdcached
##LoadPlugin rrdtool
##LoadPlugin sensors
##LoadPlugin serial
#LoadPlugin snmp
#LoadPlugin swap
#LoadPlugin table
#LoadPlugin tail
##LoadPlugin tape
#LoadPlugin tcpconns
#LoadPlugin teamspeak2
#LoadPlugin ted
##LoadPlugin thermal
##LoadPlugin tokyotyrant
#LoadPlugin unixsock
LoadPlugin uptime
#LoadPlugin users
#LoadPlugin uuid
##LoadPlugin varnish
##LoadPlugin vmem
##LoadPlugin vserver
##LoadPlugin wireless
#LoadPlugin write_http
##LoadPlugin write_redis
##LoadPlugin xmms
##LoadPlugin zfs_arc

You should see a “LoadPlugin x” where x is substituted with the plugin name. This may be prefixed by 0–2 hashes. If it has no hashes in front of it, it is loaded. If it has one hash in front of it, it is not loaded but it is supported by your system. If it has two hashes at the start, it is not supported by your system: you are probably missing a required library.

Following these rules, you can load a plugin that has one hash prepended to it by removing this hash. You can also unload a plugin by prefixing it with a hash.

Next, configure the plugin in the plugin configuration section where plugins are configured with syntax like this:

<Plugin apache>
  <Instance "local">
    URL "http://localhost/status?auto"
    User "www-user"
    Password "secret"
    # CACert "/etc/ssl/ca.crt"
  </Instance>
</Plugin>

You can look up the configuration for each plugin on the collectd website.

Once you’ve got collectd tracking statistics, it’s time to output these statistics. I view them via a web interface called Visage. It’s a gem that can be installed by running gem install visage-app. The installation instructions say Visage can be started with visage-app start but that didn’t work for me. I used sudo $(dirname $(dirname $(gem which visage-app)))/bin/visage-app start. You should be able to run this on start up with launchctl.

When Visage is running, you can find it at 127.0.0.1:9292 (replacing “127.0.0.1” with your hostname if necessary). Start by creating a profile, where you select data you want graphed. Then hit enter and you can see the graph. Deletion of profiles is not currently supported but you can remove them manually from the YAML file they are stored in ({Ruby gems folder}/gems/visage-app-1.0.0/lib/visage-app/config/profiles.yaml). I use rbenv and my file is located at /Users/Henry/.rbenv/versions/1.9.3-p0/lib/ruby/gems/1.9.1/gems/visage-app-1.0.0/lib/visage-app/config/profiles.yaml.

Using the network plugin, it’s possible to have one Visage server for all your computers. I use this approach for my computers, they all report back to a central server. The data can then be grouped together in Visage.

I’ve been using Visage for several months without problems after switching from my own home-baked solution for tracking stats. For more info, see:

  1. Yours will probably have fewer unsupported plugins, I’m running this on my MacBook not long after a clean install. 

Securing SSH

After configuring my server, I decided to set up SSH on it so I could remotely send commands to the server. All was working fine and I managed to connect Prompt to my server and SSH into my server from my iPad and iPod touch. However, after I decided to look at /var/log/secure.log in Console, I noticed messages like this:

Sep 13 07:04:35 server sshd[23502]: Invalid user oracle from 94.249.186.66
Sep 13 07:04:35 server sshd[23503]: input_userauth_request: invalid user oracle
Sep 13 07:04:35 server sshd[23503]: Received disconnect from 94.249.186.66: 11: Bye Bye
Sep 13 07:04:36 server sshd[23507]: Invalid user test from 94.249.186.66
Sep 13 07:04:36 server sshd[23508]: input_userauth_request: invalid user test
Sep 13 07:04:36 server sshd[23508]: Received disconnect from 94.249.186.66: 11: Bye Bye

Several IPs were trying to hack into my server.

Installing DenyHosts

After some research, I decided to install DenyHosts on my server. This monitors the SSH log file (secure.log if you’re on a Mac) and adds IPs that make too many incorrect attempts to access your server to your /etc/hosts.deny file. You can see how successful this program is by looking at the statistics some users are contributing. You can tell DenyHosts to use these statistics by enabling synchronisation mode. To install DenyHosts, download it, unarchive it, and cd into the directory (cd ~/Downloads/DenyHosts-2.6). Then run the setup script with sudo python setup.py install. Once DenyHosts has installed, edit the configuration file:

cd /usr/share/denyhosts
cp denyhosts.cfg-dist denyhosts.cfg
vi denyhosts.cfg

You can view my example configuration file on GitHub. Next, set up the DenyHosts daemon:

cd /usr/share/denyhosts
cp daemon-control.dist daemon-control
vi daemon-control

You should only need to edit lines 14–16. Here are the lines from my daemon-control:

DENYHOSTS_BIN   = "/usr/local/bin/denyhosts.py"
DENYHOSTS_LOCK  = "/var/lock/subsys/denyhosts"
DENYHOSTS_CFG   = "/usr/share/denyhosts/denyhosts.cfg"

To check everything works, try launching the daemon:

sudo /usr/share/denyhosts/daemon-control start

You could use this command to start the daemon every time you boot up your server. Alternatively, you could load it into launchctl (or cron). To load it into launchctl, first create the file /Library/LaunchDaemons/com.denyhosts.dh-daemon.plist. You could do this in the Terminal with the following commands:

sudo touch /Library/LaunchDaemons/com.denyhosts.dh-daemon.plist
sudo vi /Library/LaunchDaemons/com.denyhosts.dh-daemon.plist

Give it the contents:

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple Computer//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
  <dict>
    <key>Label</key>
    <string>com.hmercer.denyhosts</string>
    <key>ProgramArguments</key>
    <array>
      <string>/usr/share/denyhosts/daemon-control</string>
      <string>start</string>
    </array>
    <key>RunAtLoad</key>
    <true/>
  </dict>
</plist>

… and load it into launchctl:

sudo chown root /Library/LaunchDaemons/com.denyhosts.dh-daemon.plist
sudo launchctl load /Library/LaunchDaemons/com.denyhosts.dh-daemon.plist

Reporting blacklisted IPs

Nazar Aziz, creator of report-hack-isp:

The real problem still remains. SSHD attacks are now on the increase and it is no longer sufficient to blacklist offenders. Ideally, any SSHD hack attempt should be blacklisted, logged and most importantly; the ISP of the attacker must be notified in order to disconnect the attacking machine from the internet.

I’ve had this script running on one of my dedicated boxes for the last 12 hours and since then have received half a dozen emails from various ISPs confirming that the attacker’s servers were identified and cut off from the Internet. WIN.

Today, over 1,000,000 unique hosts have been denied by DenyHosts1. report-hack-isp is a DenyHosts plugin that will lookup the attacker’s ISP details and send an abuse report containing an excerpt of the SSHD logfile relevant to the attack. I’m now going to walk through installing this plugin, feel free to skip this section.

First, download the plugin, and extract it. Then enter the following command into the terminal, replacing <report-hack-isp-directory> with the directory you unarchived (just drag it in):

cd <report-hack-isp-directory>
sudo mv notify_isp.rb /etc/denyhosts/plugins/notify_isp.rb

Edit notify_isp.rb and replace SMTP_SERVER and SMTP_PORT with your email server’s details. Replace EMAIL_FROM with your own email address. Change LOG_FILE = ‘/var/log/sshd/**’ to your actual SSHD log file location (on a Mac it’s /var/log/secure.log). You can customise the email message in the function def get_email_message Then create the log file with sudo touch /var/log/notify_isp.log.

Make the file executable (chmod a+x notify_isp.rb) and update denyhosts.conf, pointing PLUGIN_DENY to your script. If you’re using my example DenyHosts configuration, just uncomment line 391. Restart DenyHosts and you’re done:

sudo /usr/share/denyhosts/daemon-control stop
sudo /usr/share/denyhosts/daemon-control start

Using a key pair instead of a password

To heighten SSH security, use a key pair instead of a password. This makes hacking into your server much tougher for the bad guys.

On the local machine

To get started, run ssh-keygen -t rsa on the local machine. Accept the default path and enter a password (this can be saved in the keychain). Next, go to Finder, and from the “Go” menu, select “Go to Folder…”. Enter “~/.ssh”. Copy the file id_rsa.pub.

On the remote machine

Now, on the remote machine, run touch .ssh/authorized_keys. Paste the contents of the id_rsa.pub file into this file.

Log into the remote machine as normal, and on the request for the password, type the password you entered to generate the public key. After the first login, you won’t have to type a password again.

Only allowing public key authentication

To disable password authentication and only allow public key authentication, boosting your security further, edit the file /etc/sshd_config. Find the line with the option PasswordAuthentication and, making sure it is uncommented, change it to PasswordAuthentication no. Next, find the line with the option ChallengeResponseAuthentication and, making sure it is not commented, replace it with ChallengeResponseAuthentication no. Finally, restart SSHD. This can be done on a Mac by going to the Sharing section of System Preferences and turning Remote Login off then on.

I hope this post has helped you secure your computer further. If you have any further thoughts or comments, you can get in touch with me using the comment button below.

More Recently Less Recently