5
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Cross-posted from Stack Overflow \$\endgroup\$ – 200_success Jul 20 '15 at 3:41
  • \$\begingroup\$ I was told to post it in the codereview section \$\endgroup\$ – anon Jul 20 '15 at 3:42
  • \$\begingroup\$ No problem with cross-posting. Just declare it properly so that you don't waste other users' time. \$\endgroup\$ – 200_success Jul 20 '15 at 3:43
  • 5
    \$\begingroup\$ Please for the love of all that is holy, fix your indentation. Spend two minutes clicking around on here, learn how people usually indent C++ code, and copy their style. Once that's fixed, we can talk about the subtler problems with the code. \$\endgroup\$ – Quuxplusone Jul 20 '15 at 6:10
1
\$\begingroup\$
  • 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).

\$\endgroup\$
  • 1
    \$\begingroup\$ Some of this is bad advice; for example, the advice to replace int with unsigned short throughout your code. Also notice that '1'<=ch && ch<='9' is guaranteed to do the right thing in C and C++, no matter what the execution character set is; the digits '0' through '9' must be contiguous and in order, even if the implementation has to jump through hoops to make that happen on your platform. \$\endgroup\$ – Quuxplusone Jul 21 '15 at 3:57
  • \$\begingroup\$ Can you explain why using unsigned short type for columns and rows ranging from 0 to 8 (or 1 to 9) is bad advice ? I get the validity of the other point (but since he converts the characters to integers just after, I would defintely convert first and check the result after conversion), but not this one. \$\endgroup\$ – Loufylouf Jul 21 '15 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.