Thread: Sudoku brute force

  1. #1
    Registered User
    Join Date
    Feb 2011
    Posts
    1

    Sudoku brute force

    I am a beginner in C++ programming. I was trying to make a Sudoku solver by Brute Force, but I just cant seem to figure out whats amiss.

    I have tried to assign random unique numbers to each row and each column. Theoretically, by using unrelated random numbers, this is bound to give me a solution for the sudoku.

    Can someone help me make this thing work ?



    Code:
    
    #include <iostream.h>
    #include <conio.h>
    #include <stdlib.h>
    #include <time.h>
    
    
    void main()
    {
    srand(time(NULL));
    
    int arr[9][9];
    int full[9][9];
    
    cout << "INSTRUCTIONS!";
    cout << endl << "Enter the initial Sudoku square";
    cout << "\\nEnter the numbers where they appear, or enter 0 if there is a blank space\n\n";
    
    //counters
    int i=0,j=0;
    
    for(i=0;i<9;i++)
    {
    	for(j=0;j<9;j++)
    	{
    		full[i][j]=0;
    		cout << "Enter the element at " << (i+1) << "," << (j+1) << ": ";
    		cin >> arr[i][j];
    		if(arr[i][j]!=0)
    			full[i][j]=1;
    	}
    }
    clear1: clrscr();
    
    for(i=0;i<9;i++)
    {
    	for(j=0;j<9;j++)
    	{
    		cout << arr[i][j] << "\t";
    	}
    	cout << endl;
    }
    
    
    
    for(i=0;i<9;i++)
    {
    	for(j=0;j<9;j++)
    	{
    		if(full[i][j]==0)
    		{
    
    			int x= random(1000);
    			x=(x%9)+1;
    			arr[i][j]=x;
    		}
    	}
    }
    clrscr();
    
    //horizontal check
    for(i=0;i<9;i++)
    {
    	int flag=1;
    	for(j=0;j<9;j++)
    	{
    		for(int J=(j+1);J<9;J++)
    		{
    			if(arr[i][j]==arr[i][J])
    				goto clear1;
    		}
    	}
    
    }
    //vertical check
    for(j=0;j<9;j++)
    {
    	int flag=1;
    	for(i=0;i<9;i++)
    	{
    		for(int I=(i+1);I<9;I++)
    		{
    			if(arr[i][j]==arr[I][j])
    				goto clear1;
    		}
    	}
    
    }
    //subgrid check
    // to be implemented after horizontal+vertical checks are done
    
    for(i=0;i<9;i++)
    {
    	for(j=0;j<9;j++)
    	{
    		cout << arr[i][j] << "\t";
    	}
    	cout << endl;
    }
    
    getch();
    clrscr();
    
    
    }

  2. #2
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    463
    randomly assign numbers until you get the solution?????? It's like throwing a deck of cards into the air and hope it's sorted when you pick it up. Google backtracking for a better way to solve sudoku.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    It's worse than that. The given code just picks a value for each empty cell and then stops. There's no loop clearing out of values to try again and hope to wander upon the solution, it just makes one guess and stops.

    This would be like throwing a deck of cards in the air only once and expecting them to land sorted. No picking them up to start over!
    The odds of this working are probably worse than your chances of winning the lottery three days in a row.

    You need to step back and come up with another plan. Even if you retried with the approach you're using, it would not work.
    Last edited by iMalc; 02-13-2011 at 02:51 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Jan 2011
    Posts
    87
    here is my sudoku solver, so far it tests the row, column, and box and eliminates numbers if they are there. it has few comments but it should be pretty easy to follow. its kinda big.
    i was working on this for several weeks before i saw this thread so dont think i did this in one day
    if you have any changes please post them

    note: i still need to do a bit more editing to get it to run smooth and make sure it has no bugs but it is pretty good

    i took my program out and put it in its own thread
    Last edited by bobknows; 02-14-2011 at 07:23 AM. Reason: i took my program out and am starting a new thread for it. see above ^^^

  5. #5
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    Great, just hand him the solution and dont make him think and solve it by himself...

    It really isn't a favor to hand somebody a complete solution. They learn more when solving things on their own, plus that sensation of accomplishment after they solved that damn problem is a very nice sideeffect.

  6. #6
    Registered User
    Join Date
    Jan 2011
    Posts
    87
    this isnt really a solution...
    i just included a whoel program that is structured completely different from his that does the same thing. besides, mine isnt finished yet. i just thought that it would be better to add my program to this thread instead of making a whole new one for the same purpose.

  7. #7
    Banned ಠ_ಠ's Avatar
    Join Date
    Mar 2009
    Posts
    687
    Quote Originally Posted by bobknows View Post
    this isnt really a solution...
    i just included a whoel program that is structured completely different from his that does the same thing. besides, mine isnt finished yet. i just thought that it would be better to add my program to this thread instead of making a whole new one for the same purpose.
    incorrect
    ╔╗╔══╦╗
    ║║║╔╗║║
    ║╚╣╚╝║╚╗
    ╚═╩══╩═╝

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by bobknows View Post
    this isnt really a solution...
    i just included a whoel program that is structured completely different from his that does the same thing. besides, mine isnt finished yet. i just thought that it would be better to add my program to this thread instead of making a whole new one for the same purpose.
    Add to it?! It's already far too large.

    When you have code like this, you're doing it wrong:
    Code:
                                    case 1:
                                    {
                                        guess1 = true;
                                        break;
                                    }
                                    case 2:
                                    {
                                        guess2 = true;
                                        break;
                                    }
    ...
                                    case 8:
                                    {
                                        guess8 = true;
                                        break;
                                    }
                                    case 9:
                                    {
                                        guess9 = true;
                                        break;
                                    }
    When you have this many parameters, you're doing it wrong:
    Code:
    enternumber(bool g1, bool g2, bool g3, bool g4, bool g5, bool g6, bool g7, bool g8, bool g9, int x4, int y4)
    One can learn a lot from that code in that it is in a lot of ways precisely how not to write a Sudoku solver.

    If you know how to use arrays, then use arrays for crying out loud!

    Yes I've written my own, using a bitboards approach with optimised backtracking. You probably don't want to hear how fast it is.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Jan 2011
    Posts
    87
    ok, ill take it out and start a new thread then.

    also, i had'nt thought about using an array for the guesses, ill use them in a for loop with an array now, thanks

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Running a Brute Force Attack Simulation...
    By Junior89 in forum C++ Programming
    Replies: 31
    Last Post: 02-13-2011, 08:52 PM
  2. Brute Force
    By 123sample in forum C Programming
    Replies: 4
    Last Post: 09-12-2010, 12:37 AM
  3. Sudoku Brute Force Algorithm Help (recursion?)
    By ridilla in forum C Programming
    Replies: 22
    Last Post: 05-07-2010, 03:31 PM
  4. Brute Force
    By swgh in forum A Brief History of Cprogramming.com
    Replies: 6
    Last Post: 08-16-2007, 01:41 AM
  5. Replies: 2
    Last Post: 03-21-2004, 08:21 PM