sudoku_solver.c File Reference

Sudoku Solver using recursive implementation of brute-force algorithm. More...

#include <assert.h>
#include <inttypes.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

Include dependency graph for sudoku_solver.c:

Data Structures
struct	sudoku
	Structure to hold the matrix and dimensions. More...

Functions
bool	OKrow (const struct sudoku *a, int x, int y, int v)
	Check if x^th row is valid. More...
bool	OKcol (const struct sudoku *a, int x, int y, int v)
	Check if y^th column is valid. More...
bool	OKbox (const struct sudoku *a, int x, int y, int v)
	Check if a 3x3 box is valid. More...
bool	OK (const struct sudoku *a, int x, int y, int v)
	Check if element v is valid to place at (x,y) location. More...
void	print (const struct sudoku *a)
	Print the matrix to stdout. More...
bool	get_next_unknown (const struct sudoku *a, int *x, int *y)
	Find and get the location for next empty cell. More...
bool	solve (struct sudoku *a)
	Function to solve a partially filled sudoku matrix. More...
void	test ()
int	main ()
	Main function.

Detailed Description

Sudoku Solver using recursive implementation of brute-force algorithm.

Given an incomplete N*N Sudoku and asked to solve it using the following recursive algorithm:

1. Scan the Sudoku from left to right row-wise to search for an empty cell.
2. If there are no empty cells, print the Sudoku. Go to step 5.
3. In the empty cell, try putting numbers 1 to N while ensuring that no two numbers in a single row, column, or box are same. Go back to step 1.
4. Declare that the Sudoku is Invalid.
5. Exit.

Authors

Anuj Shah

Krishna Vedala