Sudoku library

Library for generating and solving Sudoku puzzles.

The following functions are provided:

• sudoku_read(): Read a puzzle
• sudoku_print(puzzle): Print puzzle
• sudoku_print_errors(puzzle): Print rule-related errors of puzzle
• sudoku_print_empty(puzzle): Print the empty cells of puzzle
• sudoku_format_is_correct(puzzle): Show whether puzzle meets the required format
• sudoku_is_correct(puzzle): Check whether puzzle has issues (rules violation, empty cells)
• sudoku_solve(puzzle): Solve puzzle
• sudoku_generate(N): Generate puzzle that has N non empty cells
• sudoku_has_unique_choice_solution(puzzle): Show whether puzzle has a unique choice solution
• sudoku_set_value(puzzle, row, col, val): Set cell value
• sudoku_clear_value(puzzle, row, col): Clear cell value
• sudoku_set_choice(puzzle, row, col, val): Set val as cell choice
• sudoku_clear_choice(puzzle, row, col, val): Clear val from cell choices

Implementation

Sudokus are solved using a backtracking algorithm.

Compile

• Build the library (functions declared in sudoku.h):

make sudoku.o

• Build the UI that uses the library:

make sudoku-ui

Typical usage

• Read a sudoku from input_file and solve it:

./sudoku-ui < input_file

• Read a sudoku from input_file and check its correctness:

./sudoku-ui -c < input_file

• Read a sudoku from input_file and print it in a 9x9 grid:

./sudoku-ui -s < input_file

• Generate a solvable sudoku with 40 non-zero numbers:

./sudoku-ui -g 40

• Generate a solvable sudoku with 40 non-zero numbers and solve it:

./sudoku-ui -g 40 | ./sudoku-ui

Note: When the non-zero count is very low, it may not be possible to return a puzzle with a unique available choice at each step of the solution. Consequently, such puzzles may have multiple solutions. In such cases, the solver will provide only one of the possible solutions.

Puzzles

Puzzles folder contains a selection of unsolved puzzles.

Profiling

'sudoku-ui' has been tested for memory leaks with valgrind and AddressSanitizer.