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
u8sand 68
- 5 Contributors
- forum8 Replies
- 9 Views
- 9 Years Discussion Span
- comment Latest Post by algoboy
Ancient Dragon 5,243
Is this a question? If it is, then I don't get it.
u8sand 68
sorry i typed a whole thing with coding and everything it dident post tho... wtf. Lemme do it again soz.
u8sand 68
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 37
post "Sudoku.txt" please...:)
cikara21 37
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 731
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 68
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 1
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
u8sand
commented:
Nice, i'll use this as a guide +1