| Sudoku | |
|---|---|
| Description: |
This is an attempt to make a fast sudoku solver / generator. I've started using
vectors of vectors of vectors of vectors... well, you can imagine. So, now I'm
using the super-simplified version of an algorithm called spin glasses,
which is a matrix of spins and what matters is the dynamics
of the whole matrix and not the value of each cell. As you can imagine, it can
save a lot of time...
The second part, is the generator, which needed the solver to check if it's solvable (also it needed to be fast, otherwise I won't be able to generate new boards before year 3000). I still don't have a good idea to generate faster than the traditional generators, if you have one feel free to sugest. My first guess will be to use spin glasses also.
|
| Algorithms: |
Spin Glass: The spin glass is a physical model created to solve complex
problems (much more complex than sudoku puzzles) related to complex dynamic
structures (such as magnetic fields on glass). The complexity comes from the fact
that such system is not linear and in most cases are NP-complete or even
non-computable.
Wikipedia have a brief description about it and for this application it should suffice. Spin glass can also be used for neural networks and for other non-exact algorithms. Spin Cube: The spin cube is a simplification of the spin glasses in the matter that it does not have any kind of dynamics by itself, it only fill the values and takes simple sums into account to know what cells have a solution and what don't. Every time you 'set' a value on the board it fills with -1 every cell the 'set' invalidates as you can see on the figure below:
As every dimension have 9 cells wide, if you have a sum of -8 means you have 8 cells with -1 and one with zero, which in our case is the solution.
|
| Download: |
Source code: here
|
| Rengolin | This page was created using Vim |
