The fastest Sudoku solver
C++ - 0.201s official score
Using Tdoku (code; design; benchmarks) gives these results:
~/tdoku$ lscpu | grep Model.name Model name: Intel(R) Core(TM) i7-4930K CPU @ 3.40GHz ~/tdoku$ # build: ~/tdoku$ CC=clang-8 CXX=clang++-8 ./BUILD.sh ~/tdoku$ clang -o solve example/solve.c build/libtdoku.a ~/tdoku$ # adjust input format: ~/tdoku$ sed -e "s/0/./g" all_17_clue_sudokus.txt > all_17_clue_sudokus.txt.in ~/tdoku$ # solve: ~/tdoku$ time ./solve 1 < all_17_clue_sudokus.txt.in > out.txt real 0m0.241s user 0m0.229s sys 0m0.012s ~/tdoku$ # adjust output format and sha256sum: ~/tdoku$ grep -v "^:0:$" out.txt | sed -e "s/:1:/,/" | tr . 0 | sha256sum 0bc8dda364db7b99f389b42383e37b411d9fa022204d124cb3c8959eba252f05 -
Tdoku has been optimized for hard Sudoku instances. But note, contrary to the problem statement, that 17 clue puzzles are far from the hardest Sudoku. Actually they're among the easiest, with the majority requiring no backtracking at all. See some of the other benchmark datasets in the Tdoku project for puzzles that are actually hard.
Also note that while Tdoku is the fastest solver I'm aware of for hard puzzles, it's not the fastest for 17 clue puzzles. For these I think the fastest is this rust project, a derivative of JCZSolve, which was optimized for 17 clue puzzles during development. Depending on the platform it might be 5-25% faster than Tdoku for these puzzles.
Node.js, 8.231s 6.735s official score
Takes the file name as argument. The input file may already contain the solutions in the format described in the challenge, in which case the program will compare them with its own solutions.
The results are saved in 'sudoku.log'.
Code
'use strict';
const fs = require('fs');
const BLOCK = [];
const BLOCK_NDX = [];
const N_BIT = [];
const ZERO = [];
const BIT = [];
console.time('Processing time');
init();
let filename = process.argv[2],
puzzle = fs.readFileSync(filename).toString().split('\n'),
len = puzzle.shift(),
output = len + '\n';
console.log("File '" + filename + "': " + len + " puzzles");
// solve all puzzles
puzzle.forEach((p, i) => {
let sol, res;
[ p, sol ] = p.split(',');
if(p.length == 81) {
if(!(++i % 2000)) {
console.log((i * 100 / len).toFixed(1) + '%');
}
if(!(res = solve(p))) {
throw "Failed on puzzle " + i;
}
if(sol && res != sol) {
throw "Invalid solution for puzzle " + i;
}
output += p + ',' + res + '\n';
}
});
// results
console.timeEnd('Processing time');
fs.writeFileSync('sudoku.log', output);
console.log("MD5 = " + require('crypto').createHash('md5').update(output).digest("hex"));
// initialization of lookup tables
function init() {
let ptr, x, y;
for(x = 0; x < 0x200; x++) {
N_BIT[x] = [0, 1, 2, 3, 4, 5, 6, 7, 8].reduce((s, n) => s + (x >> n & 1), 0);
ZERO[x] = ~x & -~x;
}
for(x = 0; x < 9; x++) {
BIT[1 << x] = x;
}
for(ptr = y = 0; y < 9; y++) {
for(x = 0; x < 9; x++, ptr++) {
BLOCK[ptr] = (y / 3 | 0) * 3 + (x / 3 | 0);
BLOCK_NDX[ptr] = (y % 3) * 3 + x % 3;
}
}
}
// solver
function solve(p) {
let ptr, x, y, v,
count = 81,
m = Array(81).fill(-1),
row = Array(9).fill(0),
col = Array(9).fill(0),
blk = Array(9).fill(0);
// helper function to check and play a move
function play(stack, x, y, n) {
let p = y * 9 + x;
if(~m[p]) {
if(m[p] == n) {
return true;
}
undo(stack);
return false;
}
let msk, b;
msk = 1 << n;
b = BLOCK[p];
if((col[x] | row[y] | blk[b]) & msk) {
undo(stack);
return false;
}
count--;
col[x] ^= msk;
row[y] ^= msk;
blk[b] ^= msk;
m[p] = n;
stack.push(x << 8 | y << 4 | n);
return true;
}
// helper function to undo all moves on the stack
function undo(stack) {
stack.forEach(v => {
let x = v >> 8,
y = v >> 4 & 15,
p = y * 9 + x,
b = BLOCK[p];
v = 1 << (v & 15);
count++;
col[x] ^= v;
row[y] ^= v;
blk[b] ^= v;
m[p] = -1;
});
}
// convert the puzzle into our own format
for(ptr = y = 0; y < 9; y++) {
for(x = 0; x < 9; x++, ptr++) {
if(~(v = p[ptr] - 1)) {
col[x] |= 1 << v;
row[y] |= 1 << v;
blk[BLOCK[ptr]] |= 1 << v;
count--;
m[ptr] = v;
}
}
}
// main recursive search function
let res = (function search() {
// success?
if(!count) {
return true;
}
let ptr, x, y, v, n, max, best,
k, i, stack = [],
dCol = Array(81).fill(0),
dRow = Array(81).fill(0),
dBlk = Array(81).fill(0),
b, v0;
// scan the grid:
// - keeping track of where each digit can go on a given column, row or block
// - looking for a cell with the fewest number of legal moves
for(max = ptr = y = 0; y < 9; y++) {
for(x = 0; x < 9; x++, ptr++) {
if(m[ptr] == -1) {
v = col[x] | row[y] | blk[BLOCK[ptr]];
n = N_BIT[v];
// abort if there's no legal move on this cell
if(n == 9) {
return false;
}
// update dCol[], dRow[] and dBlk[]
for(v0 = v ^ 0x1FF; v0;) {
b = v0 & -v0;
dCol[x * 9 + BIT[b]] |= 1 << y;
dRow[y * 9 + BIT[b]] |= 1 << x;
dBlk[BLOCK[ptr] * 9 + BIT[b]] |= 1 << BLOCK_NDX[ptr];
v0 ^= b;
}
// update the cell with the fewest number of moves
if(n > max) {
best = {
x : x,
y : y,
ptr: ptr,
msk: v
};
max = n;
}
}
}
}
// play all forced moves (unique candidates on a given column, row or block)
// and make sure that it doesn't lead to any inconsistency
for(k = 0; k < 9; k++) {
for(n = 0; n < 9; n++) {
if(N_BIT[dCol[k * 9 + n]] == 1) {
i = BIT[dCol[k * 9 + n]];
if(!play(stack, k, i, n)) {
return false;
}
}
if(N_BIT[dRow[k * 9 + n]] == 1) {
i = BIT[dRow[k * 9 + n]];
if(!play(stack, i, k, n)) {
return false;
}
}
if(N_BIT[dBlk[k * 9 + n]] == 1) {
i = BIT[dBlk[k * 9 + n]];
if(!play(stack, (k % 3) * 3 + i % 3, (k / 3 | 0) * 3 + (i / 3 | 0), n)) {
return false;
}
}
}
}
// if we've played at least one forced move, do a recursive call right away
if(stack.length) {
if(search()) {
return true;
}
undo(stack);
return false;
}
// otherwise, try all moves on the cell with the fewest number of moves
while((v = ZERO[best.msk]) < 0x200) {
col[best.x] ^= v;
row[best.y] ^= v;
blk[BLOCK[best.ptr]] ^= v;
m[best.ptr] = BIT[v];
count--;
if(search()) {
return true;
}
count++;
m[best.ptr] = -1;
col[best.x] ^= v;
row[best.y] ^= v;
blk[BLOCK[best.ptr]] ^= v;
best.msk ^= v;
}
return false;
})();
return res ? m.map(n => n + 1).join('') : false;
}
// debugging
function dump(m) {
let x, y, c = 81, s = '';
for(y = 0; y < 9; y++) {
for(x = 0; x < 9; x++) {
s += (~m[y * 9 + x] ? (c--, m[y * 9 + x] + 1) : '-') + (x % 3 < 2 || x == 8 ? ' ' : ' | ');
}
s += y % 3 < 2 || y == 8 ? '\n' : '\n------+-------+------\n';
}
console.log(c);
console.log(s);
}
Example output
Tested on an Intel Core i7 7500U @ 2.70 GHz.
Python 3 (with dlx) 4min 46.870s official score
(single core i7-3610QM here)
Obviously beatable with a compiled language like C, and making use of threading, but it's a start...
sudoku is a module I've placed on github (copied at the footer of this post) which uses dlx under the hood.
#!/usr/bin/python
import argparse
import gc
import sys
from timeit import timeit
from sudoku import Solver
def getSolvers(filePath):
solvers = []
with open(filePath, 'r') as inFile:
for line in inFile:
content = line.rstrip()
if len(content) == 81 and content.isdigit():
solvers.append(Solver(content))
return solvers
def solve(solvers):
for solver in solvers:
yield next(solver.genSolutions())
if __name__ == '__main__':
parser = argparse.ArgumentParser(description='Time or print solving of some sudoku.')
parser.add_argument('filePath',
help='Path to the file containing proper sudoku on their own lines as 81 digits in row-major order with 0s as blanks')
parser.add_argument('-p', '--print', dest='printEm', action='store_true',
default=False,
help='print solutions in the same fashion as the input')
parser.add_argument('-P', '--pretty', dest='prettyPrintEm', action='store_true',
default=False,
help='print inputs and solutions formatted for human consumption')
args = parser.parse_args()
if args.printEm or args.prettyPrintEm:
solvers = getSolvers(args.filePath)
print(len(solvers))
for solver, solution in zip(solvers, solve(solvers)):
if args.prettyPrintEm:
print(solver)
print(solution)
else:
print('{},{}'.format(solver.representation(noneCharacter='0'), solution.representation()))
else:
setup = '''\
from __main__ import getSolvers, solve, args, gc
gc.disable()
solvers = getSolvers(args.filePath)'''
print(timeit("for solution in solve(solvers): pass", setup=setup, number=1))
Usage
- Install Python 3
- Save
sudoku.pysomewhere on your path (from the git hub link or copy it from below) - Save the above code as
testSolver.pysomewhere on your path - Install dlx:
python -m pip install dlx
- Run it (by the way it consumes memory like it's going out of fashion)
usage: testSolver.py [-h] [-p] [-P] filePath
Time or print solving of some sudoku.
positional arguments:
filePath Path to the file containing proper sudoku on their own lines
as 81 digits in row-major order with 0s as blanks
optional arguments:
-h, --help show this help message and exit
-p, --print print solutions in the same fashion as the input
-P, --pretty print inputs and solutions formatted for human consumption
Pipe output as required in the challenge spec to a file if need be:
python testSolver.py -p input_file_path > output_file_path
sudoku.py (yes there are extra features here other than solving)
import dlx
from itertools import permutations, takewhile
from random import choice, shuffle
'''
A 9 by 9 sudoku solver.
'''
_N = 3
_NSQ = _N**2
_NQU = _N**4
_VALID_VALUE_INTS = list(range(1, _NSQ + 1))
_VALID_VALUE_STRS = [str(v) for v in _VALID_VALUE_INTS]
_EMPTY_CELL_CHAR = '·'
# The following are mutually related by their ordering, and define ordering throughout the rest of the code. Here be dragons.
#
_CANDIDATES = [(r, c, v) for r in range(_NSQ) for c in range(_NSQ) for v in range(1, _NSQ + 1)]
_CONSTRAINT_INDEXES_FROM_CANDIDATE = lambda r, c, v: [ _NSQ * r + c, _NQU + _NSQ * r + v - 1, _NQU * 2 + _NSQ * c + v - 1, _NQU * 3 + _NSQ * (_N * (r // _N) + c // _N) + v - 1]
_CONSTRAINT_FORMATTERS = [ "R{0}C{1}" , "R{0}#{1}" , "C{0}#{1}" , "B{0}#{1}"]
_CONSTRAINT_NAMES = [(s.format(a, b + (e and 1)), dlx.DLX.PRIMARY) for e, s in enumerate(_CONSTRAINT_FORMATTERS) for a in range(_NSQ) for b in range(_NSQ)]
_EMPTY_GRID_CONSTRAINT_INDEXES = [_CONSTRAINT_INDEXES_FROM_CANDIDATE(r, c, v) for (r, c, v) in _CANDIDATES]
#
# The above are mutually related by their ordering, and define ordering throughout the rest of the code. Here be dragons.
class Solver:
def __init__(self, representation=''):
if not representation or len(representation) != _NQU:
self._complete = False
self._NClues = 0
self._repr = [None]*_NQU # blank grid, no clues - maybe to extend to a generator by overriding the DLX column selection to be stochastic.
else:
nClues = 0
repr = []
for value in representation:
if not value:
repr.append(None)
elif isinstance(value, int) and 1 <= value <= _NSQ:
nClues += 1
repr.append(value)
elif value in _VALID_VALUE_STRS:
nClues += 1
repr.append(int(value))
else:
repr.append(None)
self._complete = nClues == _NQU
self._NClues = nClues
self._repr = repr
def genSolutions(self, genSudoku=True, genNone=False, dlxColumnSelctor=None):
'''
if genSudoku=False, generates each solution as a list of cell values (left-right, top-bottom)
'''
if self._complete:
yield self
else:
self._initDlx()
dlxColumnSelctor = dlxColumnSelctor or dlx.DLX.smallestColumnSelector
if genSudoku:
for solution in self._dlx.solve(dlxColumnSelctor):
yield Solver([v for (r, c, v) in sorted([self._dlx.N[i] for i in solution])])
elif genNone:
for solution in self._dlx.solve(dlxColumnSelctor):
yield
else:
for solution in self._dlx.solve(dlxColumnSelctor):
yield [v for (r, c, v) in sorted([self._dlx.N[i] for i in solution])]
def uniqueness(self, returnSolutionIfProper=False):
'''
Returns: 0 if unsolvable;
1 (or the unique solution if returnSolutionIfProper=True) if uniquely solvable; or
2 if multiple possible solutions exist
- a 'proper' sudoku is uniquely solvable.
'''
slns = list(takewhile(lambda t: t[0] < 2, ((i, sln) for i, sln in enumerate(self.genSolutions(genSudoku=returnSolutionIfProper, genNone=not returnSolutionIfProper)))))
uniqueness = len(slns)
if returnSolutionIfProper and uniqueness == 1:
return slns[0][1]
else:
return uniqueness
def representation(self, asString=True, noneCharacter='.'):
if asString:
return ''.join([v and str(_VALID_VALUE_STRS[v - 1]) or noneCharacter for v in self._repr])
return self._repr[:]
def __repr__(self):
return display(self._repr)
def _initDlx(self):
self._dlx = dlx.DLX(_CONSTRAINT_NAMES)
rowIndexes = self._dlx.appendRows(_EMPTY_GRID_CONSTRAINT_INDEXES, _CANDIDATES)
for r in range(_NSQ):
for c in range(_NSQ):
v = self._repr[_NSQ * r + c]
if v is not None:
self._dlx.useRow(rowIndexes[_NQU * r + _NSQ * c + v - 1])
_ROW_SEPARATOR_COMPACT = '+'.join(['-' * (2 * _N + 1) for b in range(_N)])[1:-1] + '\n'
_ROW_SEPARATOR = ' ·-' + _ROW_SEPARATOR_COMPACT[:-1] + '-·\n'
_TOP_AND_BOTTOM = _ROW_SEPARATOR.replace('+', '·')
_ROW_LABELS = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'J']
_COL_LABELS = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
_COLS_LABEL = ' ' + ' '.join([i % _N == 0 and ' ' + l or l for i, l in enumerate(_COL_LABELS)]) + '\n'
def display(representation, conversion=None, labelled=True):
result = ''
raw = [conversion[n or 0] for n in representation] if conversion else representation
if labelled:
result += _COLS_LABEL + _TOP_AND_BOTTOM
rSep = _ROW_SEPARATOR
else:
rSep = _ROW_SEPARATOR_COMPACT
for r in range(_NSQ):
if r > 0 and r % _N == 0:
result += rSep
for c in range(_NSQ):
if c % _N == 0:
if c == 0:
if labelled:
result += _ROW_LABELS[r] + '| '
else:
result += '| '
result += str(raw[_NSQ * r + c] or _EMPTY_CELL_CHAR) + ' '
if labelled:
result += '|'
result += '\n'
if labelled:
result += _TOP_AND_BOTTOM
else:
result = result[:-1]
return result
def permute(representation):
'''
returns a random representation from the given representation's equivalence class
'''
rows = [list(representation[i:i+_NSQ]) for i in range(0, _NQU, _NSQ)]
rows = permuteRowsAndBands(rows)
rows = [[r[i] for r in rows] for i in range(_NSQ)]
rows = permuteRowsAndBands(rows)
pNumbers = [str(i) for i in range(1, _NSQ + 1)]
shuffle(pNumbers)
return ''.join(''.join([pNumbers[int(v) - 1] if v.isdigit() and v != '0' else v for v in r]) for r in rows)
def permuteRowsAndBands(rows):
bandP = choice([x for x in permutations(range(_N))])
rows = [rows[_N * b + r] for b in bandP for r in range(_N)]
for band in range(0, _NSQ, _N):
rowP = choice([x for x in permutations([band + i for i in range(_N)])])
rows = [rows[rowP[i % _N]] if i // _N == band else rows[i] for i in range(_NSQ)]
return rows
def getRandomSolvedStateRepresentation():
return permute('126459783453786129789123456897231564231564897564897231312645978645978312978312645')
def getRandomSudoku():
r = getRandomSolvedStateRepresentation()
s = Solver(r)
indices = list(range(len(r)))
shuffle(indices)
for i in indices:
ns = Solver(s._repr[:i] + [None] + s._repr[i+1:])
if ns.uniqueness() == 1:
s = ns
return s
if __name__ == '__main__':
print('Some example useage:')
inputRepresentation = '..3......4......2..8.12...6.........2...6...7...8.7.31.1.64.9..6.5..8...9.83...4.'
print('>>> s = Solver({})'.format(inputRepresentation))
s = Solver(inputRepresentation)
print('>>> s')
print(s)
print('>>> print(s.representation())')
print(s.representation())
print('>>> print(display(s.representation(), labelled=False))')
print(display(s.representation(), labelled=False))
print('>>> for solution in s.genSolutions(): solution')
for solution in s.genSolutions(): print(solution)
inputRepresentation2 = inputRepresentation[:2] + '.' + inputRepresentation[3:]
print('>>> s.uniqueness()')
print(s.uniqueness())
print('>>> s2 = Solver({}) # removed a clue; this has six solutions rather than one'.format(inputRepresentation2))
s2 = Solver(inputRepresentation2)
print('>>> s2.uniqueness()')
print(s2.uniqueness())
print('>>> for solution in s2.genSolutions(): solution')
for solution in s2.genSolutions(): print(solution)
print('>>> s3 = getRandomSudoku()')
s3 = getRandomSudoku()
print('>>> s3')
print(s3)
print('>>> for solution in s3.genSolutions(): solution')
for solution in s3.genSolutions(): print(solution)