# 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)[source]

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)[source]

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)[source]

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)[source]

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)[source]

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)[source]

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)[source]

Converts a sudoku into a string.

Paramètres

su – sudoku

Renvoie

string

source on GitHub