-
Notifications
You must be signed in to change notification settings - Fork 0
/
solver_helpers.h
102 lines (93 loc) · 4.38 KB
/
solver_helpers.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#ifndef KS_SUDOKU_SOLVER_SOLVER_HELPERS
#define KS_SUDOKU_SOLVER_SOLVER_HELPERS
#include <sys/types.h>
#include <stddef.h>
#include "common.h"
#include "sudoku_solver.h"
/**
* Returns the "naked single" value for the given cell.
*/
unsigned find_naked_single(struct possible_entries possible_values[TABLE_ORDER_MAX][TABLE_ORDER_MAX],
size_t row, size_t col);
/*
* Update the possibilities of cells as a consequence of assignment of 'val' to the given cell.
*
* sudoku_table - the table containing the sudoku board
* possible_values - lookup table for possible values of different cells in the
* sudoku board.
* (row, col) - the cell due to which the update is being performed
* val - the value being inserted into (row, col)
*/
void update_possibilities(unsigned sudoku_table[TABLE_ORDER_MAX][TABLE_ORDER_MAX],
struct possible_entries possible_values[TABLE_ORDER_MAX][TABLE_ORDER_MAX],
size_t row, size_t col, unsigned val);
/**
* Helper function to avoid redundancy in the 'solve_naked_singles' function.
*
* sudoku_table - the table containing the sudoku board
* possible_values - lookup table for possible values of different cells in the
* sudoku board.
* (search_row_start, search_row_end) - the range of rows which must be searched
for a "hidden single"
* (search_col_start, search_col_end) - the range of colums which must be searched
for a "hidden single"
* val - the "hidden single" value which is being searched for
*
* Returns true if the 'val' is found as a "hidden single" in the search space.
*/
bool solve_hidden_singles_helper(unsigned sudoku_table[TABLE_ORDER_MAX][TABLE_ORDER_MAX],
struct possible_entries possible_values[TABLE_ORDER_MAX][TABLE_ORDER_MAX],
size_t search_row_start, size_t search_row_end,
size_t search_col_start, size_t search_col_end,
unsigned val);
/*
* Update the possibilities of cells as a consequence of detecting a naked double pair
* {(row_1, col_1), (row_2, col_2)}.
*
* sudoku_table - the table containing the sudoku board
* possible_values - lookup table for possible values of different cells in the
* sudoku board.
* (row_1, col_1; row_2, col_2) - the naked double pair due to which the update is being performed
* doubles - the values in the naked double pair
*/
void update_possibilities_1(unsigned sudoku_table[TABLE_ORDER_MAX][TABLE_ORDER_MAX],
struct possible_entries possible_values[TABLE_ORDER_MAX][TABLE_ORDER_MAX],
size_t row_1, size_t col_1,
size_t row_2, size_t col_2,
struct naked_double_values doubles);
/**
* Helper function to avoid redundancy in the 'solve_naked_doubles' function.
*
* sudoku_table - the table containing the sudoku board
* possible_values - lookup table for possible values of different cells in the
* sudoku board.
* (search_row_start, search_row_end) - the range of rows which must be searched
for a "naked double"
* (search_col_start, search_col_end) - the range of colums which must be searched
for a "naked double"
*
* Returns true if a "naked double" was found in the search space.
*/
bool solve_naked_doubles_helper(unsigned sudoku_table[TABLE_ORDER_MAX][TABLE_ORDER_MAX],
struct possible_entries possible_values[TABLE_ORDER_MAX][TABLE_ORDER_MAX],
size_t search_row_start, size_t search_row_end,
size_t search_col_start, size_t search_col_end);
/**
* Initialise 'possible_entries' with values that are possible for a given sudoku cell.
* Obviously the cell is expected not to be an already filled one.
*
* Initialization is done by identifying values that are not possible for the given square
* by linearly searching the corresponding row, column and the square. The 'possible_entries'
* is updated accordingly.
*/
void initialise_possible_values(unsigned sudoku_table[TABLE_ORDER_MAX][TABLE_ORDER_MAX],
struct possible_entries possible_values[TABLE_ORDER_MAX][TABLE_ORDER_MAX],
size_t row, size_t col);
#ifdef KS_SUDOKU_DEBUG
/**
* Print the given possibility vector for the sudoku table.
*/
void print_possibility_vector(unsigned sudoku_table[TABLE_ORDER_MAX][TABLE_ORDER_MAX],
struct possible_entries possible_values[TABLE_ORDER_MAX][TABLE_ORDER_MAX]);
#endif
#endif