Programming assignment - sudoku solver

New to LiquidPoker? Register here for free!

Forum Index > Poker Blogs

Almebeast Sweden. Mar 04 2011 06:35. Posts 797

There seems to be quite a few programmers around here, so I am writing this blog to get a few tips and comments on the ideas I have concerning this assignment. I am supposed to create a sudoku solver. If you dont know what sudoku puzzles are just google it. The only constraints are that I have to program in C and use a parallel algorithm with pthreads. I'll be happy if I can create something that works, but I obviously want to make the solver as fast and efficient as possible. I think this is an interesting enough assignment. I don't know if this is seems ridiculously easy to an experienced programmer but I've only been programming in C for about a month so it seems like a nice challenge for me.

So the first idea that comes to mind is some kind of brute force algorithm where you start by trying to put a 1 in the first empty cell. If 1 cant be in that cell because there already is a 1 in the same row/column/subsquare you try 2 and so on until you find the lowest number that fits in that cell. You then move to the next cell and repeat the procedure. Whenever you encounter a cell where no number fits (this means some of the numbers you already put in are wrong) you backtrack and try to put a larger number in the previous cell.

To parallelize this algorithm I am thinking I could start a new thread whenever I put a number in a cell, for example if 1,3,5,8 all fit in the first cell I would create 4 new threads, one for each possible number. If I could do that for every cell then I would never have to backtrack since every possibility is being taken care of. But this will probably create a very large number of threads.

Question: Is there a limit to the number of threads you can create?

Even if you can create a lot of threads this might not be an efficient approach since every thread will have to keep its own copy of the board since every thread tries different numbers. If the number of threads escalates then so does the memory usage

Im considering initially sorting the cells after how many "clues" there are for each cell, i.e how many given numbers there are in the same row/column/subsquare. Instead of attacking the cells from top left to bottom right you could then attack them in order of clues, starting with the one with the most clues. That way you wont have to create as many threads, since a lot of numbers aren't possible for the first cells.

So as you probably noticed I am in a very early stage of this project. I have until March 28. Please post comments/tips/questions. In the unlikely event that people seem interested in this project I will post updates as I move along.

0 votes

After all is said and done, more is said than done.

kingpowa France. Mar 04 2011 07:13. Posts 1525

Last day, I was in a train seeing lots of people playing sudoku which I really consider lame on a logical point of view. So I started wondering about the math which are behind this puzzle. And how it could be solved. Fact is, it is not as easy as I thought. (Actually, the interesting part about math, is on the generation of the grid, existence of the solution, identifying solutions...)
You will obviously find a tons of algorithms which solve sudoku on the internet.

Using your idea, I guess one of the easiest way to solve a simple sudoku would be to assign a table/chart (not sure of the word) to each cell, in this chart you could put the numbers still available. For example, for a X(i,j) cell, if there is already a 5 and a 6 in the column j, a 1 in the row i, and a 2 and a 3 in the square where the cell is, your table/chart would be [4,7,8,9]. repeating this to each cell. When there is only one value in a table/chart, that's the unique one, and it gives you more clue to reduce others.
This one would be quite easy to apply but is obviously quite limited cause lots of sudoku can't be solved this way.

Sorry if I'm not really clear, but I will follow and maybe give some ideas on this.
GL

sorry for shitty english.

boreHM Netherlands. Mar 04 2011 07:22. Posts 1595

The amount of threads you could create far exceeds the amount of threads that would be useful to create.

For example 1000 threads could "easily" be handled by a modern desktop computer. But in hardware there's probably only 4 cores (with hyperthreading it could show as 8 cores) in your CPU. Each of those cores (or "hyper"threads) can only run one thread at a time.

In practice you usually go for about 2 times the amount of processors (or cores/threads) in your system. I don't exactly know good hyperthreading works, but on a modern quad-core processor I'd run with between 8 and 16 threads.

On the other hand, if this is an assignment for a parallel programming course, you'll have to assume the PRAM model. In this model (since it's only theory) there is no limit to the amount of threads you can have or that can run simultaneously.

Almebeast Sweden. Mar 04 2011 11:54. Posts 797

On March 04 2011 06:13 kingpowa wrote:
Last day, I was in a train seeing lots of people playing sudoku which I really consider lame on a logical point of view. So I started wondering about the math which are behind this puzzle. And how it could be solved. Fact is, it is not as easy as I thought. (Actually, the interesting part about math, is on the generation of the grid, existence of the solution, identifying solutions...)
You will obviously find a tons of algorithms which solve sudoku on the internet.

Using your idea, I guess one of the easiest way to solve a simple sudoku would be to assign a table/chart (not sure of the word) to each cell, in this chart you could put the numbers still available. For example, for a X(i,j) cell, if there is already a 5 and a 6 in the column j, a 1 in the row i, and a 2 and a 3 in the square where the cell is, your table/chart would be [4,7,8,9]. repeating this to each cell. When there is only one value in a table/chart, that's the unique one, and it gives you more clue to reduce others.
This one would be quite easy to apply but is obviously quite limited cause lots of sudoku can't be solved this way.

Sorry if I'm not really clear, but I will follow and maybe give some ideas on this.
GL

You are very clear I think. I think the easy implementation that you are suggesting is very similar to the way most people solve sudokus by hand. I really want my solver to be able to solve all sudokus with existing solutions though. As for sudokus with multiple solutions I think it's OK if it finds one solution.

After all is said and done, more is said than done.

Fudyann Netherlands. Mar 04 2011 13:15. Posts 704

You need to know more about the math of sudoku to be able to make a good solution.

Pure bruteforce sounds good to me if you don't.

Almebeast Sweden. Mar 05 2011 06:08. Posts 797

On March 04 2011 06:22 boreHM wrote:
The amount of threads you could create far exceeds the amount of threads that would be useful to create.

For example 1000 threads could "easily" be handled by a modern desktop computer. But in hardware there's probably only 4 cores (with hyperthreading it could show as 8 cores) in your CPU. Each of those cores (or "hyper"threads) can only run one thread at a time.

In practice you usually go for about 2 times the amount of processors (or cores/threads) in your system. I don't exactly know good hyperthreading works, but on a modern quad-core processor I'd run with between 8 and 16 threads.

On the other hand, if this is an assignment for a parallel programming course, you'll have to assume the PRAM model. In this model (since it's only theory) there is no limit to the amount of threads you can have or that can run simultaneously.

Very good info, thanks a bunch. So if I find it convenient to create a lot of threads I can do it, but obviously the processors will not be working on all of them simultaneously. FWIW my university gives me access to a system of 64 cores, and yes this is an assignment for a course called Programming of parallel computers.

After all is said and done, more is said than done.

wcezxx . Mar 05 2011 11:08. Posts 3

yes just try it

boreHM Netherlands. Mar 07 2011 08:13. Posts 1595

Okay well you probably have had some lectures about scalability then.

Considering a 64 core system I would try anything between 64 and 256 (maybe 512 to see performance going down) threads I think. I have a similar course running right now. In our report we also have to compare the results of running with different amounts of threads. The algorithms we have to implement do not have to be practically the fastest one, but they need a certain (theoretical) time complexity in the PRAM model.

You can PM me to exchange IM addresses if you want to discuss this more.