• Post Reply Bookmark Topic Watch Topic
  • New Topic

Trying to implement multi threading to a sudoku solver

 
lewis manuel
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So before I get into specifics, here is my main single threaded Sudoku solver class.



and here is where I call it.



Now this time I going to show the naiveSolver again but with some tweaks and I will explain those tweaks.





So the first thing right off the back is that I'm saying that the naiveSolver class implements callable because in the end I want it to return true or false to see if it solves the puzzle or not. So ultimately the call method will return a boolean(notice that I have not implemented the call method yet because there is a design problem that I've been having with that and I'll talk about that later). Notice that I have added an extra variable called rowThread. The reason for this extra variable is because this is how I envision the program will work.

Take for example this Sudoku board.



Each array(row) will be assign to a thread and will try to finish that part of the array(this is what index < board.GRIDSIZE means in the new solver). This means that each thread will start working in new row each time I submit a task. Here is some pseudocode on what I ultimately want to do.





The last problem I have is a design problem. I need to implement the call method but the call method does not accept any arguments while my runNaiveSolver method does and that is the method that I want to call in my call method. How can I remedy this situation without jumping through too many hoops to get this to work?



Now from what I can see, there should not be any problems with threads accessing an array that they are not working on(mainly because I assign them a row to work on and that is the only row they can insert a value in). This means I should not see anything along the lines of a race condition. If you see any more potential problems that I'm not seeing, please leave them in the comment section.
 
Stephan van Hulst
Bartender
Posts: 6646
90
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Normally you pass arguments to tasks by creating a new type for the task, and providing the arguments via constructor parameters. You can refactor your NaiveSolver by passing the board and the row index in its constructor, and then have the call() method just do whatever the runNaiveSolver() method is doing now.

Please don't use raw types, you should implement Callable<Boolean>, not Callable.
 
lewis manuel
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:Normally you pass arguments to tasks by creating a new type for the task, and providing the arguments via constructor parameters. You can refactor your NaiveSolver by passing the board and the row index in its constructor, and then have the call() method just do whatever the runNaiveSolver() method is doing now.

Please don't use raw types, you should implement Callable<Boolean>, not Callable.


Just so that I understand what you mean by do not use raw types, it would make more sense to do it like this correct?

 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 15759
74
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, except that you cannot use primitive types such as boolean as type parameters. That's one of the reasons we have wrapper classes, such as java.lang.Boolean. Use that instead of boolean for type parameters:
 
lewis manuel
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Alright I'll try to do as much as I can and will report back if I get stuck.

Edit: Quick question, should I make numberOfSteps as a static variable? The reason I think I should is because if I don't then numberOfSteps is only going to reflect the number of steps it took to finish the row and not the entire board because numberOfSteps is an instance variable.
 
lewis manuel
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
All right jesper I took your advice and this how far I've progress. If you see any mistakes, please let me know.

Note: I changed the name simply to reflect what it actually is.

Edit: I'm wondering if instead of passing the entire board as argument, I should only pass in the row that it will change.

 
Stephan van Hulst
Bartender
Posts: 6646
90
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your solver is just a task, each task is run by one thread, so don't call it MultiThreadedNaiveSolver. NaiveSolver is just fine.

Never use static variables. Global state is BAAAAD. Seriously. The only time you use the static keyword for somethign other than constants is when you have a really really really good reason for it, and you can explain your reasoning.

Make your board field final; if you want to pass a row instead of a board and an index, make the row final instead.

Check if the constructor arguments are valid. Your task is not valid if the board is null, for instance, or if the row index is outside the bounds of the board. Throw appropriate exceptions.

Your call() method throws an Exception. Why? Only declare exceptions if you expect to propagate them.
 
lewis manuel
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey Stephan, thanks for your reply. Let me response to your points.

1.) I changed the name because I wanted to compare both classes and see how long it would take for each solver to finish the puzzle and I didn't really want to change the name to something like NaiveSolver2 or anything else like that.

2.) I've explained with very good reason(at least I think) why I chose to make numberOfSteps static. If I don't make it static, then once I create several tasks, then each thread in that task would have their own instance of the variable numberOfSteps. This does not make sense as there should only be one instance of this variable so that once we are done, we can see the total number of steps it took to solve the puzzle.

3.) Why make the board or the row final if some of the values in the board, that ones that are not predefine, are going to change. If I declare it as final, I won't be able to change any of the cells that have the value 0.

4.) There is no way it could be null at this point because in a another class I instantiate the sudokuBoard class with some values such as how many rows and columns does the board have, how big is the grid etc. So at this point, the object has anything but null.

5.) I think the reason why you see an exception is because my IDE auto completed and inserted a throw exception and I did not really catch that but you have a point here.

I would very much appreciate a counter response to all of my points.
 
Stephan van Hulst
Bartender
Posts: 6646
90
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
lewis manuel wrote:1.) I changed the name because I want to compare both classes and see how long it takes for solver to finish the puzzle.

Fair enough.

2.) I explained with very good reason(at least I think) why I chose to make numberOfSteps static. If I don't make it static, then there would be several tasks run by N threads and thus they would have their own instance of the variable numberOfSteps. This does not make sense as there should only be one instance of this variable so that once we are done, we can see the total number of steps it took to solve the puzzle.

Sadly this reason is not good enough. What you can do instead is make your solver a Callable<Optional<Integer>>. The return value indicates whether or not the row could be solved, and if so, the number of steps. The task that is responsible for running all these sub-tasks tallies the total number of steps. Alternatively, you can store the number of steps in an instance field of the task, and the main task can access it through a getter after the task has finished, and again add them all together.

3.) Why make the board or the row final if some of the values in the board, that ones that are not predefined, are going to be changing constantly. If I declare it as final, I won't be able to change any of the cells that are 0.

For reference types, the final keyword makes the reference final. That means that you can't reassign the row/board field. It still allows you to change the contents of the object that the reference points to.

4.) There is no way it could be null at this point because in a another class I instantiate the sudokuBoard class with some values such as how many rows and columns does the board have.

Except that your class is public, and so is the constructor. Anyone can call it and pass anything. If you didn't intend this, make the class private. Otherwise, check your parameters. This will allow you to find bugs much earlier, which makes fixing them much easier.
 
lewis manuel
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan I agree with your second point and I'm going to make a getter method for the instance variable numberOfSteps and add the total to a new instance variable called totalNumberOfSteps and print that one out after I've added up the numberOfSteps each thread took(This is of course once a thread has completed its task). Seems like the easiest way to go about it.

I now agree with your third point and I guess I had a misconception of what final was really all about.

In regards to your fourth point, here is where I will be using my solvers to test them.



So it does not make sense to make the MultiThreadNaiveSolver class private because I do use it in this class.



Here is how the class looks now

 
Stephan van Hulst
Bartender
Posts: 6646
90
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, even if your SudokuPuzzle is public, you can still make your solver task package private if you put it in the same package. Try to limit visibility, unless you have a good reason to expose the solver class to the outside world.

Even if it's package private, it's a good habit to check your parameters in all methods and constructors that are not private, which will expose bugs much sooner. I'm not sure about you, but I never trust myself when I'm coding
 
Stephan van Hulst
Bartender
Posts: 6646
90
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It doesn't make sense to put both totalNumberOfSteps and numberOfSteps in one class.

A Callable represents one task that does exactly one thing. If your solver is responsible for solving a row, it can't be responsible for solving an entire board. Therefore, it can't know the total number of steps it took to solve the entire board.

You should make a class that is responsible for solving the entire board (SudokuPuzzle could do this!) and that class spawns a new task for each row. The class that is responsible for solving the entire board should contain the totalNumberOfSteps field.
 
lewis manuel
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Alright, I have three solvers I plan to test and I have four additional class called Sudoku, SudokuBoard, timer and SudokuPuzzle. So you are saying that those three solvers should be in a package called SudokuSolvers and those other four in a package called sudoku. How about that?
 
Stephan van Hulst
Bartender
Posts: 6646
90
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sure, sounds good. You should call the solvers package something like sudoku.solve, which is closer to the accepted naming conventions. I'm not sure if you need the SudokuPuzzle class, unless that's where you're planning on putting the main() method.
 
lewis manuel
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Not exactly. Here is what I mean.



This is in my Sudoku class and that is where my main is at.

Your probably thinking why is this not in the main class(Sudoku). The reason why I did not do so is because my sudoku class does three things. Asks the users input on the dimensions of the board and validates it, reads the board from a file and validates it as much as it can(it assumes that each integers is delineated by a space) and then it plays sudoku. So you can see here that this class does not consider its self in solving the puzzle. That is delegated to another class(SudokuPuzzle).
 
Stephan van Hulst
Bartender
Posts: 6646
90
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So what does instantiating SudokuPuzzle do? Can't you replace the contents of playSudoku() with the contents of solveSudoku()? It seems like adding the extra class is just noise.

Alternatively, you can just add a solve() method to the SudokuBoard class, and call that from your Sudoku class.
 
lewis manuel
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Now that you mention it, it does make much more sense to move the solve method to the SudokuBoard class.
 
lewis manuel
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks stephan, your idea worked. I gave the sudokuBoard class the responsibility of printing of out the totalNumberOfSteps it took and so I did not need exxtra instance variables in the other sudoku solver classes and I also got rid of the sudoku puzzle class. Here are the main changes.







One last thing, I've never made a package private class in netbeans. Is it as easy as making a new package, placing the classes that I want to privatize in the new package and leave the others alone and call up the method solve?
 
lewis manuel
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So I've eliminated the public keyword in all but my main class and board class so it can default to package private and lower its visibility to other classes outside of the sudoku package.
 
lewis manuel
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
After making a few design changes, here is how both classes look now.





So stephan, I would like to know which of these thread pools are more appropriate for my situation: fixedThreadPool or cacheThreadpool.

Edit: I was also thinking that the size of the thread pool should be equal to the size of the board.
So if we have a 4 x 4 board, then we would have 4 threads in total(one for each row). Is that a good idea?
 
lewis manuel
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So I've made a little bit of progress in changing the solveSudoku to run in a multiThreaded like manner and this is what I came up with.



What this method is doing now is that it creates a thread pool that is the size of the board. After each thread is done, they will return either true or false. Then I loop through the arrayList that contains the final result of each thread and if I find one that is false, that means we could not solve the puzzle.
 
lewis manuel
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My output for this is that it returns false. As in it could not solve the puzzle even though my single threaded naive solver solved it.

Here is how the MultiThreaded naive solver class looks like



What possible problems could there be occurring?
 
Stephan van Hulst
Bartender
Posts: 6646
90
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Set the size of the thread pool to 1 and see if it works. If so, the problem is caused because you have race conditions.

You can't access mutable data structure concurrently without proper synchronization.

Some other comments:

  • Sudoku, SudokuBoard and your solver can be final classes.
  • The solver constructor, solveSudoku(), SudokuBoard constructor and setValue(), are publicly accessible and aren't fail-fast. You really should check their parameters. For instance, what happens when you use setValue() with a value that's outside the allowed range?
  • It's not clear how your solving algorithm works. Document what you expect naiveSolver(int) to do on a single execution. This is specially important for recursive method definitions.
  • You should use verbs for method names. naiveSolver is a noun, not a verb.
  • The naiveSolver() method uses a lot of nested conditionals. Break this method up in smaller methods to avoid nesting too many levels.
  • Assuming that your sudoku board should contain a grid of size rows x columns, why are you making it gridSize x gridSize?
  • Using multiple threads to speed up operations is only useful if you have the cores to support them. Therefore, the number of threads shouldn't depend on the size of your problem, but on the number of cores in your system.
  •  
    lewis manuel
    Ranch Hand
    Posts: 64
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Well the way I have set up it has to be. The whole point is that a thread will be given a row to work on. If there are 4 rows, then there are 4 threads. So the number of threads are dictated by the size of the problem. So using one thread would not work because it would only check the first row.

    1.) I agree with this
    2.) Impossible because I already checked that before starting the game. It is guaranteed that all the values will be between 1 and N because I explicitly checked for that(This is for setValue()). Also the solver constructor is package private because it does not have an indentifer only class.
    3.) The algorithm uses recursion and backtracking to solve the puzzle. We always start at row 0 column 0 and first check if the value is not zero. If it is not, then skip because that value was already there. If not, then you have N possibilities to check. N being the size of the grid. In a 4 *4 board, we would have 4 possibilities. In general, we are looking for partial solutions and if we have visited every cell and filled them with a value, then it means that we have found a solution. If at any point we find a value that doesnt work, we try the next possibility. If none of them work, then we backtrack to previous cell.
    4.) Fair enough but what else can I name? I have a helper method called runNaiveSolver. If I change it to something, It would just look weird.
    5.) I plan to do that later but I want to get the multithreading part to work.
    6.) because row and column are actually the subgrid size. GridSize * GridSize is the true size of the grid.

    Edit: Alright, I have changed those classes to final, removed unnecessary if and else conditionals and gave those name action verbs.
    Edit2: I made some additional changes so that it would work with one thread and it worked perfectly. Once I added another thread, then it returned false. Meaning it could not solve the puzzle.
     
    Stephan van Hulst
    Bartender
    Posts: 6646
    90
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    lewis manuel wrote:Well the way I have set up it has to be. The whole point is that a thread will be given a row to work on. If there are 4 rows, then there are 4 threads. So the number of threads are dictated by the size of the problem. So using one thread would not work because it would only check the first row.

    No, this is a common misunderstanding. If there are four rows, there are four tasks. Four tasks can be solved by one, two, three or four threads. Think of multi-threaded programming as a line of people waiting for some office clerks to help them. The people represent tasks. The clerks represent threads. The larger your problem becomes, the more people get added to the queue. The more threads you have, the more clerks there will be to help people. You can design an application for concurrency, but still run it with one thread.

    2.) Impossible because I already checked that before starting the game. It is guaranteed that all the values will be between 1 and N because I explicitly checked for that.

    No, you can't check this, because the methods are public. You don't know which other code is going to call your public methods, by virtue of them being public. You should treat methods that are not private as if everyone in the world can access them, so you need to be prepared that people can call your methods with invalid arguments. Not even just other people, it's perfectly possible that you accidentally input a wrong argument, and don't catch it until much later. This is not a theoretical problem. These message boards are full with questions about NullPointerExceptions and so on, because people don't check method parameters and it manifests itself as a bug that pops up in a part of the code that's very far away from the part of the code that needs to be fixed.

    Another thing, why is incrementStep() a public method on SudokuBoard? Should any class anywhere be allowed to increment steps? It makes more sense to have solveSudoku() just return the number of steps when it is done. On that note, if I have boardA and boardB, what does it mean to call boardA.solveSudoku(boardB)?

    Furthermore, if isBoardValid() is meant to check whether a the board contains a contradiction, why don't you just perform this check in setValue() which rejects the change if it makes the board contradict itself, and returns a boolean that says whether it has successfully set the value? That way, a board will *always* be in a valid state.

    6.) because row and column are actually the subgrid size. GridSize * GridSize is the true size of the grid.

    This is not clear from the code, I'm thinking you should give your identifiers more descriptive names. Just a couple of observations:

  • rowThread is not a thread. Name it something like rowIndex, or maybe just row.
  • index doesn't say what it indexes.
  • rows doesn't represent rows. Name it subgridHeight. Similarly, name columns subgridWidth. The same goes for the getters.
  •  
    Stephan van Hulst
    Bartender
    Posts: 6646
    90
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    lewis manuel wrote:Edit2: I made some additional changes so that it would work with one thread and it worked perfectly. Once I added another thread, then it returned false. Meaning it could not solve the puzzle.

    Yes, this means that your tasks are not synchronized. You can solve this problem by making SudokuBoard thread-safe.
     
    lewis manuel
    Ranch Hand
    Posts: 64
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    How exactly? By making setValue a synchronized method?
     
    Stephan van Hulst
    Bartender
    Posts: 6646
    90
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    No, nothing quite so easy. Synchronizing only write access to your board doesn't prevent other threads from seeing "stale values" when they use getValue().

    I suggest you read a tutorial on synchronization, it's a very complex subject.
     
    lewis manuel
    Ranch Hand
    Posts: 64
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    You said that solveSudoku() should just return the number of steps it took to solve the problem but that would mean changing it from a boolean to an int. So it is not that easy of a change.
     
    Stephan van Hulst
    Bartender
    Posts: 6646
    90
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Sorry, I misread. Still, it should not be possible to increment the number of steps from the outside.

    solveSudoku() is what does the solving, so it knows how many steps it took. You can just set the field from that method, instead of having to increment the field from the outside.
     
    lewis manuel
    Ranch Hand
    Posts: 64
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Now that I agree with.
     
    lewis manuel
    Ranch Hand
    Posts: 64
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I've added this static final variable to the class that is calling the solveSudoku method

    private static final int NUMOFTHREADS = Runtime.getRuntime().availableProcessors();

    This should coincide with your idea that the number of threads should equal the number of processors available.
     
    lewis manuel
    Ranch Hand
    Posts: 64
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    One more thing, I can't change what setValue because in another class, I'm reading in the file that contains the board and use the method setValue to insert the value that I read from the board.
     
    Stephan van Hulst
    Bartender
    Posts: 6646
    90
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    So why not edit that class to reject the file if it describes an invalid board?
     
    lewis manuel
    Ranch Hand
    Posts: 64
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Because I assume that the board they have given me is valid from the start. Only once I start solving do I check if it's invalid. I'm doing this for simplicity sake.
     
    lewis manuel
    Ranch Hand
    Posts: 64
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Do you know what types of synchronization I would have to use to make it thread safe. I'm asking if you can pinpoint me to concepts in synchronization that I can read to help me figure this out.

    Here is how the classes look:





    This is a method in the main class(Sudoku.java) that solves the puzzle using multithreading

     
    lewis manuel
    Ranch Hand
    Posts: 64
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    After a lot of pain and struggling, I finally it got to work. Here is one solution.

     
    Stephan van Hulst
    Bartender
    Posts: 6646
    90
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    lewis manuel wrote:Because I assume that the board they have given me is valid from the start. Only once I start solving do I check if it's invalid. I'm doing this for simplicity sake.

    Well, if it's valid from the start, then there's also no reason you can't edit setValue() to ensure the board will remain in a valid state, because it won't affect the file reading process.

    Your code will become a lot simpler if you can make certain assumptions. If your setValue() method ensures the board will never be in an invalid state, then you can completely remove the isBoardValid() method, because it's already guaranteed.

    lewis manuel wrote:After a lot of pain and struggling, I finally it got to work.

    I don't think you're using concurrency correctly. You aren't actually splitting the work. Each task you create does the exact same thing: solve the entire board. I'm pretty sure this solution is slower than your single-threaded application.

    You must split the work in several different tasks. It doesn't matter if they are 2 or 100. For instance, you can have a type of task that solves one of the rows, and then create a task for every row.

    Again, tasks are unrelated to threads. Don't create a task per thread. All you need NUMOFTHREADS for is to initialize the executor service, not to create tasks.
     
    my overalls have superpowers - they repel people who think fashion is important. Tiny ad:
    the new thread boost feature brings a LOT of attention to your favorite threads
    https://coderanch.com/t/674455/Thread-Boost-feature
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!