SUDOKU: INFERENCE (PYTHON)

Inference is the process of deriving a logical conclusion from a set of given facts. In the context of Sudoku, a player attempts to infer the correct values for empty fields given the content of the already filled fields. There are numerous inference rules that experienced Sudoku players use. Let us focus on the Singles strategy, which contains two separate rules.

1. The first one (let us refer to it as forward single) is the simple observation that if an empty field f has only one available option x, then f should contain x.

2. The second single rule (let us refer to it as backward single) is based on the fact that in every region of a Sudoku board (i.e., row, column, and subgrid) the solution needs to contain every number from 1 to n. From this we can derive the rule as: if within a given region the number x is available as option only in one field f of that region, then the solution contains x in field f (because it is the only field that can supply x).

It turns out that both rules in conjunction are enough to solve a lot of Sudoku boards and we can implement a decent partial Sudoku solver based on them.

Write a function inferred(board) that accepts as input a Sudoku board and returns as output a new Sudoku board that contains all values that can be inferred by repeated application of the two single rules. For example, for the big game board above the function would completely solve the board:

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

OUTPUT:

>>> inferred(board1) [[2, 1, 3, 4, 5, 6, 7, 8, 9],

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

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

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

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

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

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

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

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