Printable View
it si a sudoku program....
i.e, it takes a 9x9 sparse array... and inputs for the array...
using the rules it has to output the solution....
RULES:
1.no element can repeat itself in a row.
2.no element can repeat itself in the column.
3.all elements 1-9 should be present in every row n column....
guys there!!!!!!!!! this is a sudoku prg 9x9...
it works for the first iteration....
i.e, further calls of sol_pos() dont take place.....
Code:
#include<iostream.h>
#include<stdio.h>
int chk_pos(int i,int j,int n); //checks whether a num is a possibilty in pos i,j or not
void sol_pos(void); //puts all 1 possibility nums into their places....
int a[10][10][10]={0};
int chk(int i,int j,int n)
{
int suc=0;
for(int col=0;col<9;col++)
if(a[i][col][0]==n)
{
suc=1;break;
}
for(int row=0;row<9;row++)
if(a[row][j][0]==n)
{
suc=1;break;
}
i=i/3;j=j/3;
for(row=3*i;row<3*(i+1);row++)
for(col=3*j;col<3*(j+1);col++)
if(a[row][col][0]==n)
suc=1;
if(suc==0)
return n;
else
return 0;
}
void sol_pos(void)
{
int i,j,k,fail=0;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
for(k=1;k<9;k++)
a[i][j][k]=0;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
k=1;
if(a[i][j][0]==0)
{
for(int num=1;num<=9;num++)
{
if(chk(i,j,num)!=0)
a[i][j][k++]=num;
}
}
}
}
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(a[i][j][0]==0 && a[i][j][2]==0)
{
fail=1;
a[i][j][0]=a[i][j][1];
}
}
}
if(fail==1)
sol_pos();
}
int main()
{
int rown,coln,n;
cout<<"enter rown coln n :0 to exit:";
do{
cin>>rown>>coln>>n;
if(rown>9 || coln>9 || n>9 || n<1)
cout<<"invalid input";
else
a[rown-1][coln-1][0]=n;
}while(n!=0);
sol_pos();
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
cout<<a[i][j][0]<<" ";
cout<<"\n";
}
return 0;
}
You need to get a newer compiler!
In C++ the headers are
And variables declared in a for loop go out of scope at the end of the loop. So you'll need to declare new loop counters in other loops:Code:#include<iostream>
#include<cstdio>
Code:int suc=0;
for(int col=0;col<9;col++)
if(a[i][col][0]==n)
{
suc=1;break;
}
for(int row=0;row<9;row++)
if(a[row][j][0]==n)
{
suc=1;break;
}
i=i/3;j=j/3;
for(int row=3*i;row<3*(i+1);row++)
for(int col=3*j;col<3*(j+1);col++)
if(a[row][col][0]==n)
suc=1;
Thats a style choice only, since AFAIK there is nothing in the standard that mandates headers use the .h extension. In fact there are quite a few headers out there that use .hppQuote:
Originally Posted by anon
The standard dictates the name of the standard headers, which are as anon said, without the .h
The name, but not the extension. If this were the case then the file itself would be iostream with no extension, which is not the case.
I'm not aware of a compiler that doesn't have iostream (plain, no extension), but I've only looked at gcc on linux, gcc/mingw, and microsoft visual studio 98 and 2003.Quote:
Originally Posted by abachler
http://ece-www.colorado.edu/~pfeffer...si/hfiles.html
http://www.informit.com/guides/conte...lus&seqNum=382
2 mins on google, abachler, lets do a little research before you post again.
Your logic is (naturally) much different than what I use for the game. Are you getting the correct possibles for each square in the 3rd dimension of the array?
That's first! :)
Second, what logic are you using to actually try to solve the puzzle, after getting the possibles listed correctly?
You'll want something like "The rule of pairs" (inside and/or outside), to assist with that, after you've handled the "solo's" (must be's, can't be's), correctly.
After every square that you solve (correctly), you need to re-apply all the logic to help eliminate or elevate the impossible "possibles", whether they're "must be's" (elevate to solutions for a square), or "can't be's", (that get removed from the list of possibles for the square in question), and then lastly, run through the rule of pairs, again.
The last paragraph above, makes sure that any change you make in one square, can "propagate" the correct changes, to every applicable square, anywhere on the board.
Even though it's "just a simple puzzle", it's important to double check the accuracy of each function you code, before going onto the next one. If not you can wind up with hundreds of lines of code, a dozen or so functions, and no idea of where to start de-bugging first! :( :(
A few comments in the code, or before the function, are always good, as well. You'd be surprised how foreign it can all look in a few years.
Lastly, it's a huge help on the forum, if you show the output - what it should be, and what it is, for a sample.
i am getting the possiblities correctly.... but after that i dont know how to proceed.....
and Adak i didnt quite get the point of must be's and cant be's ....can you try and elucidate..??
or redirect me ...??? i know my code lacks the logic after the possibilities...
and i will surely correct my mistake by adding comments..........
Each row, column and box MUST have exactly ONE digit between 1 and 9. So in a simple example:Quote:
Originally Posted by ElemenT.usha
In the upper left hand box of 9 squares, (say, 2, 2), if your list of possibles had a (1, 3) only, for any square's possibles, then that square would be a "must be" of 3, because you can't have two one's in any one box of 9 squares, and you "must" have some number for that square. If you only have one possible, then it's a "must be", of the first order! :)Code:123|456|789
=========
1__|_4_|_8_
___|__7|_2_
___|___|___
Every change in the board, even just removing one possible from one square, requires a full re-run through the basic logic, again. Otherwise, that change will not propagate to other changes, across the entire board, as it should.
I have a rather long (OK, LONG) write up of my program, I'll hunt around and post it up. It has an example of all the logic I used. (and since I'd never played Sudoku before, starting to program the game,), it's pretty easy to understand I think.
If you google "Sudoku", you'll get a zillion websites, some aimed exactly at how to solve the puzzle. My program is long, and goes into a few odd idea's, because I wanted two ways to solve the puzzle: a very fast way, and a much slower way, using an "odometer" approach.
The odometer approach is a laugh riot, but it WILL solve the puzzle (hard one's may take a few seconds to a few years to complete, though). :)
A relatively simple way to solve sudoku is by backtracking. Basically you try a candidate for each cell and if you get to a dead end (a cell for which there are no candidates left), you go back to the previous cell and try the next possible candidate for that (or if you have tried all candidates, back once more) etc. In the end, either all 81 cells are filled in correctly, or there are no more candidates to try for the first cell - in which case this puzzle is unsolvable).
This can solve any puzzle (even without any clues - I use it to generate random solutions) and usually fairly quickly. (With certain unsolvable puzzles where the offending cell is towards the end of the search tree, it might take forever. Therefore you might need to do some tests (that there are no cells with no possible candidates) first.
I think the brute-force "odometer" approach means that a full permutation of the grid is generated and tested etc. This approach is different in that it checks the correctness of the grid so far for each value it tries for each cell. Therefore dead ends are discovered early and a massive number of impossible permutations are skipped each time the algorithm traces back.
The solution for the empty grid might look like this (trying candidates sequentially, left to right, top to bottom):
Quote:
123456789
456789123
789123456
214365897
365897214
897214365
531642978
642978531
978531642
This is the contents of my Sudoku program's, detail pages, with
the formatting data, removed, for easier reading.
The "odometer" function, tries to solve the puzzle, by using each square of the puzzle, like a wheel on yourCode:
* Welcome to the Details Pages *
I began coding this program the same day I began playing Sudoku for
the first time. I've rewritten the first couple of functions which
were somewhat unclear. This was a program of discovery for me, not
a carfully designed algorithm I was already familiar with. I wanted
to include two things - an odometer function, and a very fast function
to solve the puzzle, when desired.
Three arrays of possibles are built up, for every square - row, column,
and box. These three array elements are then compared. Only numbers
that are in all three arrays, are kept. The rest are deleted, since
they can't be a valid number for that square.
Now the second phase begins. Squares with just a single possible
(solo's), are elevated to permanent status. Every other square in
that square's unit (row, column or box), is checked to see if it's
possibles need to be changed as a result.
Next, each unit is checked for 'must be's'. These exist when a unit
has only * one * three (for example), in all it's squares' possibles.
That means that square must be a three, regardless of other possibles.
In the MustBe functions, these are found, and elevated. Each affected
unit squares' possibles, are updated as well.
The outside rule of pairs is used next, to look for matching pairs
of possibles, which may be shared by other squares' possible values.
In a unit like this row:
1 2 3 4 5 6 7 8 9 <== Column #'s
==========================================
25 13 478 389 16 256 89 25 49 <== Possibles
The outside rule of pairs function finds #1 and #8 to have the same
pair of values. Knowing this, #1 must be either a 2 or a 5 and #8 must
be the other number. So * no * other valid possibles can be a 2 or a
5! Which means #6 is changed to just a 6, which makes it a solo, and gets
#6 elevated. Which means also that #5 can't have a 6 in it's possibles.
It becomes just a solo 1, which in turn means that #2 becomes just
a solo 3.
* Welcome to More Details *
In Sudoku, everything you change, can change many other things. Which is
why it's important to loop back through stage two and later functions,
after you've made changes. In this program, looping back through stage two
and above, twice, is required. Three times is never helpful, however.
Each new puzzle grid that you want checked for a solution, will require all
these functions to be called, from stage one, right on up. This sounds
like a rude waste of time, but it's the only way, using my algorithm. These
functions run very fast!
Easy puzzles are solved outright by stage two. Most puzzles need a bit
of trial and error, however. This is the last stage of the program.
I solve this with two functions, each uses a different approach to the
problem. The first one is a virtual odometer function. The squares
with no known value, are 'strung' virtually, next to each other, like
the wheels of an odometer. The possibles for each square, are the numbers
on each wheel. Now we turn the wheels, just like an odometer, and test each
resulting puzzle, to see if it's the solution. To make this work, the
lowest possible original values are assigned to the squares, by Odometer.
The actual incrementing is done by the Increment function, which is called
by Odometer, at the first square it can't assign a good number to. If
Increment can find a good value, it's assigned, and the program returns
to Odometer, for further assignments. It's a back and forth dance, by two
functions working together.
Odometer can solve puzzles which have their solutions in the lower part of
the puzzles search space, with adequate speed. Puzzles which have their
solution in the upper part of their search space, and particularly if that
search should require 'driving' the odometer from the 8th or 9th row -
are a sheer horror!
The second function is MagicTouch, an efficient speed-burner at solving.
It scans the board and id's some squares with only two possibles left. That
squares's array subscript is put into a small array called least(n). Now
MagicDat is called to prepare the dat file templates MagicTouch will use
to set the values of each of the least squares possible value. For example,
* Welcome to Still More Details *
the first template will be:
1 1 1
1 1 2 is next, all the way to:
2 2 2.
These template numbers tell MagicTouch which square should be assigned
to it's first possible value, and which square should be assigned it's
second possible number.
Ironically, MagicDat uses an odometer logic, to create these templates.
MagicTouch now makes the assignments of possibles to each paired square,
according to the next template in the dat file. The resulting puzzle values
are all then given a preliminary test; by row, column, and box. Only
puzzles which have passed the previous test(s), are tested further.
At this point, many of the squares still have no known value! This is
designed to remove obvious conflicts * only *, in the assignments made.
Proposed solutions which pass all three of these preliminary tests, are
passed to the stage one, stage two, and stage three functions, to see if
they really will succeed in solving the entire puzzle.
In early testing, MagicTouch solves every puzzle in less than half a second,
on my P3 laptop, using just interpreted BASIC. No particular optimizations
have been made. Compiled versions of Magic Sudoku are up to 10 times faster,
solving puzzles in limited testing.
An empty Sudoku puzzle, is not a Sudoku puzzle. It is an empty puzzle,
waiting for it's initial values to be given. I had never heard of that
being presented as a puzzle to solve, and this program does not have code
that will support that concept.
car's odometer. Beginning with square 1, 1 (the top left square), it finds the lowest number in the squares
list of "possibles", and assigns that value to the square. It then does the same to the next square 2, 1, and
tests to see if that combo of values is legal; continuing in this way until it finds a square whose assigned value
is NOT legal.
Then it begins incrementing that squares values, through it's range of possibles, from lower to higher values.
If no legal value is found, it moves to the left (back the way it came from), and begins incrementing that wheel's
values, after setting the value of the last wheel, to it's lowest possible value.
This is repeated, all the way back to the first square 1,1, if needed. Since it does no early testing, and only works
it's way up the squares in a very sequential manner, it's deadly slow to solve a problem which has the wrong
value on it's first squares, and that isn't discovered until the odometer function is working with squares down
on the middle or (worse), lowest squares of the puzzle. Then you're REALLY in for a LONG (perhaps days), wait,
for it to solve the puzzle.
You are missing an important rule...Quote:
Originally Posted by ElemenT.usha
Each 3x3 sub grid should contain all elements 1-9
otherwise, this would be valid, shift position by 1 each row like:
123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678
Here is a solver I wrote a while back
And you say you are just a Hobby programmer. Wonder what would you do if you were some professional
programmer!
Thanks for the kind words, manav. :)
Element.usha: Do your possibles list only the possibles for each square, for all these: row, column, and box?
thank you adak .......
the program:::
Code:
#include<iostream.h>
#include<stdio.h>
int input_sdk(void);
int chk_pos(int i,int j,int n);
int get_pos(void);
void print(void);
int must_be(void);
int ord_pair(void);
void reset_ord_i(int ,int ,int );
void reset_ord_j(int ,int ,int );
void reset_pos(void);
int a[10][10][10]={0};
int main()
{
int suc1,suc2;
input_sdk();
for(int cnt=0;cnt<=100;cnt++)
{
do{
reset_pos();
get_pos();
suc1=must_be();
}while(suc1==1);
suc2=ord_pair();
print();
}
print();
return 0;
}
int input_sdk(void)
{
int rown,coln,n;
cout<<"enter rown coln n :0 to exit:";
do{
cin>>rown>>coln>>n;
if(rown>9 || coln>9 || n>9 || n<1)
cout<<"invalid input";
else
a[rown-1][coln-1][0]=n;
}while(n!=0 && rown!=0);
return 0;
}
int get_pos(void)
{
int i,j,k;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
k=1;
if(a[i][j][0]==0)
{
for(int num=1;num<=9;num++)
{
if(chk_pos(i,j,num)!=0)
a[i][j][k++]=num;
}
}
}
}
return 0;
}
int must_be(void)
{
int i,j,success=0;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
if(a[i][j][0]==0)
{
if(a[i][j][2]==0)
{
a[i][j][0]=a[i][j][1];
success=1;
}
}
return (success);
}
int ord_pair(void)
{
int i,j,k,pos,success=0;
for(i=0;i<9;i++)
{
pos=-1;
for(j=0;j<9;j++)
{
if(pos==-1 && a[i][j][3]==0)
pos=j;
else if(a[i][j][3]==0 && pos!=-1)
{
if(a[i][pos][1]==a[i][j][1] && a[i][pos][2]==a[i][pos][2])
{
reset_ord_i(i,a[i][j][1],a[i][j][2]);
must_be();
success=1;
}
}
}
}
for(j=0;j<9;j++)
{
pos=-1;
for(i=0;i<9;i++)
{
if(pos==-1 && a[i][j][3]==0)
pos=i;
else if(a[i][j][3]==0 && pos!=-1)
{
if(a[i][pos][1]==a[i][j][1] && a[i][pos][2]==a[i][pos][2])
{
reset_ord_j(j,a[i][j][1],a[i][j][2]);
must_be();
success=1;
}
}
}
}
return success;
}
int chk_pos(int i,int j,int n)
{
int suc=0;
for(int col=0;col<9;col++)
if(a[i][col][0]==n)
{
suc=1;break;
}
for(int row=0;row<9;row++)
if(a[row][j][0]==n)
{
suc=1;break;
}
i=i/3;j=j/3;
for(row=3*i;row<3*(i+1);row++)
for(col=3*j;col<3*(j+1);col++)
if(a[row][col][0]==n)
suc=1;
if(suc==0)
return n;
else
return 0;
}
void reset_pos(void)
{
int i,j,k;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
for(k=1;k<=9;k++)
a[i][j][k]=0;
}
void reset_ord_i(int i,int x,int y)
{
int j,k,t;
for(j=0;j<9;j++)
{
if(a[i][j][3]!=0)
{
for(k=1;k<=9;k++)
{
if(a[i][j][k]==x || a[i][j][k]==y)
{
t=k;
while(a[i][j][t]!=0)
{
a[i][j][t]=a[i][j][t+1];
t++;
}
}
}
}
}
}
void reset_ord_j(int j,int x,int y)
{
int i,k,t;
for(i=0;i<9;i++)
{
if(a[i][j][3]!=0)
{
for(k=1;k<=9;k++)
{
if(a[i][j][k]==x || a[i][j][k]==y)
{
t=k;
while(a[i][j][t]!=0)
{
a[i][j][t]=a[i][j][t+1];
t++;
}
}
}
}
}
}
void print(void)
{
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(a[i][j][0]==0)
{
int k=1;
cout<<"\t"<<i+1<<j+1<<"pos:";
while(a[i][j][k]!=0)
cout<<a[i][j][k++];
}
}
}
cout<<"\n\n";
for(i=0;i<9;i++)
{
cout<<"\n";
for(int j=0;j<9;j++)
cout<<a[i][j][0]<<" ";
}
}
A few improvements. Mostly just to save time while de-bugging. Try them out.
Code:/* SudokuEL.cpp, by ElemenT.usha
Status: checking possibles and promotion of "solo's", logic.
EZ game is shown as having two 6's in row 3, and two 2's in column 1.
*/
#include<iostream.h>
#include<stdio.h>
int input_sdk(void);
int chk_pos(int i,int j,int n);
int get_pos(void);
void print(void);
int must_be(void);
int ord_pair(void);
void reset_ord_i(int ,int ,int );
void reset_ord_j(int ,int ,int );
void reset_pos(void);
int a[10][10][10]={0};
int main()
{
int suc1,suc2;
input_sdk();
for(int cnt=0;cnt<=100;cnt++)
{
do{
reset_pos();
get_pos();
suc1=must_be();
}while(suc1==1);
suc2=ord_pair();
print();
}
print();
cout << "\n\n\t\t\tProgram Complete, Press Enter";
suc2 = getchar(); //just to hold the window open for viewing
putchar(suc2); //stops a stupid warning
return 0;
}
int input_sdk(void)
{
int rown,coln,n;
char load = 'y';
//cout << "Load EZ puzzle y/n? ";
//cin >> load;
if (load == 'y' || load == 'Y') {
a[0][2][0]=8; a[1][1][0]=5; a[1][3][0]=1; a[1][6][0]=7; a[1][8][0]=9;
a[2][1][0]=3; a[2][3][0]=9; a[2][4][0]=7; a[2][7][0]=4; a[2][8][0]=1;
a[3][1][0]=1; a[3][3][0]=7; a[4][2][0]=5; a[4][3][0]=9; a[4][5][0]=8;
a[4][6][0]=1; a[5][5][0]=2; a[5][7][0]=3; a[6][0][0]=8; a[6][1][0]=9;
a[6][4][0]=4; a[6][6][0]=5; a[6][7][0]=2; a[7][0][0]=7; a[7][2][0]=4;
a[7][5][0]=1; a[7][7][0]=8; a[8][6][0]=9;
}
else {
cout<<"enter rown coln n :0 to exit:";
do{
cin>>rown>>coln>>n;
if(rown>9 || coln>9 || n>9 || n<1)
cout<<"invalid input";
else
a[rown-1][coln-1][0]=n;
}while(n!=0 && rown!=0);
}
return 0;
}
int get_pos(void)
{
int i,j,k;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
k=1;
if(a[i][j][0]==0)
{
for(int num=1;num<=9;num++)
{
if(chk_pos(i,j,num)!=0)
a[i][j][k++]=num;
}
}
}
}
return 0;
}
int must_be(void)
{
int i,j,success=0;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
if(a[i][j][0]==0)
{
if(a[i][j][2]==0)
{
a[i][j][0]=a[i][j][1];
success=1;
}
}
return (success);
}
int ord_pair(void)
{
int i,j,k,pos,success=0;
for(i=0;i<9;i++)
{
pos=-1;
for(j=0;j<9;j++)
{
if(pos==-1 && a[i][j][3]==0)
pos=j;
else if(a[i][j][3]==0 && pos!=-1)
{
if(a[i][pos][1]==a[i][j][1] && a[i][pos][2]==a[i][pos][2])
{
reset_ord_i(i,a[i][j][1],a[i][j][2]);
must_be();
success=1;
}
}
}
}
for(j=0;j<9;j++)
{
pos=-1;
for(i=0;i<9;i++)
{
if(pos==-1 && a[i][j][3]==0)
pos=i;
else if(a[i][j][3]==0 && pos!=-1)
{
if(a[i][pos][1]==a[i][j][1] && a[i][pos][2]==a[i][pos][2])
{
reset_ord_j(j,a[i][j][1],a[i][j][2]);
must_be();
success=1;
}
}
}
}
return success;
}
int chk_pos(int i,int j,int n)
{
int suc=0;
for(int col=0;col<9;col++)
if(a[i][col][0]==n)
{
suc=1;break;
}
for(int row=0;row<9;row++)
if(a[row][j][0]==n)
{
suc=1;break;
}
i=i/3;j=j/3;
for(row=3*i;row<3*(i+1);row++)
for(col=3*j;col<3*(j+1);col++)
if(a[row][col][0]==n)
suc=1;
if(suc==0)
return n;
else
return 0;
}
void reset_pos(void)
{
int i,j,k;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
for(k=1;k<=9;k++)
a[i][j][k]=0;
}
void reset_ord_i(int i,int x,int y)
{
int j,k,t;
for(j=0;j<9;j++)
{
if(a[i][j][3]!=0)
{
for(k=1;k<=9;k++)
{
if(a[i][j][k]==x || a[i][j][k]==y)
{
t=k;
while(a[i][j][t]!=0)
{
a[i][j][t]=a[i][j][t+1];
t++;
}
}
}
}
}
}
void reset_ord_j(int j,int x,int y)
{
int i,k,t;
for(i=0;i<9;i++)
{
if(a[i][j][3]!=0)
{
for(k=1;k<=9;k++)
{
if(a[i][j][k]==x || a[i][j][k]==y)
{
t=k;
while(a[i][j][t]!=0)
{
a[i][j][t]=a[i][j][t+1];
t++;
}
}
}
}
}
}
void print(void)
{
int m = 0;
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(a[i][j][0]==0)
{
int k=1;
if(m++ % 4 == 0)
cout << "\n";
cout<<"\t"<<i+1<<j+1<<"pos:";
while(a[i][j][k]!=0)
cout<<a[i][j][k++];
}
}
}
cout<<"\n\n";
for(i=0;i<9;i++)
{
if(i%3==0 && i > 1) {
cout << "\n ";
cout << "---------------------";
}
cout<<"\n ";
for(int j=0;j<9;j++) {
if(j%3==0 && j > 1)
cout << "| ";
cout<<a[i][j][0]<<" ";
}
}
cout << '\n';
}
thanxxx dude... got the solution ... just tell me whether the code is completely generalised in every respect
how many different ways are there to code a sudoku solver???? i have seen the box, line. and row. the brute force, the better brute force and several other ways that i cant understand
How many threads do we need about sudoku?
one for each idiot that tries to make a sudoku solver without any idea of which algorithms would be good at it (this includes my sudoku thread), and one more thread for everyone who knows what they're doingQuote:
Originally Posted by Bubba
so a little more than 5 billion then, which is around 3x as many as we currently have
Sorry, I did not realize how old this thread was before responding. Closed for obvious reasons.