fun

sudoku-solver.py - A simple program that can solve any (solvable) sudoku puzzle.

Copyright 2016 Maarten 'Vngngdn' Vangeneugden

Licensed under the Apache License, Version 2.0 (the "License");

you may not use this file except in compliance with the License.

You may obtain a copy of the License at

    https://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software

distributed under the License is distributed on an "AS IS" BASIS,

WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

See the License for the specific language governing permissions and

limitations under the License.

"""

# I don't think I need to explain this, do I? Although I will explain how the

# program works:

# One is supposed to give an array of arrays, which will each contain a series

# of integer values in range [1,9]. Some of them may be 0, these will then stand

# for an empty value.

# This program's goal is to remove all 0's (blank spaces) and fill them so, that

# the sudoku is considered solved. After that, it prints the sudoku to the

# terminal.

# Prints the given sudoku to the terminal in a readable way:

def print_sudoku(sudoku):

    print(sudoku)

            pass

        print()  # Start a new line.

        """

# Given an empty sudoku, the solution is very simple.

def solve_empty_sudoku(sudoku): 

    n = 3

    for i in range(0, n*n):

        for j in range(0, n*n):

            sudoku[i][j] = (i*n + i/n + j) % (n*n) + 1;

    return sudoku

# Creates a table of 9x9 in the form of an array containing arrays.

def create_sudoku():

    x = []

    for i in range(0,9):

        x.append([0, 0, 0, 0, 0, 0, 0, 0, 0])

    return x

EMPTY = 0

# Checks if the given sudoku qualifies as a root solution.

def is_possible_root_solution(sudoku):

    root_solution = solve_empty_sudoku()

    for i in range(0, len(root_solution)):

        for j in range(0, len(root_solution[i])):

            if sudoku[i][j] != root_solution[i][j] and sudoku[i][j] != 0:

                return False

    # When here, all the sudoku can be filled as a root solution.

    return True

# Checks whether the given number already exists in the given array.

def exists_in_array(x, y, sudoku):

    return False

# Checks whether the number on the given location is unique in its column.

def exists_in_column(x, y, sudoku):

        if sudoku[x][i] == value and i != y and sudoku[x][i] != 0:

    return False

# Checks whether the number on the given location is unique in its (3x3) grid.

def exists_in_grid(x, y, sudoku):

    # We'll increment x and y by 1 in order to have some 1-indexed math:

    # The idea I'm going for now:

    # I'll first try to find out in which segment of the sudoku the value is in.

    # When I've found it, I trim the data to that segment, after I'll be

    # checking on that segment only.

    # Chart:

    """

    +-----+

    |A B C|

    |D E F|

    |G H I|

    +-----+

    """

    n = 3

    A = x%n

    B = y%n

    for i in range(0, n):

        for j in range(0, n):

            C = x - A + i

            D = y - B + j

            if sudoku[C][D] == value and (C != x and D != y):

                return True

    return False

def is_filled_sudoku(sudoku):

    for i in range(0, len(sudoku)):

        for j in range(0, len(sudoku[i])):

            if sudoku[i][j] == 0:

                return False

    return True

def find_first_empty_grid(sudoku):

    for i in range(0, len(sudoku)):

        for j in range(0, len(sudoku[i])):

            if sudoku[i][j] == 0:

                return i, j

def is_valid_assignment(x, y, value, sudoku):

    sudoku[x][y] = value

    if exists_in_column(x, y, sudoku):

    if exists_in_grid(x, y, sudoku):

    return True

# Makes a deep copy of the given sudoku, and returns that copy.

def make_copy(sudoku):

    newSudoku = []

    for array in sudoku:

        newSudoku.append(array.copy())

    return newSudoku

sudokuA = create_sudoku()

def recursive_solution(sudoku):

    if is_filled_sudoku(sudoku):

        return True  # The sudoku is solved.

    else:

        x, y = find_first_empty_grid(sudoku)

        print(str(x) + "-" + str(y))

            # We're going to fill in numbers from 1 to 9, to find a solution

            # that works.

            sudoku[x][y] = i

                oldSudoku = make_copy(sudoku)

                    sudoku = oldSudoku

                    return True

        return False

# MAIN

if recursive_solution(sudokuA):

    print_sudoku(sudokuA)

    print("Failed!")

    print_sudoku(sudokuA)