## (C#) Sudoku board validation algorithm. It is already fast on my machine and I wonder how I can make it significantly faster, if at all (for fun)

I tested this algorithm on 9×9 boards and on average, if the board passed to the function is a (valid) solution, it takes 0.13-0.14 seconds for 1 million executions on my machine. I ran my code in Release mode in Visual Studio and timed it using `Stopwatch`. I found the idea to use summing of all digits in rows, columns and square cells from another StackOverflow post on suggestions for making a sudoku validator. Note that I gave my code capabilities to work with perfect squares (perfect square is assumed in code) for the board size, where the size is assumed to be the same in all dimensions. I am also planning to build a sudoku solver in the near future.

The sudoku board validating function:

``````public static bool IsValidSudokuBoard(int()() board)
{
int size = board.Length, cellSize = (int)Math.Sqrt(size), sumOfAllNums = (int)SumAllUpTo(size);
for (int row = 0; row < size; row++)
if (Sum(board(row)) != sumOfAllNums)
return false;
for (int column = 0; column < size; column++)
{
int columnSum = 0;
for (int row = 0; row < size; row++)
columnSum += board(row)(column);
if (columnSum != sumOfAllNums)
return false;
}
for (int row = 0; row < size; row += cellSize)
for (int column = 0; column < size; column += cellSize)
{
int cellSum = 0;
for (int rowOffset = 0; rowOffset < cellSize; rowOffset++)
for (int columnOffset = 0; columnOffset < cellSize; columnOffset++)
cellSum += board(row + rowOffset)(column + columnOffset);
if (cellSum != sumOfAllNums)
return false;
}
return true;
}
``````

Where `SumAllUpTo` is defined as follows:

``````public static double SumAllUpTo(double end, double start = 0d)
=> end * Math.Floor((end + 1d) / 2d) - ((start == 0d) ? 0d : SumAllUpTo(start));
``````

And `Sum` is defined as follows:

``````public static int Sum(this int() array)
{
int result = 0;
for (int x = 0; x < array.Length; x++)
result += array(x);
return result;
}
``````

## javascript – Sudoku Solver with hashmaps

is there a way to change the board using hashmaps?
There’s this project I have where I have to implement both recursion to solve the board which is already done and solve the board but I need hashmaps to make the board and I’m not sure how to do so.
If anyone can make it and show me it that would be great.

``````    public static int()() GRID_TO_SOLVE = {
{9,0,0,1,0,0,0,0,5},
{0,0,5,0,9,0,2,0,1},
{8,0,0,0,4,0,0,0,0},
{0,0,0,0,8,0,0,0,0},
{0,0,0,7,0,0,0,0,0},
{0,0,0,0,2,6,0,0,9},
{2,0,0,3,0,0,0,0,6},
{0,0,0,2,0,0,9,0,0},
{0,0,1,9,0,4,5,7,0},
};

private int()() board;
public static final int EMPTY = 0;
public static final int SIZE = 9;

public Sudoku(int()() board) {
this.board = new int(SIZE)(SIZE);

for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
this.board(i)(j) = board(i)(j);
}
}
}

private boolean isInRow(int row, int number) {
for (int i = 0; i < SIZE; i++)
if (board(row)(i) == number)
return true;

return false;
}

private boolean isInCol(int col, int number) {
for (int i = 0; i < SIZE; i++)
if (board(i)(col) == number)
return true;

return false;
}

private boolean isInBox(int row, int col, int number) {
int r = row - row % 3;
int c = col - col % 3;

for (int i = r; i < r + 3; i++)
for (int j = c; j < c + 3; j++)
if (board(i)(j) == number)
return true;

return false;
}

private boolean isOk(int row, int col, int number) {
return !isInRow(row, number)  &&  !isInCol(col, number)  &&  !isInBox(row, col, number);
}

public boolean solve() {
for (int row = 0; row < SIZE; row++) {
for (int col = 0; col < SIZE; col++) {
if (board(row)(col) == EMPTY) {
for (int number = 1; number <= SIZE; number++) {
if (isOk(row, col, number)) {
board(row)(col) = number;

if (solve()) {
return true;
} else {
board(row)(col) = EMPTY;
}
}
}

return false;
}
}
}

return true;
}

public void display() {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
System.out.print(" " + board(i)(j));
}

System.out.println();
}

System.out.println();
}

public static void main(String() args) {
Sudoku sudoku = new Sudoku(GRID_TO_SOLVE);
System.out.println("Sudoku Grid to Solve");
sudoku.display();

if (sudoku.solve()) {
System.out.println("Solved Grid");
sudoku.display();
} else {
System.out.println("No Solution");
}
}

}
``````

## Sudoku Graph in Julia – Code Review Stack Exchange

I’m building a graph coloring sudoku solver in Julia, so the first thing i’m tackling is the graph implementation. I have the bare structure completed, meaning I can create the graph with all of the right edges.

In terms of efficiency, it’s currently at

``````@timev s = SudokuGraph(3);

> 0.001573 seconds (16.05 k allocations: 1013.641 KiB)
> elapsed time (ns): 1573000
> bytes allocated:   1037968
> pool allocs:       16050
> non-pool GC allocs:1
> malloc() calls:    3
> realloc() calls:   1
``````

But to be honest I’m not sure if this is good or bad.

After the initial writing and refactoring, this is what it looks like. I’d appreciate tips on making it more idiomatic/proper Julia or efficient.

(Note, in `set_cell!` I changed `//` to `/` for the sake of not breaking the syntax highlighting here)

``````#Pkg.add("Combinatorics")
using Combinatorics

mutable struct Node
row::Int
col::Int
cell::Int
value::Int

function Node(coords::Tuple{Int,Int})
row, col = coords
return new(row, col, 0, 0)
end
end

function set_cell!(node::Node, size::Int)
col = node.col - 1
row = node.row - 1
node.cell = 1 + floor(((col / size) + row) - (row % size))
end

function get_coordinates(node::Node)::Tuple{Int,Int,Int}
return (node.row, node.col, node.cell)
end

function are_adjacent(nodes::Tuple{Node,Node})::Bool
a, b = get_coordinates.(nodes)
return any(a .== b)
end

struct Edge
nodes::Tuple{Node,Node}

function Edge(nodes::Tuple{Node,Node})
return new(nodes)
end
end

function nodes_to_edges(nodes::Vector{Node})::Vector{Edge}
return Edge.(Tuple.(filter(are_adjacent, Tuple.(combinations(nodes, 2)))))
end

mutable struct SudokuGraph
nodes::Vector{Node}
edges::Vector{Edge}

function SudokuGraph(size::Int)
cols = size^2
space = Iterators.product(1:cols, 1:cols)
nodes = Node.(reshape((space...), cols^2))
set_cell!.(nodes, fill(size))
edges = nodes_to_edges(nodes)

return new(nodes, edges)
end
end
``````

Thank you!

## c – preciso criar um jogo em sudoku

Faça um programa na linguagem de programação C. Seu programa deve apresentar um tabuleiro de sudoku, e permitir que o usuário jogue nesse tabuleiro. O tabuleiro inicial deve ser lido de um arquivo, que contém 81 números entre 0 e 9, que são os valores de cada posição do tabuleiro. O valor 0 é usado para representar uma casa vazia. Caso o arquivo não exista, deve inicializar com um tabuleiro default (que pode ser vazio).

O programa deve ter um laço principal que consiste em:

apresenta o tabuleiro – caso o tabuleiro esteja completo e correto (fim do jogo), esse fato deve ser informado;

lê uma tecla do usuário. Essa tecla pode ser:

um dígito entre 1 e 9 – representa o início de uma jogada, descrita abaixo;

a letra ‘g’ – grava o estado atual do jogo; o programa pede o nome de um arquivo e grava o tabuleiro nesse arquivo;

a letra ‘l’ – ler um jogo salvo anteriormente; o programa pede o nome do arquivo e substitui o tabuleiro pelo conteúdo dessa arquivo (caso consiga ler o arquivo);

a letra ‘s’ – o usuário pede para sair do jogo; o programa pede confirmação.

volta à apresentação do tabuleiro

Uma jogada consiste em o usuário digitar 3 números: a linha, a coluna e o valor a colocar nessa posição. O programa deve avisar o usuário (e não aceitar a jogada), se algum desses valores for inválido (não tiver entre 1 e 9), se a posição escolhida não estiver vazia, ou se essa jogada levar a uma situação inválida do tabuleiro (pelas regras do sudoku).

Após cada jogada válida, o tabuleiro deve ser gravado no arquivo que foi lido no início do programa. Dessa forma, sempre que o programa começa, o usuário volta à mesma situação em que estava na última vez que jogou

eu comecei a fazer esse código só que meu professor não explicou como faz o resto, alguem me ajuda por favor

int main()
{
FILE *arq;
arq= fopen(“jogo”,”a”);
if (arq==NULL){
printf(“não foi possivel abrir”);
return 1;
}
int i,j,m(9)(9);
for(i=0; i<9; i++){
for(j=0; j<9; j++){

``````           fprintf(arq,"  ");

}
fprintf(arq,"n");
}

for(i=0; i<9; i++){
for(j=0; j<9; j++){
scanf("%d",&m(i)(j));
if(m(i)(j)>=10 || m(i)(j)==0 ){
printf("digite só números entre 1 e 9");
}
}
}

fclose(arq);

return 0;
``````

}

## beginner – Python Sudoku Solver – Problems with the array

I’m learning Python, and want to create a sudoku solver without blindly copying one of the million examples already posted. I’ve created a user-entered array, but I think I’ve done something wrong with the return board part of the function, as none of the other functions are running. My code is:

``````def userboard():

board=()
for i in range(9):
print("With a space between the numbers and 0 for blank squares, enter each row beginning with row {}".format(i+1))
row=(int(x) for x in input().strip().split())
board.append(row)

print("")
print("Puzzle to be solved:")
for i in board:
print("")
for j in i:
print(j, end="  ")
print()
print("")

return board
``````

Which is supposed to be passed to a solve function, that calls upon two other functions, to identify the 0 values and verify the board is correct before it attempts the backtracking solve. I had some major issues trying to print the board with separating grid lines, but that’s not an essential issue.
Problem is, I keep getting a ‘board is not defined’ error.
The solve code is:

``````def solve_board(board):

find = identify_no_value(board)
if not find:
return True
else:
row, col = find

for i in range(1,10):
if board_validity(board, i, (row, col)):
board(row)(col) = i

if solve_board(board):
return True

board(row)(col) = 0
return False

def board_validity(board, insertion, position):

#row
for i in range(len(board(0))):
if board(position(0))(i) == insertion and position(1) != i:
return False
#column
for i in range(len(board)):
if board(i)(position(1)) == insertion and position(1) != i:
return False
#box
box_x = position(1) // 3
box_y = position(0) // 3

for i in range(box_y * 3, box_y*3 + 3):
for j in range(box_x * 3, box_x*3 + 3):
if board(i)(j) == num and (i,j) != position:
return False

def identify_no_value(board):

for i in range(len(board)):
for j in range(len(board(0))):
if board(i)(j) == 0:
return (i, j)
return None
``````

Can someone point out where I’ve gone wrong please? Thank you.

## c – Find Box number (Sudoku)

I have written a function in C to display each sudoku box. However I wasn’t able to find exactly the number of each box.
Here is the code:

``````void valid_Box(void)
{
size_t i = 0U, j = 0U, k = 0U, m = 0U;
size_t col = 0 , row = 0, G_SIZE = 9, BOX_SIZE = 3;

for (; i < G_SIZE; i+=3)
{
row = (i/3)*3;
printf("Box number %zdn",row+1);
for (j = 0; j < G_SIZE; j+=3)
{
col = (j/3)*3;
for (k = 0; k < BOX_SIZE; k++)
{
for (m = 0; m < BOX_SIZE; m++)
{
printf("(%d) ",Grid(row+k)(col+m));
}
putchar('t');
}
puts("");
}
puts("");
}
return;
}
``````

And here is the output:

``````Box number 1
(1) (0) (5)     (0) (0) (0)     (0) (0) (0)
(0) (2) (0)     (0) (0) (0)     (0) (0) (0)
(0) (0) (2)     (0) (0) (0)     (2) (0) (0)

Box number 4
(0) (0) (0)     (0) (8) (0)     (0) (0) (8)
(0) (0) (0)     (0) (0) (0)     (0) (0) (0)
(0) (0) (0)     (0) (0) (0)     (0) (0) (0)

Box number 7
(0) (0) (0)     (0) (0) (0)     (0) (0) (0)
(0) (0) (0)     (0) (0) (0)     (0) (0) (0)
(0) (0) (0)     (0) (0) (0)     (0) (0) (0)
``````

The goal to display each box’s number before printing the box, but I can’t figure out a way.Any hints?

## python – Leetcode valid sudoku

Link here

I’ll include a solution in Python and C++ and you can review one. I’m mostly interested in reviewing the C++ code which is a thing I recently started learning; those who don’t know C++ can review the Python code. Both solutions share similar logic, so the review will apply to any.

## Problem statement

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

• Each row must contain the digits 1-9 without repetition. Each column
• must contain the digits 1-9 without repetition. Each of the nine 3 x
• 3 sub-boxes of the grid must contain the digits 1-9 without
repetition.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.

Example 1:

``````Input: board =
(("5","3",".",".","7",".",".",".",".")
,("6",".",".","1","9","5",".",".",".")
,(".","9","8",".",".",".",".","6",".")
,("8",".",".",".","6",".",".",".","3")
,("4",".",".","8",".","3",".",".","1")
,("7",".",".",".","2",".",".",".","6")
,(".","6",".",".",".",".","2","8",".")
,(".",".",".","4","1","9",".",".","5")
,(".",".",".",".","8",".",".","7","9"))
Output: true
``````

Example 2:

``````Input: board =
(("8","3",".",".","7",".",".",".",".")
,("6",".",".","1","9","5",".",".",".")
,(".","9","8",".",".",".",".","6",".")
,("8",".",".",".","6",".",".",".","3")
,("4",".",".","8",".","3",".",".","1")
,("7",".",".",".","2",".",".",".","6")
,(".","6",".",".",".",".","2","8",".")
,(".",".",".","4","1","9",".",".","5")
,(".",".",".",".","8",".",".","7","9"))
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
``````

`valid_sudoku.py`

``````def is_valid(board, empty_value='.', b_size=3):
seen = set()
size = b_size * b_size
for row in range(size):
for col in range(size):
if (value := board(row)(col)) == empty_value:
continue
r = f'0{row}{value}'
c = f'1{col}{value}'
b = f'2{row // b_size}{col // b_size}{value}'
if r in seen or c in seen or b in seen:
return False
seen.update({r, c, b})
return True

if __name__ == '__main__':
g = (
("5", "3", ".", ".", "7", "5", ".", ".", "."),
("6", ".", ".", "1", "9", "5", ".", ".", "."),
(".", "9", "8", ".", ".", ".", ".", "6", "."),
("8", ".", ".", ".", "6", ".", ".", ".", "3"),
("4", ".", ".", "8", ".", "3", ".", ".", "1"),
("7", ".", ".", ".", "2", ".", ".", ".", "6"),
(".", "6", ".", ".", ".", ".", "2", "8", "."),
(".", ".", ".", "4", "1", "9", ".", ".", "5"),
(".", ".", ".", ".", "8", ".", ".", "7", "9"),
)
print(is_valid(g))
``````

Stats:

``````Runtime: 92 ms, faster than 81.70% of Python3 online submissions for Valid Sudoku.
Memory Usage: 14.1 MB, less than 73.95% of Python3 online submissions for Valid Sudoku.
``````

Here’s an alternative solution using numpy, it’s shorter and more readable but slower:

``````import numpy as np

def is_valid(board, size=3, empty_value='.'):
board = np.array(board)
blocks = board.reshape(4 * (size)).transpose(0, 2, 1, 3).reshape(2 * (size * size))
for grid in (board, board.T, blocks):
for line in grid:
non_empty = line(line != empty_value)
if not len(non_empty) == len(set(non_empty)):
return False
return True
``````

Stats:

``````Runtime: 172 ms, faster than 5.19% of Python3 online submissions for Valid Sudoku.
Memory Usage: 30.2 MB, less than 11.10% of Python3 online submissions for Valid Sudoku.
``````

`valid_sudoku.h`

``````#ifndef LEETCODE_VALID_SUDOKU_H
#define LEETCODE_VALID_SUDOKU_H

#include <string_view>
#include <unordered_set>

bool sudoku_check_update(const size_t &row, const size_t &col, const char &value,
const int &block_size,
std::unordered_set<std::string_view> &seen);

bool sudoku_check(const std::vector<std::vector<char>> &board,
const char &empty_value = '.');

void test1();

#endif //LEETCODE_VALID_SUDOKU_H
``````

`valid_sudoku.cpp`

``````#include <iostream>
#include <vector>
#include <string_view>
#include <cmath>
#include <unordered_set>

bool sudoku_check_update(const size_t &row, const size_t &col, const char &value,
const int &block_size,
std::unordered_set<std::string_view> &seen) {
std::string_view r, c, b;
r = "0-" + std::to_string(row) + value;
c = "1-" + std::to_string(col) + value;
b = "2-" + std::to_string(row / block_size) + std::to_string(col / block_size) +
value;
for (const auto &seen_id: {r, c, b}) {
if (seen.find(seen_id) != seen.end())
return false;
seen.insert(seen_id);
}
return true;
}

bool sudoku_check(const std::vector<std::vector<char>> &board,
const char &empty_value = '.') {
std::unordered_set<std::string_view> seen;
const auto row_size = board.size();
const int block_size = std::sqrt(row_size);
for (size_t row = 0; row < row_size; ++row) {
for (size_t col = 0; col < row_size; ++col) {
auto value = board(row)(col);
if (value == empty_value)
continue;
if (!sudoku_check_update(row, col, value, block_size, seen))
return false;
}
}
return true;
}

void test1() {
std::vector<std::vector<char>> v = {
{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
{'.', '.', '.', '.', '8', '.', '.', '7', '9'}
};
std::cout << sudoku_check(v);
}
``````

Stats:

``````Runtime: 48 ms, faster than 17.98% of C++ online submissions for Valid Sudoku.
Memory Usage: 20.4 MB, less than 22.55% of C++ online submissions for Valid Sudoku.
``````

## java – Solving a sudoku with backtracking

I wrote this java Class to solve a standard 9×9 sudoku board.
It uses backtracking to solve each field of the board.

I am really interested in feedback for the “isValid” and “isBlockValid” Methods, because they are redundant.

Here is my code on github.

Also here is the code:

``````public class SudokuSolver {

private boolean solve(int()() board, int counter){

int col = (int) counter / board.length;
int row = counter % board.length;

if (col >= board.length){
printBoard(board);
return true;
}

if (board(row)(col) == 0) {

for (int n = 1; n <= board.length; n++) {

if (isValid(n,row,col, board)){
board(row)(col) = n;

if (solve(board,counter+1)){
return true;
}

}
board(row)(col) = 0;

}
}else{
if (solve(board,counter+1)){
return true;
}
}

return false;
}

public void startSolving(int()() board){
if(!solve(board, 0)){
System.out.println("no solution");
}
}

private boolean isValid(int n, int row, int col, int()() board){

int i;
int j;

for (i = 0; i < board.length; i++) {
if(board(row)(i) == n){
return false;
}
}

for (i = 0; i < board.length; i++) {
if(board(i)(col) == n){
return false;
}
}

//check if block is valid - do not know any other way for solving this

// check block 1
if (row >= 0 && col >= 0 && row <= 2 && col <= 2){
if(!isBlockValid(n, row, col, board, 0, 2, 0, 2)){
return false;
}
}

// check block 2
if (row >= 0 && col >= 3 && row <= 2 && col <= 5){
if(!isBlockValid(n, row, col, board, 0, 2, 3, 5)){
return false;
}
}

// check block 3
if (row >= 0 && col >= 6 && row <= 2 && col <= 8){
if(!isBlockValid(n, row, col, board, 0, 2, 6, 8)){
return false;
}
}

// check block 4
if (row >= 3 && col >= 0 && row <= 5 && col <= 2){
if(!isBlockValid(n, row, col, board, 3, 5, 0, 2)){
return false;
}
}

// check block 5
if (row >= 3 && col >= 3 && row <= 5 && col <= 5){
if(!isBlockValid(n, row, col, board, 3, 5, 3, 5)){
return false;
}
}

// check block 6
if (row >= 3 && col >= 6 && row <= 5 && col <= 8){
if(!isBlockValid(n, row, col, board, 3, 5, 6, 8)){
return false;
}
}

// check block 7
if (row >= 6 && col >= 0 && row <= 8 && col <= 2){
if(!isBlockValid(n, row, col, board, 6, 8, 0, 2)){
return false;
}
}

// check block 8
if (row >= 6 && col >= 3 && row <= 8 && col <= 5){
if(!isBlockValid(n, row, col, board, 6, 8, 3, 5)){
return false;
}
}

// check block 9
if (row >= 6 && col >= 6 && row <= 8 && col <= 8){
if(!isBlockValid(n, row, col, board, 6, 8, 6, 8)){
return false;
}
}

return true;
}

private boolean isBlockValid(int n, int row, int col, int()() board, int starti, int stopi, int startj, int stopj){

for (int i = starti; i <= stopi; i++) {

for (int j = startj; j <= stopj; j++) {

if (board(i)(j) == n) {
return false;
}
}
}

return true;
}

private void printBoard(int()() board){

System.out.println();

for (int() row : board){
System.out.print("|");
for (int col : row){
System.out.print(col);
System.out.print("|");
}
System.out.println();
}
System.out.println();
}

public static void main(String() args) {

int()() board =
{{2,0,5,0,0,0,0,0,0},
{3,0,8,6,0,0,9,0,0},
{0,0,0,1,0,0,4,0,0},
{0,0,0,0,5,0,0,1,0},
{0,0,0,0,9,0,0,2,0},
{8,7,0,0,2,0,0,0,0},
{0,0,0,0,8,9,0,0,3},
{0,0,6,0,0,3,0,0,5},
{5,0,4,0,0,0,0,0,1}};

SudokuSolver sudokuSolver = new SudokuSolver();
sudokuSolver.startSolving(board);
}
}

$$```$$
``````

## Recursive Sudoku solver using Python

A Sudoku solver that works recursively. I’d appreciate your comments about coding style, structure and how to improve it. Thank you very much for your time.

Code structure

The Solver works by accepting a string of 81 digits for the Sudoku puzzle input. Zeros are taken as empty cells. It parses it into a 9×9 Numpy array.

The `get_candidates` function creates lists of possible digits to fill each cell following Sudoku’s rules (no repeating 1-9 digit along rows, columns and 3×3 sub-grids).

The main solver function is `solve`. First, it discards wrong candidates with the `filter-candidates` function. “Wrong candidates” are those that when filled to a empty cell, led to another cell having no more candidates elsewhere on the Sudoku grid.

After filtering candidates, `fill_singles` is called to fill empty cells that have only one remaining candidate. If this process leads to a completely filled Sudoku grid, it’s returned as a solution. There’s a clause to return `None` which is used to backtrack changes by the `make_guess` function. This function will fill the next empty cell with the least quantity of candidates with one of its candidates, a “guess” value. It then recursively calls `solve` to either find a solution or reach a no-solution grid (in which case `solve` returns `None` and the last guess changes are reverted).

``````from copy import deepcopy
import numpy as np

def create_grid(puzzle_str: str) -> np.ndarray:
"""Create a 9x9 Sudoku grid from a string of digits"""

# Deleting whitespaces and newlines (n)
lines = puzzle_str.replace(' ','').replace('n','')
digits = list(map(int, lines))
# Turning it to a 9x9 numpy array
grid = np.array(digits).reshape(9,9)
return grid

def get_subgrids(grid: np.ndarray) -> np.ndarray:
"""Divide the input grid into 9 3x3 sub-grids"""

subgrids = ()
for box_i in range(3):
for box_j in range(3):
subgrid = ()
for i in range(3):
for j in range(3):
subgrid.append(grid(3*box_i + i)(3*box_j + j))
subgrids.append(subgrid)
return np.array(subgrids)

def get_candidates(grid : np.ndarray) -> list:
"""Get a list of candidates to fill empty cells of the input grid"""

def subgrid_index(i, j):
return (i//3) * 3 + j // 3

subgrids = get_subgrids(grid)
grid_candidates = ()
for i in range(9):
row_candidates = ()
for j in range(9):
# Row, column and subgrid digits
row = set(grid(i))
col = set(grid(:, j))
sub = set(subgrids(subgrid_index(i, j)))
common = row | col | sub
candidates = set(range(10)) - common
# If the case is filled take its value as the only candidate
if not grid(i)(j):
row_candidates.append(list(candidates))
else:
row_candidates.append((grid(i)(j)))
grid_candidates.append(row_candidates)
return grid_candidates

def is_valid_grid(grid : np.ndarray) -> bool:
"""Verify the input grid has a possible solution"""

candidates = get_candidates(grid)
for i in range(9):
for j in range(9):
if len(candidates(i)(j)) == 0:
return False
return True

def is_solution(grid : np.ndarray) -> bool:
"""Verify if the input grid is a solution"""

if np.all(np.sum(grid, axis=1) == 45) and
np.all(np.sum(grid, axis=0) == 45) and
np.all(np.sum(get_subgrids(grid), axis=1) == 45):
return True
return False

def filter_candidates(grid : np.ndarray) -> list:
"""Filter input grid's list of candidates"""
test_grid = grid.copy()
candidates = get_candidates(grid)
filtered_candidates = deepcopy(candidates)
for i in range(9):
for j in range(9):
# Check for empty cells
if grid(i)(j) == 0:
for candidate in candidates(i)(j):
# Use test candidate
test_grid(i)(j) = candidate
# Remove candidate if it produces an invalid grid
if not is_valid_grid(fill_singles(test_grid)):
filtered_candidates(i)(j).remove(candidate)
# Revert changes
test_grid(i)(j) = 0
return filtered_candidates

def merge(candidates_1 : list, candidates_2 : list) -> list:
"""Take shortest candidate list from inputs for each cell"""

candidates_min = ()
for i in range(9):
row = ()
for j in range(9):
if len(candidates_1(i)(j)) < len(candidates_2(i)(j)):
row.append(candidates_1(i)(j)(:))
else:
row.append(candidates_2(i)(j)(:))
candidates_min.append(row)
return candidates_min

def fill_singles(grid : np.ndarray, candidates=None) -> np.ndarray:
"""Fill input grid's cells with single candidates"""

grid = grid.copy()
if not candidates:
candidates = get_candidates(grid)
any_fill = True
while any_fill:
any_fill = False
for i in range(9):
for j in range(9):
if len(candidates(i)(j)) == 1 and grid(i)(j) == 0:
grid(i)(j) = candidates(i)(j)(0)
candidates = merge(get_candidates(grid), candidates)
any_fill = True
return grid

def make_guess(grid : np.ndarray, candidates=None) -> np.ndarray:
"""Fill next empty cell with least candidates with first candidate"""

grid = grid.copy()
if not candidates:
candidates = get_candidates(grid)
# Getting the shortest number of candidates > 1:
min_len = sorted(list(set(map(
len, np.array(candidates).reshape(1,81)(0)))))(1)
for i in range(9):
for j in range(9):
if len(candidates(i)(j)) == min_len:
for guess in candidates(i)(j):
grid(i)(j) = guess
solution = solve(grid)
if solution is not None:
return solution
# Discarding a wrong guess
grid(i)(j) = 0

def solve(grid : np.ndarray) -> np.ndarray:
"""Recursively find a solution filtering candidates and guessing values"""

candidates = filter_candidates(grid)
grid = fill_singles(grid, candidates)
if is_solution(grid):
return grid
if not is_valid_grid(grid):
return None
return make_guess(grid, candidates)

# # Example usage

# puzzle = """100920000
#             524010000
#             000000070
#             050008102
#             000000000
#             402700090
#             060000000
#             000030945
#             000071006"""

# grid = create_grid(puzzle)
# solve(grid)
$$```$$
``````

## algorithms – How does Backtracking work in this Sudoku solver? How is the next “path” chosen

I have this solve function.

From my understanding the backtracking part of this algorithm is the line after the recursive solve().
I would think that it would leave 0’s in the final board.
Say if I get to a spot on the board where it needs to backtrack, wont it assign `grid(y)(x) = 0` then advance to the next possible value `n`? How is the next “path” (next `n` value) chosen when backtracking?

``````   def solve():
for y in range(9) :
for x in range(9) :
if grid(y)(x) == 0 :
for n in range(1,10) :
if possible(y,x,n) :
grid(y)(x) = n
solve()
grid(y)(x) = 0
return
pprint(grid)
``````