Sudoku-solving program

Question

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.

Answer 1

• The indentation is a complete mess. I have seriously never seen this before
• You are reinventing the wheel with ctoi, which, if I understood well, does basically what atoi does.
• There isn't a single useful comment in your code. It's either dead code (which should be removed) or some strange thing
• The naming of your variables is quite bad and inconsistent. One example : x, y, r and c. I guess x and r are the same thing and that the same goes for y and c. x and y are maybe the only one-character long variable names that are acceptable (and I personally prefer iRow and iCol to avoid confusion), but that's just one example.
• if(ch<='9' && ch>='1') You're just lucky that works. If you want to use comparison, prefer using numbers, not characters that are represented by numbers by the machine.
• Multiple expressions on one line (counter_row++;counter_col=1; for example) is also something you don't quite see often. The main reason is that it does not make you win anything but a line in your file (and who cares ?), but it makes your code hard to read.
• The types of your variables is also quite bad. Let's look at that int from_r_c_ret_box(int r,int c). We've kind of figured that r and c are rows and columns numbers, so why do you allow them to take negative values ? unsigned int would be better, and as a sudoku is a 9*9 square, unsigned short would be perfect.
• the while(1) is useless and dangerous. Just make a proper condition, or even better, as you know the number of iteration, do a for loop (well, two in this case).

That's already quite a lot to do before even considering improving the algorithm. Bit it would be a pleasure to make another review once you have corrected the few points below (if you want to do that, post another question, don't edit this one).