Hi guys,

I have been working on a sudoku solver, that finds solution by brute forcing during my school days.... But due to the huge number of loops i couldn't do it at then.... SO decided to complete it now....

So here the algorithm:
1. Get the number of fixed values from the user.
2. Populate those values..
3. Check if the input sudoku is valid.
4. If valid, fill each posistion by checking numbers from 1 to 9, if they are valid at the posistion...
5. Done....

Well! In my sudoku i have only checked for rows and colomns..... i.e I don't care if a number repeats in 3*3 matrics.... I will work on that bit, later....

Now the prob is, i cannot get the bruteforcing part correctly.... Even the check for a valid input sudoku is not working......
SO please help me guys...... No syntax error.... Some logical one.....
Thanks in advance.....

// Gigantic Addtion.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


int _tmain(int argc, _TCHAR* argv[])
{
    return 0;
}

#include<iostream>
#include<fstream>

using namespace std;

void display(int sudoku[9][9])
{
    for(int i=0;i<9;i++)
    {
        cout<<endl<<endl;
        for(int j=0;j<9;j++)
        {
            cout<<sudoku[i][j]<<"  ";
        }
    }
    cout<<endl;
}
void fix(int sudoku[9][9])
{
    int num, flag=0;
    do
    {

        cout<<"Enter the number of fixed values you want place in Sudoku"<<endl;
        cin>>num;
    }while(num<0&&num>9);

    for(int k=0;k<num;k++)
    {

        int i,j,val;
        do
        {
            cout<<"Please enter the cordinates of the number(Row*coloumn)"<<endl;
            cin>>i>>j;
            do
            {
                cout<<"Enter the value"<<endl;
                cin>>val;
            }while(val<1&&val>9);

            if(sudoku[i-1][j-1]==10)
            {
                sudoku[i-1][j-1]=val;
                system("CLS");
                display(sudoku);
                flag=0;
            }
            else
            {
                cout<<"Value already fixed at the point"<<endl;
                flag=1;
            }
        }while(flag==1);
    }

}

int check(int sudoku[9][9])
{
    int flag=0;
    cout<<endl<<"Checking"<<endl;
    for(int i=0;i<9;i++)
    {

        for(int j=0;j<9;j++)
        {

            if(sudoku[i][j]!=10)
            {
                for(int k=0;k<9;k++)
                {

                    for(int p=0;p<9;)
                    {

                        if(i!=k||p!=j)
                        {
                            if(sudoku[i][j]==sudoku[k][j])
                            {
                                cout<<"Invalid fixed numbers"<<endl;
                                flag=1;
                                break;
                            }
                            else
                            {
                                break;
                            }
                        }
                    }
                }
                for(int s=0;s<9;s++)
                {

                    for(int g=0;g<9;)
                    {

                        if(i!=g||j!=s)
                        {

                            if(sudoku[i][j]==sudoku[g][s])
                            {
                                cout<<"Invalid fixed numbers"<<endl;
                                flag=1;
                                break;
                            }
                            else
                            {
                                break;
                            }
                        }

                    }
                }
            }
        }
    }
    return flag;
}


void fill(int sudoku[9][9])
{
    int flag1=1, flag2=1;
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            for(int k=1;k<10;k++)
            {
                if(sudoku[i][i]==10)
                {
                    for(int l=0;l<9;l++)
                    {
                        for(int p=0;p<9;)
                        {
                            if(sudoku[l][p]!=k)
                            {
                                flag1=0;
                            }
                            else
                            {
                                flag1=1;
                            }
                        }
                    }
                    for(int q=0;q<9;q++)
                    {
                        for(int v=0;v<9;)
                        {
                            if(sudoku[v][q]!=k)
                            {
                                flag2=0;
                            }
                            else
                            {
                                flag2=1;
                            }
                        }
                    }
                    if(flag1==0&&flag2==0)
                    {
                        sudoku[i][j]=k;
                        system("CLS");
                        display(sudoku);
                    }
                }
            }
        }
    }
}


void main()
{

    int sudoku[9][9];
    int test;
    int enter;
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            sudoku[i][j]=10;
        }
    }
    display(sudoku);
    fix(sudoku);
    test=check(sudoku);
    if(test==1)
    {
        cout<<"Your Sudoku input is wrong, Hence cannot be solved"<<endl;
        display(sudoku);
    }
    else
    {
        fill(sudoku);
    }
    display(sudoku);
    cin>>enter;
}

While there are multiple parts in your code that I find a bit shady, the real mess starts at the "check" and "fill" functions I guess. A very quick look at the fill function reveals this loop:

for(int p=0;p<9;)

In the other functions you used break statements to terminate the loop (which I think is poor in this case, one of the reasons being resulting in issues like this one), but here you don't.

Overall though I don't think you put much thought into your algorithm. I also think you're underestimating some things. For example, checking if a sudoku is valid might not be all that trivial. (Checking to see if a sudoku only has 1 unique solution for example might not be something you can quickly do. Although I'd have to ponder on it to say it with certainty..)

Aside from the algorithm you could divide your functions into smaller functions a lot better, and your naming could be a lot better too. multiple nested loops are not great to plough through.

You don't seem to have put a whole lot of effort into this, so I won't either, but a quick brainstorm on how I would approach this:

  1. Read a sudoku from a file (instead of letting it be entered by a user)
  2. Keep track of the remaining possibilities per empty square. (based on the row, column and 3x3 square the square is part of)
  3. Find the square which has the least remaining possibilities.
  4. Try these possibilities for this square (which means entering it, and updating the column/row/square's remaining possibilities) and then try to solve the sudoku recursively.

If the sudoku is proper, meaning it only has 1 unique solution it will find the one solution. Wrong tries at the 4th step will at some point result in one or more empty square's with 0 remaining possibilties, meaning it is not solvable. If the sudoku is not proper it might result in multiple solutions, for example when you start with a completely empty sudoku. You could perform checks for this in the recursive solving function so it shows errors, or only shows the first found solution. Whatever suits your needs.

but a quick brainstorm on how I would approach this:

K! Fine! I get it.... But here is the thing, i have given way with any sort of algorithm simplification in my code. What i aim here is to have a basic bruteforcing program, which take care of a single square at a time... I don't want it to look for squares with lowest possible number of possibilities....
But your suggestions are great, and i will work with it later... But for now.... What i want it to do is: (Reposting with some more elaborate steps)
1. Get the number of fixed values from the user..
2. Have that number of variables fixed in the sudoku array, by getting coordinates from the user.
3. Check if the present input sudoku values are valid... i.e no row or coloumn has a repeated value in it...
4. Start with the first square, and check the smallest number(1-9), possible in that square. and fix it there.
5. Advance to the next square and repeat step 4.
6. If the selected square already have a value, skip it....
7. The final result is the solved Sudoku......

I know the fact that, this type of bruteforcing with zero simplification at any point in the program is really heavy on the processor and all that.... But that is something i am trying to do.....
My objective is not to solve a sudoku.... It's to use the most basic bruteforcing algorithm to do the job..

And As per this program, it is not necessary that, the sudoku should have a single solution. Like if i fix only a single value in the array, there are lot of solutions... From which i only get or take the one that bruteforcing result in.....

Thanks you so much for the time, and suggestions. I will look in to that for sure....

A very quick look at the fill function reveals this loop:

And yes! Thank you for pointing out that loop... Yeah! It is not that necessary to have that loop. I will replace it and post it again..... Thank You so much.....

My objective is not to solve a sudoku.... It's to use the most basic bruteforcing algorithm to do the job..

I'm a little bit confused by this. Could you define what you mean by "the job" exactly? The algorithm you describe may result in a non-solvable sudoku while it could have been solved in it's original state. For example, consider something like this:

000|000|456
000|120|000
000|000|000
-----------
020|000|000
000|000|000
000|000|000
-----------
002|000|000
000|000|000
000|000|000

Am I right in thinking that your algorithm will place "1" at the top left square because it's the lowest value that can be there? (There is no 1 in the 3x3 square, none in the row and none in the column) But when you place a 1 there you result in a non-solvable soduko as there is no longer space for a '2' in the top row.

Maybe I wasn't clear, but the steps I posted earlier are also a brute-force approach to solving a sudoku.

This article has been dead for over six months. Start a new discussion instead.