This is a Sudoku solver program which uses backtracking. It is a problem from Online Judge and I made it work after some struggle, but it needs to be faster as I'm getting a Time Limit Exceeded message.
The input format:
.46...9..
.3.1.....
.2..6..85
...87....
6...3...4
....14...
79..5..3.
.....2.4.
..2...61.
And then I just need to output the solved board. I am probably making some repeated calls, unnecessary calculations/comparisons that make the program slower, but I don't have any clue how to make this faster.
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int already_given[9+1][9+1];
bool used_list_for_row[9+1][9+1] ; //[current row][current value]
bool used_list_for_col[9+1][9+1] ; //[current col][current value]
bool used_list_for_box[9+1][9+1] ; //[current box][current value]
int solution[9+1][9+1];
inline void init()
{
for(int x=1;x<=9;x++)
for(int y=1;y<=9;y++)
{
already_given[x][y] = 0;
used_list_for_box[x][y] = false;
used_list_for_col[x][y] = false;
used_list_for_row[x][y] = false;
}
}
inline void print_solution()
{
for(int r=1;r<=9;r++)
{for(int c=1;c<=9;c++)
{
if(!already_given[r][c])
printf("%d",solution[r][c]);
else
printf("%d",already_given[r][c]);
}
printf("\n");
}
}
inline int from_r_c_ret_box(int r,int c)
{
if(c>=1 && c<=3)
{
if(r>=1 && r<=3) return 1;
if(r>=3 && r<=6) return 4;
if(r>=6 && r<=9) return 7;
}
if(c>=3 && c<=6)
{
if(r>=1 && r<=3) return 2;
if(r>=3 && r<=6) return 5;
if(r>=6 && r<=9) return 8;
}
if(c>=6 && c<=9)
{
if(r>=1 && r<=3) return 3;
if(r>=3 && r<=6) return 6;
if(r>=6 && r<=9) return 9;
}
}
inline void solver(int cur_row,int cur_col)
{
int cur_box = from_r_c_ret_box(cur_row,cur_col);
if(!already_given[cur_row][cur_col])
for(int possible_val = 1;possible_val<=9;possible_val++)
{if(!used_list_for_row[cur_row][possible_val])
if(!used_list_for_col[cur_col][possible_val])
if(!used_list_for_box[cur_box][possible_val])
{
solution[cur_row][cur_col] = possible_val;
used_list_for_row[cur_row][possible_val] = true;
used_list_for_col[cur_col][possible_val] = true;
used_list_for_box[cur_box][possible_val] = true;
if(cur_col==9 && cur_row == 9)
{
print_solution();
}
if(cur_col==9 && cur_row!=9)
solver(cur_row+1,1);
else
solver(cur_row,cur_col+1);
// printf("R:%d C:%d V:%d\n",cur_row,cur_col,possible_val);
used_list_for_row[cur_row][possible_val] = false;
used_list_for_col[cur_col][possible_val] = false;
used_list_for_box[cur_box][possible_val] = false;
}
}
if(already_given[cur_row][cur_col])
{
if(cur_col==9 && cur_row == 9)
{
print_solution();
}
if(cur_col==9 && cur_row!=9)
solver(cur_row+1,1);
else
solver(cur_row,cur_col+1);
}
}
inline int ctoi(char c)
{
return (c-'0');
}
void process(char ch,int r,int c)
{
if(ch<='9' && ch>='1')
{
already_given[r][c] = ctoi(ch);
used_list_for_row[r][ctoi(ch)] = true;
used_list_for_col[c][ctoi(ch)] = true;
used_list_for_box[from_r_c_ret_box(r,c)][ctoi(ch)] = true;
}
}
int main()
{
int tc = 0;
scanf("%d",&tc);
for(int testcase=1;testcase<=tc;testcase++)
{
init();
char c;int counter_row = 1,counter_col = 0;
while(1)
{
c = getchar();
if(counter_row*counter_col==81) break;
if(c=='.' || (c<='9' && c>='1') )
{
if(counter_row==9 && counter_col==9)
{
process(c,counter_row,counter_col);
break;}
else if(counter_col==9 && counter_row!=9)
{
counter_row++;counter_col=1;
}
else
{
counter_col++;counter_row=counter_row;
}
process(c,counter_row,counter_col);
}
}
printf("Case %d:\n",testcase);
solver(1,1);
//printf("\n");
}
return 0;
}
I have been coding this for last 6 hours without any help (just from the concept of backtracking and I'm also bad at recursion). There are some similar questions but I want to specifically know what I can do with my code to make it faster.