module special.sudoku

Short summary

module ensae_teaching_cs.special.sudoku

This file proposes a simple algorithm to solve a Sudoku. It finds the first possible solution.

source on GitHub

Functions

function	truncated documentation
chiffre_barre_carre	Look into every number in sub square i, j, if a number in it s[i][k] is not null,
chiffre_barre_colonne	Look into every number in column j, if the number in column k s[i][k] is not null,
chiffre_barre_ligne	Look into every number in line i, if the number in column k s[i][k] is not null,
meilleure_case	look over all empty place and pick the one with the least possible options
nombre_possible	tells for a particular position the list of possible number
resolution_sudoku	Solves the Sudoku.
sudoku2str	Converts a sudoku into a string.

Documentation

This file proposes a simple algorithm to solve a Sudoku. It finds the first possible solution.

source on GitHub

ensae_teaching_cs.special.sudoku.chiffre_barre_carre(s, r, i, j)

Look into every number in sub square i, j, if a number in it s[i][k] is not null,

Paramètres:

• s – current state of the sudoku

• r – array r[n] == 0 means number n+1 is already taken on this sub square

• i – sub square are indexed by (0 based)

• j – see parameter i

source on GitHub

ensae_teaching_cs.special.sudoku.chiffre_barre_colonne(s, r, j)

Look into every number in column j, if the number in column k s[i][k] is not null,

Paramètres:

• s – current state of the sudoku

• r – array r[n] == 0 means number n+1 is already taken on this column

• j – column index (0 based)

source on GitHub

ensae_teaching_cs.special.sudoku.chiffre_barre_ligne(s, r, i)

Look into every number in line i, if the number in column k s[i][k] is not null,

Paramètres:

• s – current state of the sudoku

• r – array r[n] == 0 means number n+1 is already taken on this line

• i – line index (0 based)

source on GitHub

ensae_teaching_cs.special.sudoku.meilleure_case(s)

look over all empty place and pick the one with the least possible options

Paramètres:

s – current state of the sudoku

Renvoie:

(i,j,r), (i,j) is the best position, r the list of possible numbers

source on GitHub

ensae_teaching_cs.special.sudoku.nombre_possible(s, i, j)

tells for a particular position the list of possible number

Paramètres:

• s – current state of the sudoku

• i – line index (0 based)

• j – column index (0 based)

Renvoie:

9-element array, 0: not possible, 1: possible at position (i, j)

source on GitHub

ensae_teaching_cs.special.sudoku.resolution_sudoku(s)

Solves the Sudoku.

Paramètres:

s – sudoku (0 for empty case)

Renvoie:

0 for impossible, 1 for possible, then s contains the solution

The algorithm is the following:

1. Find the position of a zero element (no number yet) with the smallest number of options

2. If there is at least one possible option, try the first one, go to step 1

3. If not, the Sudoku cannot be solved, go back to last list of multiple options and try the next one.

Example:

s = [[0, 0, 0, 3, 0, 0, 8, 0, 0],
     [0, 0, 7, 9, 0, 8, 0, 0, 5],
     [0, 0, 0, 2, 0, 4, 1, 0, 0],
     [0, 9, 0, 8, 1, 0, 0, 4, 7],
     [0, 4, 0, 0, 0, 0, 0, 0, 6],
     [0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 1, 0, 0, 0, 5, 0, 2, 0],
     [5, 3, 4, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 7, 0, 0, 0, 0, 0]]

resolution_sudoku(s)

for i in range(0, 9):
print(s[i])

source on GitHub

ensae_teaching_cs.special.sudoku.sudoku2str(su)

Converts a sudoku into a string.

Paramètres:

su – sudoku

Renvoie:

string

source on GitHub