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 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), 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:

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

}