142 lines
5.7 KiB
Markdown
142 lines
5.7 KiB
Markdown
# Sudoku Funpark
|
|
Creating worlds most inefficient Sudoku solver, by trying every option, without any smart approach.
|
|
|
|
_(This was a learning project to get a better grasp of Golang. But more important; It was fun to do!.)_
|
|
|
|
## Goals
|
|
* Create the most inefficient Sudoku solver imaginable
|
|
* Be a learning experience for the Go programming language
|
|
|
|
I wrote [a blog post](https://blog.ligthert.net/posts/exploration-fun-and-process-cycles-of-sudoku/) about this.
|
|
|
|
## Features
|
|
* Worlds least efficient Sudoku solver
|
|
* Ability to assign a number of CPU cores to this task
|
|
* Split workloads among several computers
|
|
|
|
## Usage
|
|
To use the sudoku solver, run the binary with all the `-row` parameters available. Use other parameters to tune our output or CPU usage.
|
|
```
|
|
Usage of ./sudoku-funpark:
|
|
-numcpu int
|
|
Number of CPU cores to assign to this task. (default 12)
|
|
-output string
|
|
Type of output. 'human' for human readable. 'flat' for flat as stored in memory output. 'json' for JSON output. (default "human")
|
|
-part int
|
|
Process part x in n parts. Cannot be lower than 1, or higher than specified in split. (default 1)
|
|
-print string
|
|
'short': normal output;'long': normal output with timestamps; 'silent': Only print the results; (default "short")
|
|
-row1 string
|
|
1st row of the sudoku puzzle. (default "000000000")
|
|
-row2 string
|
|
2nd row of the sudoku puzzle. (default "000000000")
|
|
-row3 string
|
|
4rd row of the sudoku puzzle. (default "000000000")
|
|
-row4 string
|
|
4th row of the sudoku puzzle. (default "000000000")
|
|
-row5 string
|
|
5th row of the sudoku puzzle. (default "000000000")
|
|
-row6 string
|
|
6th row of the sudoku puzzle. (default "000000000")
|
|
-row7 string
|
|
7th row of the sudoku puzzle. (default "000000000")
|
|
-row8 string
|
|
8th row of the sudoku puzzle. (default "000000000")
|
|
-row9 string
|
|
9th row of the sudoku puzzle. (default "000000000")
|
|
-split int
|
|
Split the tasks in n parts. This depends on the availability of the first row. (default 1)
|
|
```
|
|
|
|
Instead of using the 3x3 blocks with 3x3 digits, it uses horizontal rows from top to bottom.
|
|
|
|
|
|
## Example
|
|
To see the solver in action, run the tool with the following parameters.
|
|
|
|
For a short running (~14 seconds) example:
|
|
> $ ./sudoku-funpark -row1 769104802 -row2 154800060 -row3 832700154 -row4 600900328 -row5 045328670 -row6 328670945 -row7 597410280 -row8 006283090 -row9 200590006
|
|
|
|
For a long running (~1 hours 15 minutes) example:
|
|
> $ ./sudoku-funpark -row1 769104802 -row2 154800060 -row3 002700150 -row4 600900308 -row5 045328670 -row6 328670945 -row7 597410280 -row8 006283090 -row9 200590006
|
|
|
|
The outpot (of the short running parameters) will look something like this:
|
|
```
|
|
./sudoku-funpark -row1 769104802 -row2 154800060 -row3 832700154 -row4 600900328 -row5 045328670 -row6 328670945 -row7 597410280 -row8 006283090 -row9 200590006
|
|
Loading blocks... Done! (38.957376ms)
|
|
Populating blocks... Done! (92.087174ms)
|
|
Number of (potential) solutions: 26542080
|
|
Validating solutions
|
|
Processing: 8% (2131893/26542080); Rate: 2131884/sec for 1.000028115s; Time left (est.): 11s
|
|
Processing: 16% (4292163/26542080); Rate: 2160219/sec for 1.000087826s; Time left (est.): 10s
|
|
Processing: 24% (6438334/26542080); Rate: 2146157/sec for 1.000017364s; Time left (est.): 9s
|
|
Processing: 32% (8529362/26542080); Rate: 2090965/sec for 1.000367121s; Time left (est.): 8s
|
|
Processing: 40% (10737065/26542080); Rate: 2207530/sec for 1.000072427s; Time left (est.): 7s
|
|
Processing: 48% (12958905/26542080); Rate: 2221755/sec for 1.000003187s; Time left (est.): 6s
|
|
Processing: 57% (15163877/26542080); Rate: 2204929/sec for 1.000002717s; Time left (est.): 5s
|
|
Processing: 65% (17254760/26542080); Rate: 2090742/sec for 1.00008452s; Time left (est.): 4s
|
|
Processing: 73% (19513142/26542080); Rate: 2258348/sec for 1.000071076s; Time left (est.): 3s
|
|
Processing: 82% (21795213/26542080); Rate: 2282028/sec for 1.000076024s; Time left (est.): 2s
|
|
Processing: 90% (24048891/26542080); Rate: 2253645/sec for 1.000146957s; Time left (est.): 1s
|
|
Processing: 98% (26226252/26542080); Rate: 2177215/sec for 1.000129955s; Time left (est.): 0s
|
|
Processing: 100% (26542080/26542080); Rate: 315792/sec for 1.000105149s; Time left (est.): 0s
|
|
Validated solutions (13.001683829s)
|
|
|
|
Solution #1:
|
|
╔═══════════╗
|
|
║769│154│832╢
|
|
║154│832│769╢
|
|
║832│769│154╢
|
|
╟───┼───┼───╢
|
|
║671│945│328╢
|
|
║945│328│671╢
|
|
║328│671│945╢
|
|
╟───┼───┼───╢
|
|
║597│416│283╢
|
|
║416│283│597╢
|
|
║283│597│416╢
|
|
╚═══════════╝
|
|
```
|
|
|
|
## Caveats
|
|
While this may very well solve all possible Sudoku puzzles (including the one [designed against brute force algorithms](https://en.wikipedia.org/wiki/Sudoku_solving_algorithms)), the blanks in the puzzle, the harder it is, the more possible solutions there are, the more solutions it needs to parse, the longer it takes. As this is a computational heavy program, the more CPU you throw against it the faster it will solve issues.
|
|
|
|
## Generating your own blocks
|
|
To generate your own blocks, you could use the following code:
|
|
```go
|
|
func (solver *Solver) generate_blocks() []int {
|
|
|
|
var blocks []int
|
|
decvals := [9]int{49, 50, 51, 52, 53, 54, 55, 56, 57}
|
|
|
|
for counter := 123456789; counter <= 987654321; counter++ {
|
|
|
|
// Convert number to string ([]byte)
|
|
digits := strconv.Itoa(counter)
|
|
|
|
// Check if every number is only represented only once
|
|
var valid bool
|
|
valid = true
|
|
for decval := range decvals {
|
|
var count int
|
|
for digit := range digits {
|
|
if digits[digit] == byte(decvals[decval]) {
|
|
count = count + 1
|
|
}
|
|
}
|
|
|
|
if count != 1 {
|
|
valid = false
|
|
}
|
|
}
|
|
|
|
if valid {
|
|
blocks = append(blocks, counter)
|
|
}
|
|
}
|
|
|
|
return blocks
|
|
|
|
}
|
|
```
|