Sudoku

[u8sand]

Hello everyone...
Recently, i tried making a puzzle solver. And it came out perfect. I wanted to try somthing harder so i went on to a sudoku puzzle solver. You see i checked a bunch of places and found that the best and easiest way to do it is with a function that trys ever

[Ancient Dragon]

Is this a question? If it is, then I don't get it.

[u8sand]

sorry i typed a whole thing with coding and everything it dident post tho... wtf. Lemme do it again soz.

[u8sand]

Class

#include "includes.h"

int game[9][9];

class Solver
{
public:
    Solver() { trys = 1; it = 1; }
    ~Solver() {}
    
    bool Solve();
    bool IsOkAt(int,int,int);
    
    int trys;
    int it;
private:
};

bool Solver::Solve()
{
    bool c = false;
    int b = trys;
    int i = 0;
    int n = 0; // i,n and q for the for loops.
    int q = 0;
    for(i = 0; i < 9; i++)
        for(n = 0; n < 9; n++)
        {
            if(!IsOkAt(game[i][n],n,i)) // is the thing there already ok?
            { // not? then try somthing else
                for(q = 1; q < 10 && !c; q++)
                {
                    trys++;
                    if(IsOkAt(q,n,i))
                    {
                        game[i][n] = q;
                        c = true;
                    }
                }
                if(c) // found it
                {
                    system("cls");
                    cout << trys << " try(s)\n" << it << " iteration(s)\n";
                    for(i = 0; i < 9; i++)
                    {
                        for(n = 0; n < 9; n++)
                            cout << game[i][n];
                        cout << endl;
                    }
                    c = false;
                }
                else // stuck?
                {
                    if(trys != b)
                    {
                        it++; // another iteration
                        Solve(); // re-do function
                    }
                    else  // stuck and nothing happend? unsolvible...
                        return false;
                }
            }
        }
    if(trys != b) // you did somthing, try again
    {
        it++;
        Solve();
    }
    return true; // you dident do anything on that try, ok, it's solved..
}

bool Solver::IsOkAt(int num,int x,int y)
{
    if(num < 1 || num > 9)
        return false;
    for(int i = 0; i < 9; i++) // commums
        if(game[i][x] == num && i != y)
            return false;
    for(int i = 0; i < 9; i++) // rows
        if(game[y][i] == num && i != x)
            return false;
    return true; // all good? return true..
}

Includes.h

#ifndef INCLUDE
#define INCLUDE

#include <iostream>
#include <fstream>
#include <windows.h>

using namespace std;

#endif

main.cpp

#include "includes.h"
#include "Sudoku.h"

int main()
{
    system("title Sudoku Solver");
    ifstream fin("Sudoku.txt");
    if(!fin)
    {
        fin.close();
        ofstream fout("Sudoku.txt");
        fout << "000000000\n000000000\n000000000\n000000000\n" << 
                "000000000\n000000000\n000000000\n000000000\n" <<
                "000000000\n";
        fout.close();
        cout << "Sudoku.txt did not exist.. It is now created, insert your sudoku game there.\n";
    }
    else
    {
        char line[256];
        for(int y = 0; y < 9; y++)
        {
            fin.getline(line,256);
            for(int x = 0; x < 9; x++)
            {
                game[y][x] = (((int)line[x])-48);
            }
        }
        fin.close();
        cout << "Puzzle to solve... Starting in 2 seconds..\n\n";
        for(int i = 0; i < 9; i++)
        {
            for(int n = 0; n < 9; n++)
                cout << game[i][n];
            cout << endl;
        }
        Sleep(2000);
        Solver s;
        if(!s.Solve())
            cout << "Could not solve : (\n";
        else
            cout << "\n\nSOLVED!\n";
    }
    system("pause");
    return 0;
}

this program is suppost to solve a sudoku game that you insert into the notpad document...
It works if you comment out the collums and leave rows in the IsOkAt function, or comment out the rows and leave collums. But doesent work together. It crashes. Please somone tell me what might be wrong?
Btw, i did not code it to find the 3by3 squares yet but i will when i finish this problem.

And thanks dragon for posting even though my post made no sence : /.

[cikara21]

post "Sudoku.txt" please...:)

[cikara21]

your problems is..

bool Solver::Solve()
{
     //...........
     else // stuck?
     {
      if(trys != b)
      {
          it++; // another iteration
          Solve(); //-------------------- [B]HERE [/B]----------------------//
      }
      else  // stuck and nothing happend? unsolvible...
           return false;
    }
    //............
    if(trys != b) // you did somthing, try again
    {
        it++;
        Solve(); //-------------------- [B]OR HERE[/B] ----------------------//
    }
}

[StuXYZ]

As cikara pointed out, you are incorrectly using trys!=b and that is going to get you into a mess.

I would (a) suggest that you use a count of the zeros to decide if you have succeeded. (b) Have a look at your algorithm. (c) check the rules of since you are not checking that the square (3x3) only contains 9 unique digits.

The algorithm is going to get stuck. THEN you have no way to back track ( ie suppose that you have put 1 in game[0][0] but that turns out to be incorrect then how do you replace that with a 2 if putting a 1 does not violate the problem.).

In your code, game is ok to be global, but solver should work with its own copy. Then the starting values can be set to allow iteration progression.

However, the algorithm is awful, especially as you scale to larger sudoku (4x4, 5x5 ..., 3x3x3 etc). Even for 3x3 you have on average about [TEX]10^{30}[/TEX] options (based on typically, 55 open positions)

However, if you try to keep a possible list for each square, then a series of simple rules will fill a large amount of the grid in (or reduce the search list. (and the determination of ring depends will allow you to prove that the problem has multiple solutions.)

[u8sand]

Well thank you everyone for posting.
I still have not completly figured out what my problem was but decided to search for a new algorithum. I was aware that this method would not get me EVERY puzzle, but at least work for some. Thanks guys. Ima mark the post as solved.

[algoboy]

Hi guys, I've write a c++ code to solve sudoku, please check this link:
http://algojava.blogspot.com/2009/01/sudoku-solver-c.html