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 (i, j) \in \{0, 1, 2\}^2 (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