Solving the hardest Sudoku - part 2
JeanFrancoisPuget 2700028FGP Visits (4393)
My previous post on Sudoku described how a fairly simple OPL model could be used to solve a hard Sudoku problem. I ended the post this way:
What do you say?
I see, you're asking about the solution to the above Sudoku. Well, why not download CPLEX for free and run the above model to find out?
This post is a detailed tutorial on how to run that Sudoku model on a Windows PC using CPLEX. It also addresses an interesting challenge about using Microsoft Excel for defining the problem data and for publishing the solution. And, by the way, it also discloses the solution to the Sudoku problem...
I. Getting CPLEX Installed
First step is to get CPLEX (full product name is IBM ILOG CPLEX Optimization Studio) installed on your machine. There are basically three ways:
I guess have a slight preference for the third option, but all three options are perfectly legitimate. From now on I assume CPLEX has been installed on your local machine.
II. Creating an OPL project for Sudoku
Step 2 - Launching the IDE
Next step is to launch the OPL IDE that was installed as part of CPLEX. On my machine, a Windows 7 PC, it appears in the start menu under the IBM ILOG category.
If it is the first time you run it, then you will get a question about which workspace to use. Select where you want your files to be stored on your system. You can check the box so that you don't get the question each time you launch OPL. Here is my choice.
Step 3 - Creating a project
We then create a new OPL project, using the File menu on the top left, clicking on File > New > OPL Project:
This brings a window where we enter a project name. I have chosen to use "sudoku" as the project name. I also selected the check boxes beside "Add a default Run Configuration" and "Create Model".
Step 4 - Editing the model
After clicking on the "Finish" button we get ready to use IDE. The sudoku.mod pane is open, and we can type in the model described in the previous post.. As a matter of fact I simply cut and paste the model text from that post. I reproduce it here for ease of use.
Simply cut the text above and paste it in the sudoku.mod pane. You should get an IDE looking something like this.
Step 5 - Running the configuration
Now, let us look at the run configuration that was automatically created. You can expand it by clicking on the left arrow near to "Run Configurations", then click again on the left arrow near to "Configuration 1". The model we edited is part of it.
We run this configuration by right clicking on it. The following drop down menu appears, and you should select the "Run This" item.
A window pops up, asking if we want to solve the model We check the box near "Always save resources before launching" so that we don't get this question again, and we select OK, given we did not save our model so far.
The problem is then solved by CPLEX. This takes a short time, and the result is published in the IDE.
Step 6 - Looking at the solution
We can see it for instance by moving the mouse over the Decision Variables in the lower left pane. The result is then displayed as a 2 D array.
The solution is also available in one of the lower center panes. select the third one, and resize a bit the window. You should get something like the following
That's it! the Sudoku is solved.
III. Using Data Files
You now know how to create a project, how to create an optimization model, and how to solve it. We could stop this tutorial here, but let us look at two interesting extensions. The first one is that we can reuse the same model with different data, ie solve another Sudoku problem with the same model. One way would be to just edit the input array in the model. This would be fine, but what if we want to solve again the first problem we solved? We would need to again edit the input part of the model.
Step 7 - Creating a Data File
A better way is to leverage the separation between data and model in OPL. The model should contain what is stays true for all the Sudolu problems, while the data part should contain what is specific to one particular Sudoku problem. The latter is basically the input array. Let us create a data file for it. We do it in a similar way as for creating a model, using the File menu on the top left: we select File > New > Data.
As before, we are asked for a name.
Step 8 - Editing the Data File
After selecting Finish, we get a sudoku.dat pane we can edit. We cut and paste the input array to it. I reproduce the text below for convenience
input = [[8,
Note that we no longer need to specify the dimensions of the array nor the fact that it is an array of integer. We only provide the values, i.e. the input data. After editing the pane you should get something like:
Step 9 - Editing the Model File
We then need to edit the model, so that the input is read from the data file instead of being part of the model. We simply have to replace the actual values by three dots.
Step 10 - Editing the Run Configuration
Last step is to add the data file to the run configuration. There are various ways to do it. I like to drag and drop the sudoku.dat file to the configuration in the left pane. This yields the following question, to which we answer OK of course.
Step 11 - Running the Configuration
We then run the resulting configuration, as before
The problem is then solved, and we get the same solution as before. No surprise here. We can look at it s in Step 6 above.
What did we achieve? We have found a way to solve other Sudoku problems easily. Indeed, we simply have to create a new data file for each new problem. Then we create a new run configuration with the new data file and the same model as before. I won't show how to, it is a mere repeat of steps 7 to 10.
IV. Using MS Excel
I could stop the tutorial here, but I want to address an interesting challenge. In reaction to my tweet about my previous post I got this interesting answer by M. Colebrook. He has used Microsoft Solver Foundation (MSF) to express and solve the same Sudoku problem. I don't know MSF really, but it is clearly well integrated with Microsoft Excel, as one can use the latter to input data and output results.
This triggered my interest in using OPL bridge to Microsoft Excel. Let us see how it works in detail..
Step 12 - Creating an MS Excel File
I created the following Excel file and saved it in the sudoku sub directory of the workspace directory we selected in step 2. If you save the Excel file elsewhere then you'll need to provide the path to the file in the SheetConnection statement later on.
I added borders to make it look nice, but these aren't required to solve the problem. What matter is that the input area is defined by its top left corner and bottom right corner as "B2:J10". I also added borders in a second area that will receive the result or our computation. This second area is defined by "B12:J20". Note that I named the sheet "hard". That name will be referred to in OPL. The input area will then be ""'hard'!B2:J10" and the output area will be "'hard'!B12:J20" . We put extra single quotes around the spreadsheet name in case it contains blank spaces.
We can use the same file with several sheets, one per Sudoku problem, as long as we refer to sheets by their names.
Once the file is create we might want to close Excel. Indeed, in some circumstances, it is not possible for OPL to write to it as long as it is open in Excel.
Step 13 - Creating a New Data File
We then have to create a new data file. I decided to call it xls, but any name would be fine.
Step 14 - Accessing MS Excel
We then edit the xls.dat pane with three statements:
input from SheetRead(sheet, "'hard'!B2:J10");
The first statement opens a connection to the Excel file we just created. The second statement reads the input from it. The last statement writes the results to it once the problem is solved. Note that these statements refer to the areas by the name of the sheet we are using, and the top left/bottom right corners.
Step 15. Creating a New Run Configuration
Last step is to create a new configuration with the xls.dat data file and the sudoku.mod model file. One way to do it is to right click on the Run Configurations item on the left pane, then select New > Run Configuration.
We are then asked for a name, as usual. I kept the default name here, but we could have selected another name.
We then drag and drop the xls.dat file and the sudoku.mod file to it.
Step 16 - Running It
Then, we can run this configuration as before, by right clicking on it.
Then the problem is solved.
Step 17 - Looking At The Result
The result can be looked at exactly as in step 6 above. We can also open the Excel file again to see how it looks. As expected, the result has been published in the area we have defined in the SheetWrite statement.
We see that using MS Excel is quite straightforward. Note that we could use a relational database in a very similar way, using a new data file with few statements.
Let us recap what we have done. We have learned how to create:
We have learned how to solve problems, via run configurations. Last, but not least, we have also learned how to use Excel for input/output.
There is much more to OPL than the above example, and if you want to learn more you can use the resources available on the right pane of the IDE.