Skip to content

Instantly share code, notes, and snippets.

@taeseunglee
Last active December 27, 2016 16:57
Show Gist options
  • Save taeseunglee/2357b65115b4e57611a4633af2aabc99 to your computer and use it in GitHub Desktop.
Save taeseunglee/2357b65115b4e57611a4633af2aabc99 to your computer and use it in GitHub Desktop.
solve sudoku(9x9) problem using backtracking algorithm
#include <stdio.h>
#include <stdbool.h>
struct coord{
int x;
int y;
};
/* structure of parameters for play_sudoku function */
struct __sudoku_param {
int grid[9][9];
struct coord ulc[81]; /* ulc : unassigned 'location candidates' */
int ulc_size;
int ulc_idx; /* next ulc index */
};
bool play_sudoku(struct __sudoku_param*);
void find_avail_number(struct coord, struct __sudoku_param*, bool*);
void print_grid(struct __sudoku_param);
int main(void)
{
struct __sudoku_param sudoku_param;
/* Initialization */
int ulc_size = 0;
for(int i=0; i<9; i++){
for(int j=0; j<9; j++){
scanf("%d",&sudoku_param.grid[i][j]);
if (!sudoku_param.grid[i][j]) {
sudoku_param.ulc[ulc_size].x = i;
sudoku_param.ulc[ulc_size].y = j;
ulc_size ++;
}
}
}
sudoku_param.ulc_size = ulc_size;
sudoku_param.ulc_idx = 0;
/* Run */
play_sudoku(&sudoku_param);
/* Print the result */
print_grid(sudoku_param);
return 0;
}
// Backtracking
bool play_sudoku(struct __sudoku_param* sudoku_param)
{
struct coord point;
if (sudoku_param->ulc_idx == sudoku_param->ulc_size)
return true;
point.x = sudoku_param->ulc[sudoku_param->ulc_idx].x;
point.y = sudoku_param->ulc[sudoku_param->ulc_idx].y;
sudoku_param->ulc_idx++;
bool is_avail[10];
for (int i = 1; i < 10; i++)
is_avail[i] = true;
find_avail_number(point, sudoku_param, is_avail);
for (int i = 1; i < 10; i++) {
if(is_avail[i]) {
sudoku_param->grid[point.x][point.y] = i;
if(play_sudoku(sudoku_param)) return true;
sudoku_param->grid[point.x][point.y] = 0;
}
}
sudoku_param->ulc_idx--;
return false;
}
/* Find available numbers at the point */
void find_avail_number(struct coord point, struct __sudoku_param* sudoku_param, bool* is_avail)
{
for(int idx = 0; idx < 9; idx++){
is_avail[sudoku_param->grid[idx][point.y]] = false;
is_avail[sudoku_param->grid[point.x][idx]] = false;
}
int start_x = (point.x/3)*3;
int start_y = (point.y/3)*3;
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
is_avail[sudoku_param->grid[start_x+i][start_y+j]] = false;
}
}
}
void print_grid(struct __sudoku_param sudoku_param)
{
for(int i=0; i<9; i++){
for(int j=0; j<9; j++){
printf("%d ", sudoku_param.grid[i][j]);
}
printf("\n");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment