Sudoku: Difference between revisions
Content deleted Content added
+Stata |
|||
Line 9,691:
=={{header|Stata}}==
In this implementation, a Sudoku is a 9x9 matrix, with either digits 1-9 or missing values. A cell is any element of a. A cell can be reference with indices i,j, or with a single index n between 1 and 81.
Three functions are defined:
* sudoku(a) will return 0 if there is no solution, 1 if there is '''at least''' one solution, and then a is modified in place with the solution found. This function builds several tables before calling the main "solver" function.
* solve(a,s,t,v,w) is made of two parts: first, all cells that can be filled without any assumption are considered known. Then, if not all cells are known, a cell with minimal number of choices is found, and a recursive call to solve is made with all possibilities in turn for this cell.
* push(a,s,t,v,w,n,z) is an auxiliary function, which basically push the value z in the nth cell of matrix a. Here n is a value between 1 and 81.
Fixed tables:
* t(n,.) is a row i,j,k: the cell n (1-81) has row index i, column index j, and square index k, where i, j, k are all in 1-9.
* s(n,.) is a row that contains the indices of the 20 "neighbors" of cell n: these are the cells in the same row, column or square.
Varying tables:
* v(n,z)=1 is the cell n may have the value z, otherwise 0. When a value z is added in the matrix, all neighboring cells are updated (they can't take the value z anymore)
* w(n)=1 if cell n is not yet known, otherwise 0.
The example grid given below is taken from [https://en.wikipedia.org/wiki/Sudoku_solving_algorithms Wikipedia]. It does not require any recursive call (it's entirely filled in the first step of ''solve''), as can be seen with additional ''printf'' in the code to follow the algorithm.
<lang stata>mata
function sudoku(a) {
Line 9,780 ⟶ 9,798:
a = 5,3,.,.,7,.,.,.,.\
sudoku(a)
|