Sudoku Solver, 2022-03-14

dancing_links.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
:mod:`dancing_links`
==================

.. module:: dancing_links
    :platform: Unix, Windows
    :synopsis: An implementation of Donald Knuth's Dancing Links in Python.

Created on 2015-10-19, 22:53

"""

import copy
import math
from itertools import product


class DancingLinksSolver(object):
    """A Dancing Links Algorithm solver for Sudokus.

    This code has been adapted from http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html,
    only modified slightly to accommodate class structure and Python 2.6.

    # Author: Ali Assaf <ali.assaf.mail@gmail.com>
    # Copyright: (C) 2010 Ali Assaf
    # License: GNU General Public License <http://www.gnu.org/licenses/>

    """

    def __init__(self, sudoku):
        self.sudoku = sudoku

    def solve(self):
        """Runs the Dancing Links/Algorithm X solver on the Sudoku.

        This code has been adapted from http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html

        :return: List of lists with the same size as the input Sudoku, representing solutions.
        :rtype: list

        """

        R, C = int(math.sqrt(len(self.sudoku))), int(math.sqrt(len(self.sudoku[0])))
        N = R * C

        X = (
            [("rc", rc) for rc in product(range(N), range(N))]
            + [("rn", rn) for rn in product(range(N), range(1, N + 1))]
            + [("cn", cn) for cn in product(range(N), range(1, N + 1))]
            + [("bn", bn) for bn in product(range(N), range(1, N + 1))]
        )
        Y = dict()

        for r, c, n in product(range(N), range(N), range(1, N + 1)):
            b = (r // R) * R + (c // C)  # Box number
            Y[(r, c, n)] = [
                ("rc", (r, c)),
                ("rn", (r, n)),
                ("cn", (c, n)),
                ("bn", (b, n)),
            ]

        X, Y = self._exact_cover(X, Y)

        for i, row in enumerate(self.sudoku):
            for j, n in enumerate(row):
                if n:
                    self._select(X, Y, (i, j, n))

        for solution in self._solve(X, Y, []):
            grid = copy.deepcopy(self.sudoku)
            for (r, c, n) in solution:
                grid[r][c] = n
            yield grid

    @staticmethod
    def _exact_cover(X, Y):
        # Dict comprehension does not exist in Python 2.6...
        # X = {j: set() for j in X}
        X_out = {}
        for j in X:
            X_out[j] = set()

        for i, row in Y.items():
            for j in row:
                X_out[j].add(i)
        return X_out, Y

    def _solve(self, X, Y, solution):
        if not X:
            yield list(solution)
        else:
            c = min(X, key=lambda c: len(X[c]))
            for r in list(X[c]):
                solution.append(r)
                cols = self._select(X, Y, r)
                for s in self._solve(X, Y, solution):
                    yield s
                self._deselect(X, Y, r, cols)
                solution.pop()

    @staticmethod
    def _select(X, Y, r):
        cols = []
        for j in Y[r]:
            for i in X[j]:
                for k in Y[i]:
                    if k != j:
                        X[k].remove(i)
            cols.append(X.pop(j))
        return cols

    @staticmethod
    def _deselect(X, Y, r, cols):
        for j in reversed(Y[r]):
            X[j] = cols.pop()
            for i in X[j]:
                for k in Y[i]:
                    if k != j:
                        X[k].add(i)

hard.txt

****5**7*
*5**1*4*2
871******
*6*42***5
**4***6**
2***76*1*
******851
5*7*4**3*
*1**9****

hard_solution.txt

642359178
953817462
871264593
169423785
734581629
285976314
496732851
527148936
318695247

medium.txt

*72****6*
***72*9*4
*9*1****2
*******4*
82*4*71**
**9*6*8**
***9**6**
**3*72*9*
*6*843*7*

medium_solution.txt

172394568
358726914
694158732
715289346
826437159
439561827
247915683
583672491
961843275

References.md

• Sudoku Solving Techniques
• Sudoku on Wikipedia

simple.txt

*3*467*5*
92**1***6
*673**148
3*1**6*27
4**85*6**
*9*2**4**
**5624**1
2*3***5*4
*4**3*7*2

simple_solution.txt

138467259
924518376
567392148
351946827
472851693
896273415
785624931
213789564
649135782

sudoku.py

"""
Script for solving sudokus.

Material worth reading: 
- https://en.wikipedia.org/wiki/Sudoku

The objective is to fill a 9 × 9 grid with digits so that each column, each row, 
and each of the nine 3 × 3 subgrids that compose the grid (also called "boxes", "blocks", or "regions") 
contain all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, 
which for a well-posed puzzle has a single solution.

"""

# Proposed first implementation strategy:
# 1. Read the simple.txt file and store the data read in some kind of data container, for instance a list of lists or a dict. 
#    All `*` characters are to be regarded as unknown value.
# 2. Write a method for assessing if the Sudoku stored fulfills the objective stated above. This is needed going forward, so that 
#    we can see if a change we introduce is allowed.
# 3. Write the solver and solve the Sudoku (this is the hard part)
# 4. Write a method to compare two Sudokus with each other and see if they are identical.
# 5. Read the simple_solution.txt file and compare the solved Sudoku with the solution and verify that it is correct.

import pprint

# Reading the file
with open('simple.txt', mode='rt') as f:
    raw_data = f.readlines()

# Parsing it to data structures.
sudoku = []
for row in raw_data:
    this_row = []
    for char in row.strip():
        if char.isdigit():
            this_row.append(int(char))
        else:
            this_row.append(None)
    sudoku.append(this_row)

# Defining getter methods for rows, columns and boxes
def get_row_values(sudoku, row_nbr):
    this_row = []
    for value in sudoku[row_nbr]:
        if value is not None:
            this_row.append(value)
    return this_row

def get_column_values(sudoku, column_nbr):
    this_column = []
    for row in sudoku:
        if row[column_nbr] is not None:
            this_column.append(row[column_nbr])
    return this_column

def get_box_values(sudoku, box_row_nbr, box_column_nbr):
    this_box = []
    for row_nbr in range(box_row_nbr * 3, box_row_nbr * 3 + 3):
        for col_nbr in range(box_column_nbr * 3, box_column_nbr * 3 + 3):
            if sudoku[row_nbr][col_nbr] is not None:
                this_box.append(sudoku[row_nbr][col_nbr])
    return this_box

# Finding out what values are possible to insert into the first cell.
possible = {1,2,3,4,5,6,7,8,9}
possible = possible.difference(get_row_values(sudoku,0))
possible = possible.difference(get_column_values(sudoku, 0))
possible = possible.difference(get_box_values(sudoku, 0, 0))

sudokuclass.py

from pprint import pprint

class Sudoku:
    def __init__(self, file_path):
        # Reading the file
        with open(file_path, mode='rt') as f:
            raw_data = f.readlines()

        # Parsing it to data structures.
        sudoku = []
        for row in raw_data:
            this_row = []
            for char in row.strip():
                if char.isdigit():
                    this_row.append(int(char))
                else:
                    this_row.append(None)
            sudoku.append(this_row)
   
        self.sudoku = sudoku

    def solve(self):
        is_solved = False
        while not is_solved:
            has_found_something_to_change = False
            possible_values = self.get_possibles_dict()
            for (row_nbr, col_nbr) in possible_values:
                if len(possible_values[(row_nbr, col_nbr)]) == 1:
                    self.sudoku[row_nbr][col_nbr] = possible_values[(row_nbr, col_nbr)].pop()
                    has_found_something_to_change = True
            is_solved = self.is_sudoku_solved()
            
            if not has_found_something_to_change:
                break
        
        pprint(self.sudoku)

    def is_sudoku_solved(self):
        for row_nbr in range(len(self.sudoku)):
            for col_nbr in range(len(self.sudoku)):
                if self.sudoku[row_nbr][col_nbr] is None:
                    return False
        return True

    def get_possibles_dict(self):
        """
        {(1,2): {1,6}, ...}
        """
        possibles_dict = dict() 
        for row_nbr in range(len(self.sudoku)):
            for col_nbr in range(len(self.sudoku)):
                if self.sudoku[row_nbr][col_nbr] is not None:
                    continue
                possible = {1,2,3,4,5,6,7,8,9}
                possible = possible.difference(self.get_row_values(row_nbr))
                possible = possible.difference(self.get_column_values(col_nbr))
                possible = possible.difference(self.get_box_values(row_nbr // 3, col_nbr // 3))
                possibles_dict[(row_nbr, col_nbr)] = possible
        return possibles_dict

    def get_row_values(self, row_nbr):
        this_row = []
        for value in self.sudoku[row_nbr]:
            if value is not None:
                this_row.append(value)
        return this_row

    def get_column_values(self, column_nbr):
        this_column = []
        for row in self.sudoku:
            if row[column_nbr] is not None:
                this_column.append(row[column_nbr])
        return this_column

    def get_box_values(self, box_row_nbr, box_column_nbr):
        this_box = []
        for row_nbr in range(box_row_nbr * 3, box_row_nbr * 3 + 3):
            for col_nbr in range(box_column_nbr * 3, box_column_nbr * 3 + 3):
                if self.sudoku[row_nbr][col_nbr] is not None:
                    this_box.append(self.sudoku[row_nbr][col_nbr])
        return this_box


s = Sudoku('medium.txt')
s.solve()

sudokuclass_with_brute_force.py

from pprint import pprint
from copy import deepcopy
import time
from dancing_links import DancingLinksSolver

class Sudoku:
    def __init__(self, file_path_or_sudoku):
        if isinstance(file_path_or_sudoku, list):
            self.sudoku = file_path_or_sudoku
        else:
            # Reading the file
            with open(file_path_or_sudoku, mode='rt') as f:
                raw_data = f.readlines()

            # Parsing it to data structures.
            sudoku = []
            for row in raw_data:
                this_row = []
                for char in row.strip():
                    if char.isdigit():
                        this_row.append(int(char))
                    else:
                        this_row.append(None)
                sudoku.append(this_row)
    
            self.sudoku = sudoku

    def solve(self):

        is_solved = False
        while not is_solved:
            self.is_sudoku_valid()

            has_found_something_to_change = False
            possible_values = self.get_possibles_dict()
            change_1 = self.find_naked_singles(possible_values)
            possible_values = self.get_possibles_dict()
            change_2 = self.find_hidden_singles(possible_values)
            has_found_something_to_change = change_1 or change_2

            if self.is_sudoku_solved():
                is_solved = True
            elif not has_found_something_to_change:
                # Slow Brute force
                # self.brute_force()
                # is_solved = True
                
                # A very efficient "Brute Force" solution for Sudokus:
                # https://en.wikipedia.org/wiki/Dancing_Links
                # solver = DancingLinksSolver(deepcopy(self.sudoku))
                # self.sudoku = next(solver.solve())
                # is_solved = True
                
                # If no Brute force is allowed.
                raise Exception("I cannot solve this Sudoku with the methods I have at my disposal!")
            else:
                continue

    def brute_force(self):
        possible_values = self.get_possibles_dict()
        for (row_nbr, col_nbr) in possible_values:
            for possible_value in possible_values[(row_nbr, col_nbr)]:
                try:
                    attempt = deepcopy(self.sudoku)
                    attempt[row_nbr][col_nbr] = possible_value
                    s = Sudoku(attempt)
                    s.solve()
                except:
                    pass
                else:
                    if s.is_sudoku_solved() and s.is_sudoku_valid():
                        self.sudoku = s.sudoku
                        return
        raise Exception("Not solvable with Brute Force!")

    def find_naked_singles(self, possible_values):
        has_found_something_to_change = False
        for (row_nbr, col_nbr) in possible_values:
            if len(possible_values[(row_nbr, col_nbr)]) == 1:
                self.sudoku[row_nbr][col_nbr] = possible_values[(row_nbr, col_nbr)].pop()
                has_found_something_to_change = True
        return has_found_something_to_change

    def find_hidden_singles(self, possible_values):
        has_changed_something = False
        
        # This is the Hidden Singles in rows part
        for row_nbr in range(len(self.sudoku)):
            this_rows_possibles = []
            for (possibles_row_nbr, possibles_col_nbr), possibles in possible_values.items():
                if possibles_row_nbr == row_nbr:
                    this_rows_possibles.append(((possibles_row_nbr, possibles_col_nbr), possibles))
            for value in range(1, 10):
                has_nbr_in_it = []
                for (possibles_row_nbr, possibles_col_nbr), possibles in this_rows_possibles:
                    has_nbr_in_it.append(value in possibles)
                if sum(has_nbr_in_it) == 1:
                    for index, bool_value in enumerate(has_nbr_in_it):
                        if bool_value:
                            (row_nbr_to_set, col_nbr_to_set), _ = this_rows_possibles[index]
                            self.sudoku[row_nbr_to_set][col_nbr_to_set] = value
                            has_changed_something = True
                            break
         
        # This is the Hidden Singles in columns part
        
         
        # This is the Hidden Singles in boxes part
        
        return has_changed_something

    def is_sudoku_valid(self):
        for row_nbr in range(len(self.sudoku)):
            row_values = self.get_row_values(row_nbr)
            if len(row_values) != len(set(row_values)):
                raise Exception("Sudoku is invalid")
        
        for col_nbr in range(len(self.sudoku)):
            col_values = self.get_column_values(col_nbr)
            if len(col_values) != len(set(col_values)):
                raise Exception("Sudoku is invalid")
        
        for box_row_nbr in range(3):
            for box_col_nbr in range(3):
                box_values = self.get_box_values(box_row_nbr, box_col_nbr)
                if len(box_values) != len(set(box_values)):
                    raise Exception("Sudoku is invalid")
        
        return True

    def is_sudoku_solved(self):
        for row_nbr in range(len(self.sudoku)):
            for col_nbr in range(len(self.sudoku)):
                if self.sudoku[row_nbr][col_nbr] is None:
                    return False
        return True

    def get_possibles_dict(self):
        """
        {(1,2): {1,6}, ...}
        """
        possibles_dict = dict() 
        for row_nbr in range(len(self.sudoku)):
            for col_nbr in range(len(self.sudoku)):
                if self.sudoku[row_nbr][col_nbr] is not None:
                    continue
                possible = {1,2,3,4,5,6,7,8,9}
                possible = possible.difference(self.get_row_values(row_nbr))
                possible = possible.difference(self.get_column_values(col_nbr))
                possible = possible.difference(self.get_box_values(row_nbr // 3, col_nbr // 3))
                if len(possible) == 0:
                    raise Exception("There are no more possibilities for this cell.")
                possibles_dict[(row_nbr, col_nbr)] = possible
        
        possibles_dict = self.filter_on_naked_pairs(possibles_dict)

        return possibles_dict

    def filter_on_naked_pairs(self, possibles_dict):
        # Do the Naked Pairs filtering
        return possibles_dict

    def get_row_values(self, row_nbr):
        this_row = []
        for value in self.sudoku[row_nbr]:
            if value is not None:
                this_row.append(value)
        return this_row

    def get_column_values(self, column_nbr):
        this_column = []
        for row in self.sudoku:
            if row[column_nbr] is not None:
                this_column.append(row[column_nbr])
        return this_column

    def get_box_values(self, box_row_nbr, box_column_nbr):
        this_box = []
        for row_nbr in range(box_row_nbr * 3, box_row_nbr * 3 + 3):
            for col_nbr in range(box_column_nbr * 3, box_column_nbr * 3 + 3):
                if self.sudoku[row_nbr][col_nbr] is not None:
                    this_box.append(self.sudoku[row_nbr][col_nbr])
        return this_box


s = Sudoku('hard.txt')
t = time.time()
s.solve()
print(f"Solving took {time.time() - t} seconds.")
pprint(s.sudoku)
solution = Sudoku('hard_solution.txt')
print(s.sudoku == solution.sudoku)

very_hard.txt

***4*****
**9******
*3**7****
***7****8
****5*32*
4**86***5
5*3****8*
7983**4**
**6**9***

very_hard_solution.txt

652431897
179628534
834975261
365792148
987154326
421863975
513247689
798316452
246589713