Sudoku in C or C++

For your information, this is still a project that I have to present during the oral exam of my BTS in computer science. I'm not very comfortable because I got into computer science for this BTS, which was somewhat imposed on me (and going back to school after 9 years in the workforce isn't necessarily easy), so I have to meet certain criteria for the exam, such as creating an app in C or C++.

Thank you, Nabla's and the others, for the ideas provided. I will look into it and get back to you if I need help.

messages <3>, <4>, <5>
I don’t know if it’s the time or if I’m losing patience, but this is the second time in a row that I come across a C++ discussion thread where the answers have NOTHING to do with the question asked. We’re not here to share our life stories or discuss the topic, it’s crazy!

@dna.factory
So NO, a sudoku is not complicated to program if you know how to write for loops. Moreover, there’s no solver to program. You just need to think for two minutes before diving in.

Each cell can contain a value from 0 to 9 (its domain). This domain is restricted by the cells in the block, row, and column. I’ll give you the method in pseudo code so you still have a bit of work left. The usual sudoku contains 3x3 blocks of 3x3 cells each (n=3).

For each cell (i,j) in the grid If the domain of cell(i,j) is reduced to one element: place it Else: draw a value v at random from the remaining values in the domain For each cell in row i: remove value v from the domain For each cell in column j: remove value v from the domain For each cell in the n x n square containing (i,j): remove value v from the domain End for

In my humble opinion, people who say it’s out of their reach are frankly misguided. The verification is actually simpler. The only "difficulty" is associating a cell (i,j) with a block (but that’s not a big deal).

#define n 3 // sudoku 3x3 blocks of 3x3 cells // Associate each cell (row,column) with an index that identifies a block // (the top left block is 0, the one to its right is 1, etc...) which gives // this mapping for n = 3 : // 000111222 // 000111222 // 000111222 // 333444555 // 333444555 // 333444555 // 666777888 // 666777888 // 666777888 // Returns the identifier of the block containing the cell (row, column) unsigned coordinates2block(unsigned row,unsigned column){ if (row >= n*n) throw; if (column >= n*n) throw; return (row/n)*n + column/n; // '/' : integer division }

To verify a grid:

Empty the domains associated with each row Empty the domains associated with each column Empty the domains associated with each block For each row i For each column j Add the value of cell(i,j) to the domain of row(i) Add the value of cell(i,j) to the domain of column(j) Add the value of cell(i,j) to the domain of the block containing (i,j) End for End for For each row i If the domain of row(i) does not contain all 9 values: return false End for For each column j If the domain of column(j) does not contain all 9 values: return false End for For each block If the domain of the block does not contain all 9 values: return false End for Return true

To generate a grid to be filled by the user you simply generate a solution and remove some values. For example, 5 or 6 values per block. In some cases, the grid might have multiple solutions but that doesn’t matter, since in the end the verification function doesn’t check if the starting grid and the proposed solution match, it just checks if the proposed grid is valid.

Now all you have left is to code all of this ;-) If you’re motivated, you can easily see that the pseudo code I’m proposing works for n x n blocks of n x n elements (with n >=1 and not just n = 3).

In terms of implementation, you could for example use structures like this:

#include <vector> typedef std::vector<bool> domain_t; struct cell_t{ domain_t domain; // for generating the grid or for the solver unsigned value; }; typedef std::vector<std::vector<cell_t> > grid_t; 

What would have been hard, would have been:

1) having to code a solver. But it’s actually done very easily with a CSP model (see operational research courses for enthusiasts) which, like the method I just proposed, is based on domain reductions. It’s quite simple to check if the grid has one or multiple solutions (using a branching tree).

2) having to generate grids with a unique solution (but once the solver is coded, you just have to remove values and only allow their removal if the solution remains unique).

Good luck!

I agree with Niel, we also need to consider the candidate's capacity in question
not to say too much to scare him, I hope you understand.

A sudoku is quite complex to program... especially if you are not comfortable with programming...
Did you choose your project freely or was it imposed?

--
Utae Gamuza

For the creation of random grids, I don't know.

However, for the architecture, first you create a matrix (a 2-dimensional array) of the size of a grid (it may be variable if letters are also used).
Make an algorithm to check each row, each column, and each square, to see if each number is used exactly once, and only once.

Make sure that the values generated by the program cannot be modified by the user on their grid.

... it's a bit soft for a presentation ...

Personally, I chose "the game of life", it's not really a game but rather a pretty cool (and simplistic) simulation about bioculture. It's more complex to program than "guess the number" but definitely simpler than sudoku.
Type game of life into Wikipedia, you'll find the model for the simulation... personally, I had a lot of fun making it.

--
Utae Gamuza

Indeed, the Game of Life is quite good...
There's also Langton's ant which is pretty good (and easy)
https://fr.wikipedia.org/wiki/Fourmi_de_Langton

(but in my day, there was no need for that, you just had to ask to be included...)
--
Stop failing the Turing test!

[Irony mode activated] Oh yes, it sounds very simple for someone who has had little or no lessons in C++... [Irony mode deactivated]

I don't see how our responses are off-topic; we suggested (if possible) simpler projects for their level. A Sudoku remains quite a challenge, and not everyone is a programming whiz... you also need to tell me where I'm telling my life story...
Anyway, you can keep your pointless remarks (beginning of your message) and just focus on helping them... like we do.

See you!
--
Utae Gamuza

For the verification of the grid, I agree, it's easy, but that's not the point of the project.

For the creation of the grid, however, I do not agree, or maybe you expressed yourself poorly.
Your method allows for starting a grid, but often will not allow for finishing it.
Because it comes down to solving a sudoku by placing values randomly among those available...
It works at the beginning, up to a certain point.
Or else, your method consists of trying to create grids randomly until you happen to find a good one, which can take quite a bit of time...

As for generating a grid by removing values at random...
Not only do we risk generating grids with multiple solutions, but we also risk generating grids that are impossible to solve (or at least very, very difficult).

I do not agree either when you say that we do not answer the question.
An important part of the question is: "that I am really not gifted."
I did a BTS in management information (10 years ago), so I know the level.
I admit, upon re-reading, I misunderstood the question; I thought she was going to enter BTS, not take the exam, which explains my first answer.
Indeed, for a final exam, 'finding the number' is too simplistic (I programmed it on my calculator in high school), but, already for her, it allows her to get an idea of her level; if what is proposed to her seems easy, then, indeed, she can try to focus on something more complicated.

--
Stop failing the Turing test!

or else, your method consists of trying to create grids randomly until you get lucky and find a good one, which can take quite a bit of time...

Absolutely not. It's neither long nor incorrect. We simply choose a value at random from those still available for the cell. We restrict the set of available values so that the cells constrained by the value we install receive a value consistent with the grid's value in subsequent iterations.

For example, for a sudoku with n = 3, I initially have 9 values available for each cell. I pick a value between 0 and 8 (which gives me 9 values). Let's say I pick the value 6. I move 6 times in {0,1,2,3,4,5,6,7,8,9}, which corresponds to the value 6 that I am installing in the cell. So I remove the value 6 from the domain of the cells in the upper left quadrant, from the top row, and from the left column.

Next, I move to the cell immediately to the right. The 6 is no longer available (so there are 8 values left available). I pick a value between 0 and 7 (which corresponds to a sample of 8 values). Let's say I pick the value 6. I move 6 steps in {0,1,2,3,4,5,7,8,9} to choose my value, which is the value 7. Then I remove this value from the corresponding quadrant, row, and column cells. And so on.

Conclusion: we visit each cell once and only once; for each one, we take a random draw that systematically gives us an admissible value (and when the domain is reduced to one element, we don't even need to make a random draw, we know it's the only value we can install in the cell). In short, it's a polynomial algorithm, it’s efficient...

as for generating a grid by removing values at random...
not only do we risk generating grids with multiple solutions, but we also risk generating grids that are impossible to solve (or at least, very very difficult)

No, since you start from an admissible solution and you remove certain cells. There is therefore at least that solution. As for having multiple solutions, I've already explained how to avoid multiple solutions, but if you don't remove too many values, the grid will be constrained enough to only have one (or few) solution(s). In any case, even if there are multiple solutions it doesn’t matter since the verification method does not compare the solution that generated the grid with the solution proposed by the player.

I also don't agree when you say [...]

Well, the program fits in 100 lines and I’ve already given the structure of the code. As you can see, it’s just a few for loops, which should be one of the first things we learn in algorithms. The only difficulty of the problem was thinking about the algorithm, and we’ve covered that. And you’ve seen that there’s nothing miraculous about it.

Moreover, if we tell it the task is to generate a sudoku, then why digress to talk about other games? The purpose of the forum is to respond to a problem, not to contest the statement, right?

Good luck!

Nothing indicates that the subject was imposed: she clearly says "... I chose ...". Ideally, it is still better to take a topic compatible with one's abilities... It is preferable that at the end, during the presentation, the program works. I'm saying this in her best interest and at no point was I off topic...
I've seen too many people during my studies who chose a project that was too complex for them and who failed during the presentation!
Sudoku may seem easy for you to implement, but that's certainly not the case for everyone! If she's not sure of herself, as dna.factory says, she might as well test what she knows on a simpler project...

--
Utae Gamuza

a sudoku developers forum: http://www.setbb.com/phpbb/?mforum=sudoku

Personally, it was one of my first-year projects: Programming a Sudoku solver in C in two days.

It's not "that" complicated; you actually need to know how to play basic Sudoku well for your program to have good algorithms...

I personally walked around with a 3-dimensional array to store all my values.

So here is the outcome of the battle...

#include <iostream> #include <vector> #include <set> #include <cstdlib> #include <cassert> #define N 3 #define N2 N*N typedef std::set<unsigned> domaine_t; unsigned randint(unsigned max){ return (unsigned) (((double) rand()*(max+1))/RAND_MAX); } struct case_t{ domaine_t domaine; unsigned valeur; case_t(): valeur(0) { for(unsigned i=1;i<N2+1;++i) domaine.insert(i); } void supprimer(unsigned val){ domaine_t::iterator fit = domaine.find(val); if(fit != domaine.end()) domaine.erase(fit); } }; struct grille_t{ std::vector<std::vector<case_t> > data; grille_t(){ for(unsigned i=0;i<N2;++i){ data.push_back(std::vector<case_t>(N2,case_t())); } } void corriger(unsigned i,unsigned j,unsigned val){ assert(i < N2); assert(j < N2); // Remove val from row i and column j for(unsigned k=0;k<N2;++k){ data[i][k].supprimer(val); data[k][j].supprimer(val); } // Remove val from the square whose top left cell // is (i0,j0) unsigned i0 = i / N2; unsigned j0 = j / N2; for(unsigned i1=0; i1<N; ++i1){ for(unsigned j1=0; j1<N; ++j1){ data[i0+i1][j0+j1].supprimer(val); } } } void generer(){ unsigned val, k, rnd; for(unsigned i=0;i<N2;++i){ for(unsigned j=0;j<N2;++j){ const domaine_t & d = data[i][j].domaine; rnd = randint(d.size()-1); // Draw the value for the cell (i,j) // (the rnd-th value from the domain) domaine_t::const_iterator sit (d.begin()), send(d.end()); for(k=0;sit!=send && k < rnd;++sit, ++k); val = *sit; data[i][j].valeur = val; // Correct the domains corriger(i,j,val); } } } }; std::ostream & operator << (std::ostream & out,const grille_t & g){ for(unsigned i = 0; i < N2; ++i){ if(i%N == 0){ for(unsigned j = 0; j < N2 + N; ++j) out << '-'; out << std::endl; } for(unsigned j = 0; j < N2; ++j){ if (j%N == 0) out << '|'; out << g.data[i][j].valeur; } out << std::endl; } return out; } int main(){ // for(unsigned k=0;k<20;++k) std::cout << randint(9) << std::endl; grille_t grille; grille.generer(); std::cout << grille << std::endl; return 0; }

As you can see, I implemented exactly the algorithm I mentioned to you. You will be pleased, there is indeed a case I had not thought of. But since we have plenty of computer pros and the hardest part is done, I am sure you will find the right path (well, I know I didn't initialize the seed of the random generator).

Here is what it looks like:

------------ |847|691|352 |536|478|910 |192|350|476 ------------ |283|765|194 |674|932|580 |951|840|237 ------------ |725|183|649 |419|207|803 |368|509|721 

The 0s correspond to cells that could not be filled, typically the last one in the second row. In fact, this is due to the fact that when filling the cells of the last square, there are only two admissible values (9 and 1) among the three that should be placed (i.e. {1, 5, 9}. I am not a sore loser, so I humbly admit that I messed up on this point.

How to solve the problem: we need to maintain the domain associated with each square and ensure that when we insert a value into the grid, we do not run out of values for the remaining cells which, I admit, is not necessarily ultra-trivial. And that works out rather well because otherwise it would have been enough to copy this source to do the project for you. I admit that I don't have the mental strength to think too much about it tonight, but that's already a lead.

Regarding the point "what you mention is a solver": yes it resembles that and we don't really have a choice, but if you find another method, feel free to share it with us.

Regarding "write the pseudocode", it was already done in my first message.

Regarding your messages: I am happy to see the enthusiasm you put into defending your point of view and your honesty. Really. Now I think the goal is to move forward with the resolution of the problem, and I am expecting messages from you that are more constructive and that will advance the resolution of the problem (there's no point in flooding a discussion thread with a debate, private messages are meant for that). As far as I'm concerned, that's what I've tried to do, I await your contribution, especially since from what I understand, you are strong in computing. In short, impress me ;-)

Good luck.

I had tried to make one a while ago (during my "crazy" phase) and I really hit a wall with it, so I won't try again (just thinking about it gives me a headache)...
The "O" thing is exactly the flaw that dna.factory detected... now you understand more the difficulty of creating such a program.
--
Utae Gamuza

1) This is absolutely not what dna.factory announced; he didn't even understand that the algorithm was indeed generating a random grid. I'm referring you to his messages. At no point did he raise the issue with the algorithm I proposed. Moreover, if you followed the discussion, you will see that not everything I proposed is to be discarded. On the contrary, I even showed him that, indeed, to generate a grid, we had almost the equivalent of a solver.

2) He didn't propose the slightest constructive approach to help him solve his problem. He just acted like a know-it-all with "you won't make it, I'm the best haha." I'm still waiting to see the pro in action (and I say this sincerely, because dynamic pivot tables in Excel within a C/C++ program makes me chuckle).

3) I have nothing to prove, nor am I ashamed of anything. I acknowledge that the subject is more difficult than I initially suspected (see previous message). It doesn't bother me at all to admit that I was wrong. At least I tried to answer the question instead of acting like a know-it-all and filling the discussion with messages that serve no purpose. In the end, that's the only thing I've reproached him for. Honestly, who cares if he has a BTS in computer science? If he wants to share his life story, there are forums on CCM for that.

Rather than polluting this thread with childish and uninteresting discussions, I invite you, if you wish, to continue the debate in private messages; I would be delighted to respond.

With that, sincerely, good evening.

I understand perfectly :-)

Cool then, we're on the same wavelength... no matter whether you find it easy or not, what's important is whether it's doable for her.
--
Utae Gamuza

I'm going to be the dream breaker...
Forget about sudoku, you don't have the level...
It's more of a level for the end-of-BTS exam.

If you want to create a game program, start with 'guess the number I'm thinking of' (with higher, lower)
It's really the basics of programming, but at least it allows you to move forward slowly.

--
Stop failing the Turing test!