turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Navigation
- Tecnomatix
- Forums
- Blogs
- Knowledge Bases
- Groups

- Siemens PLM Community
- Tecnomatix
- Plant Simulation
- Solving Sudoku Puzzles

Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-20-2014 11:11 AM

The objective is to fill the 9×9 grid with numbers from 1 to 9 such that each row, column, and 3×3 boxes contains each number exactly once. For a particular puzzle some pre-defined hints are given.

We want to develop a simple algorithm for solving such a **Sudoku** problem that can be implemented by *SimTalk in Plant Simulation*. An appropriate data structure is a table with 9×9 cells. The cells are

The basic idea is a recursive procedure with a parameter of the described data structure. If there is an empty cell then the puzzle is unsolvable. Each recursive procedure needs such an exit condition. For a cell with at least 2 possibilities the procedure is recursively called with all possible values. A corresponding subroutine reduces the sets of possibilities of the other cells. If all cells have exactly one possibility a solution is found.

The model file for Plant Simulation 11 TR 2 contains some example puzzles. Press the button and select a **Sudoku** problem containing in the collection. You can early terminate the algorithm by pressing again the button. Otherwise the algorithm finds all possible solutions.

The maximal depth of the recursive calls of the recursive procedure describes the complexity of the problem. But this description depends on the algorithm and its implementation.

For an unique solution 17 hints seems to be necessary. Note that 77 hints are not enough for an unique solution.

**References**

Delahaye, Jean-Paul: *The Science Behind Sudoku.* Scientific American **294** (2006), 80-87.

Krawitz, Björn (personal communication 2006)

2 REPLIES

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-20-2014 11:17 PM

It's great!

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-26-2016 09:45 AM

Nice one, thank you Peter!

I could not resist and had to tamper with it a bit I should say, I was not trying to "improve" it, I only wanted to see whether some checks that I do as a human when solving Sudokus can speed up the "brute-force" algorithm

I've added some checks to fix certain cells before going into deeper recursions. I've walked through each column and row and checked whether I can find a number that appears in only one list of possible cell-values in that column/row and then I fixed that cell to this number.

This reduces computation time and also the requried call-depth, especially for more complex puzzles (for puzzle B2: down from 104s to 14s and from 40 recursions to 30).

And I've realized: It's great (more? ) fun for me to use Plant Simulation for solving Sudokus than solving them manually ^^

____________________________________________________________

Alex Dilg, Consultant at**Sim**Plan AG (www.SimPlan.de)

This post was good and/or helpful to you? Please provide some Kudos, thank you!

Alex Dilg, Consultant at

This post was good and/or helpful to you? Please provide some Kudos, thank you!

Follow Siemens PLM Software

© 2018 Siemens Product Lifecycle Management Software Inc