Last active
December 27, 2016 16:57
-
-
Save taeseunglee/2357b65115b4e57611a4633af2aabc99 to your computer and use it in GitHub Desktop.
solve sudoku(9x9) problem using backtracking algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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