File Sudoku.h

↰ Parent directory (ADS/backtrack)

The Sudoku (reality check of section 16.3 and exercise 16.7), of size n^2 x n^2 with the numbers 1 , … , n^2, n = 3 the classic one: the squares are filled in order, each with the numbers that check() allows, no equal number on its row, its column and its block of n x n, and the search backtracks when a square has none.

Definition (ADS/backtrack/Sudoku.h)

Detailed Description

The cost is a constant for n = 3, a huge one, and superpolynomial in n. 0 marks an empty square.

The contracts [see File Contract.h]: check() needs a square of the grid and a value in [ 1 , n^2 ]; sudoku() a grid of n^2 x n^2 squares with values in [ 0 , n^2 ], those given consistent, and the solution is checked too (both at level 3). The operations are defined in Sudoku.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 16.3 and exercise 16.7, https://algoritmicamente.it/materiali/libro/capitoli/cap16.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/backtrack/impl/Sudoku.tpp

  • cstddef

  • vector

Namespaces

Functions

Typedefs