Pemecah Sudoku tercepat

21

Pemenang ditemukan

Sepertinya kita memiliki pemenang! Kecuali ada yang berencana untuk bertarung dengan pemecah Sudoku tercepat di dunia saat ini, pengguna 53x15 menang dengan Tdoku pemecah yang sangat cepat. Bagi siapa pun yang masih mengerjakan solver mereka, saya masih akan melakukan benchmark pengiriman baru ketika saya punya waktu.

Tantangan

Tujuan permainan Sudoku adalah untuk mengisi papan dengan angka 1-9, satu di setiap sel, sedemikian rupa sehingga setiap baris, kolom dan kotak hanya berisi masing-masing angka satu kali. Aspek yang sangat penting dari sebuah teka-teki Sudoku adalah bahwa seharusnya hanya ada satu solusi yang valid.

Tujuan dari tantangan ini sederhana, Anda harus menyelesaikan serangkaian teka-teki Sudoku secepat mungkin. Namun, Anda tidak hanya akan menyelesaikan Sudoku lama, Anda akan memecahkan teka-teki Sudoku paling sulit yang ada, Sudokus 17-petunjuk. Ini sebuah contoh:

Sudoku yang keras

Aturan

Bahasa

Anda bebas menggunakan bahasa apa pun. Jika saya tidak memiliki kompiler yang diinstal untuk bahasa Anda , Anda harus dapat memberikan satu set instruksi baris perintah yang diperlukan untuk menginstal lingkungan di mana skrip Anda dapat dijalankan di Linux .

Mesin benchmark

Benchmark akan dijalankan pada Dell XPS 9560, 2.8GHz Intel Core i7-7700HQ (peningkatan 3,8GHz) 4 core, 8 thread, 16GB RAM. GTX 1050 4GB. Mesin menjalankan Ubuntu 19.04. Inilah unamehasilnya, untuk siapa saja yang tertarik.

Linux 5.0.0-25-generic #26-Ubuntu SMP Thu Aug 1 12:04:58 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux

Memasukkan

Input akan diberikan sebagai file. Itu dapat ditemukan di sini . File ini berisi 49151 teka-teki Sudoku. Baris pertama file adalah jumlah puzzle, dan setiap baris setelahnya adalah 81 karakter dan mewakili puzzle. Sel yang tidak diketahui adalah 0, dan sel yang diketahui adalah 1-9.

Program Anda harus dapat menggunakan nama file sebagai argumen, atau meminta input file dari STDIN , untuk memfasilitasi pengecekan manual atas solusi Anda. Harap sertakan instruksi bagaimana program Anda mengambil input.

Pengaturan waktu / penilaian

Dari diskusi di komentar, dan beberapa refleksi, kriteria penilaian telah diubah menjadi waktu seluruh program Anda. Program Anda harus menghasilkan file output dengan hash yang benar bahkan selama penilaian resmi. Ini tidak mengganggu solusi apa pun yang ada, dan tidak mengubah peringkat saat ini. Setiap pemikiran tentang sistem penilaian dihargai.

Jika dua solusi memiliki skor yang sama untuk menjalankan individual, saya akan menjalankan beberapa tolok ukur, dan waktu rata-rata akan menjadi skor akhir. Jika skor rata-rata berbeda kurang dari 2%, saya akan menganggap itu seri.

Jika solusi Anda membutuhkan waktu lebih dari satu jam untuk berjalan, itu tidak akan diberi skor secara resmi. Dalam kasus tersebut, Anda bertanggung jawab untuk melaporkan mesin yang menjalankannya, dan skor Anda. Untuk pemecah yang dioptimalkan, ini seharusnya tidak menjadi masalah.

EDIT : Saya mendapat perhatian bahwa meskipun sulit, masalah yang ada bukanlah yang paling sulit. Jika waktu tersedia, saya akan mencoba membandingkan solusi yang disajikan di sini dengan set puzzle yang lebih sulit, dan menambahkan skor untuk setiap pengiriman. Namun, ini tidak akan menjadi penilaian resmi, dan hanya untuk bersenang-senang.

Verifikasi

Solusi Anda akan diverifikasi oleh checksum MD5 / SHA256. Skrip Anda harus dapat menghasilkan file yang berisi semua teka-teki dan solusinya. Namun, file juga akan diperiksa secara manual, jadi jangan mencoba untuk mendapatkan tabrakan hash. File output Anda harus sesuai:

MD5: 41704fd7d8fd0723a45ffbb2dbbfa488
SHA256:0bc8dda364db7b99f389b42383e37b411d9fa022204d124cb3c8959eba252f05

File akan berada dalam format:

<num_puzzles>
<unsolved_puzzle#1>,<solved_puzzle#1>
<unsolved_puzzle#2>,<solved_puzzle#2>
...
<unsolved_puzzle#n>,<solved_puzzle#n>

dengan single trailing newline.

Apa yang tidak diizinkan?

Anda sama sekali tidak diizinkan untuk solusi hard-code . Algoritme Anda harus dapat diterapkan pada serangkaian teka-teki Sudoku apa pun, baik Sudokus yang mudah maupun yang lebih sulit. Namun, itu sepenuhnya baik-baik saja jika solusi Anda lambat untuk teka-teki yang lebih mudah.

Anda tidak diizinkan memiliki program non-deterministik . Anda diizinkan untuk menggunakan generator nomor acak, tetapi benih generator harus diperbaiki. Aturan ini adalah untuk memastikan bahwa pengukuran lebih tepat, dan memiliki varian yang lebih sedikit. (Terima kasih kepada Peter Taylor untuk tipnya)

Anda tidak diperbolehkan menggunakan sumber daya eksternal atau permintaan web apa pun selama runtime program Anda. Semuanya harus mandiri. Ini tidak berlaku untuk pustaka dan paket yang diinstal, yang diizinkan.

Info lain

Jika Anda ingin set tes lain untuk memeriksa solusi Anda, berikut adalah 10.000 Sudokus yang lebih mudah . Inilah solusinya .

MD5: 3cb465ef6077c4fcab5bd6ae3bc50d62
SHA256:0bc8dda364db7b99f389b42383e37b411d9fa022204d124cb3c8959eba252f05

Jika Anda memiliki pertanyaan, jangan ragu untuk bertanya, dan saya akan mencoba untuk menjelaskan kesalahpahaman.

maks
sumber
Saya memiliki pemecah APL + WIN tetapi kecuali jika Anda memiliki salinan juru bahasa di komputer Anda, Anda harus menghitung saya keluar. Untuk info contoh keras Anda mengambil 30 ms dan contoh mudah pertama 16 ms.
Graham
@ Graham butuh 30ms untuk semua 49151 sudokus, atau rata-rata 30ms?
Maks
Sayangnya 30ms hanya untuk contoh yang sulit. Kecuali jika ini layak untuk dilakukan, saya hanya menjalankan solver APL terhadap contoh keras Anda dan yang pertama dari contoh mudah. Jika kita dapat memperkirakan dari contoh keras, kita melihat sekitar 1500 detik untuk set lengkap
Graham
1
Haruskah entri juga menjadi kode golf? Atau ... Bisakah mereka bermain golf, untuk bersenang-senang? ;-)
The Matt
2
@TheMatt Saya lebih suka non-golf, supaya saya bisa memverifikasi bahwa tidak ada yang mencurigakan
maxb

Jawaban:

5

C ++ - skor resmi 0.201s

Menggunakan Tdoku ( kode ; desain ; tolok ukur ) memberikan hasil ini:

~ / tdoku $ lscpu | grep Model.name
Nama model: Intel (R) Core (TM) i7-4930K CPU @ 3.40GHz

~ / tdoku $ # build:
~ / tdoku $ CC = clang-8 CXX = clang ++ - 8 ./BUILD.sh
~ / tdoku $ clang -untuk memecahkan contoh / build.c build / libtdoku.a 

~ / tdoku $ # sesuaikan format input:
~ / tdoku $ sed -e "s / 0 /./g" all_17_clue_sudokus.txt> all_17_clue_sudokus.txt.in

~ / tdoku $ # selesaikan:
~ / tdoku $ time ./solve 1 <all_17_clue_sudokus.txt.in> out.txt
0m0.241s nyata
pengguna 0m0.229s
sys 0m0.012s

~ / tdoku $ # sesuaikan format output dan sha256sum:
~ / tdoku $ grep -v "^: 0: $" out.txt | sed -e "s /: 1: /, /" | tr. 0 | sha256sum
0bc8dda364db7b99f389b42383e37b411d9fa022204d124cb3c8959eba252f05 -

Tdoku telah dioptimalkan untuk contoh keras Sudoku. Tetapi perhatikan, berlawanan dengan pernyataan masalah, bahwa 17 teka-teki petunjuk jauh dari Sudoku yang paling sulit. Sebenarnya mereka termasuk yang termudah, dengan mayoritas tidak memerlukan backtracking sama sekali. Lihat beberapa dataset benchmark lain di proyek Tdoku untuk puzzle yang sebenarnya sulit.

Juga perhatikan bahwa meskipun Tdoku adalah pemecah tercepat yang saya ketahui untuk puzzle keras, itu bukan yang tercepat untuk 17 puzzle petunjuk. Untuk ini saya pikir yang tercepat adalah proyek karat ini , turunan dari JCZSolve, yang dioptimalkan untuk 17 teka-teki petunjuk selama pengembangan. Tergantung pada platformnya mungkin 5-25% lebih cepat dari Tdoku untuk teka-teki ini.

53x15
sumber
Wow, itu bacaan yang menarik tentang implementasi dan teori di baliknya. Sebelum saya memulai tantangan ini, saya ingin menemukan pemecah dan set data canggih. Saya kira saya tidak terlihat cukup keras. Dari artikel "ilmiah" yang populer, 17 teka-teki petunjuk adalah semua yang pernah dibicarakan, jadi asumsi saya bahwa itu adalah yang paling sulit. Saya akan mencoba menjalankan semua kiriman terhadap set data yang disajikan dalam artikel Anda, dan saya akan membandingkan kiriman Anda hari ini. Pekerjaan yang fantastis!
Maks.
Terima kasih! Anda lihat dari artikel bahwa menemukan solusi canggih membawa saya pada perjalanan panjang. :-) Saya mengerti mengapa orang fokus pada 17 teka-teki petunjuk: dataset terkenal, terdefinisi dengan baik, lengkap atau hampir begitu, cukup besar, dan sulit untuk pemecah yang naif. Walaupun menarik untuk mempelajari teka-teki yang lebih sulit, kekerasan sulit untuk diformalkan. misalnya, apakah yang kita maksudkan secara subyektif atau empiris sulit bagi manusia berdasarkan teknik yang diperlukan? maksud kami rata-rata lambat untuk pemecah tertentu di bawah permutasi acak? Apakah yang kami maksud adalah ukuran pintu belakang minimum di bawah formula dengan inferensi pigeonhole yang dipilih? dll
53x15
8

Node.js , 8.231s 6.735s skor resmi

Mengambil nama file sebagai argumen. File input mungkin sudah berisi solusi dalam format yang dijelaskan dalam tantangan, dalam hal mana program akan membandingkannya dengan solusi sendiri.

Hasilnya disimpan dalam 'sudoku.log' .

Kode

'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);
}

Contoh output

Diuji pada Intel Core i7 7500U @ 2.70 GHz.

keluaran

Arnauld
sumber
Saya mungkin harus membersihkan skor. Jika Anda melakukan sesuatu secara paralel, skor Anda masih merupakan jumlah dari semua waktu penyelesaian individu. Anda harus menghitung jumlah itu dan menyajikannya sebagai skor Anda. Dengan begitu lebih tentang mendapatkan kode secepat mungkin. Kode selalu dapat memparalelkan di 49151 teka-teki, membuat bagian itu sepele. Saya mungkin mengubah skor menjadi total waktu program, dan melarang multithreading. Atau, mungkin multithreading harus menjadi bagian dari tantangan?
Maks
1
@ Maxb saya mengerti. Saya tidak mengerti bahwa kekhawatiran Anda tentang multi-threading.
Arnauld
1
Mengapa solusi Anda jauh lebih cepat daripada yang lain?
Anush
2
@Anush Apa yang saya sebut 'gerakan paksa' dalam kode adalah apa yang membuatnya secara signifikan lebih cepat dan lebih dikenal sebagai single tersembunyi . (Kita juga bisa mencari kembar tersembunyi, tiga kali lipat, paha depan, dll. Tapi saya tidak yakin itu benar-benar layak, setidaknya di Node.)
Arnauld
3
" Saya mulai melihat single telanjang " hati-hati dengan ungkapan :)
ngn
3

Python 3 (dengan dlx ) 4 menit 46,870 skor resmi

(single core i7-3610QM di sini)

Jelas bisa dikalahkan dengan bahasa yang dikompilasi seperti C, dan memanfaatkan threading, tapi ini awal ...

sudokuadalah modul yang saya letakkan di github (disalin di bagian dlxbawah tulisan ini) yang menggunakan di bawah tenda.

#!/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))

Pemakaian

  • Instal Python 3
  • Simpan di sudoku.pysuatu tempat di jalur Anda (dari tautan hub git atau salin dari bawah)
  • Simpan kode di atas sebagai testSolver.pysuatu tempat di jalur Anda
  • Instal dlx:
python -m pip instal dlx
  • Jalankan (dengan cara mengkonsumsi memori seperti itu keluar dari mode)
penggunaan: testSolver.py [-h] [-p] [-P] filePath

Pemecahan waktu atau pencetakan dari beberapa sudoku.

argumen posisi:
  path filePath ke file yang berisi sudoku yang tepat pada baris mereka sendiri
                sebagai 81 digit dalam urutan baris-utama dengan 0s sebagai kosong

argumen opsional:
  -h, --help tampilkan pesan bantuan ini dan keluar
  -p, --cetakan solusi dengan cara yang sama seperti input
  -P, - input cetak yang tepat dan solusi yang diformat untuk konsumsi manusia

Memotong output seperti yang diperlukan dalam spec tantangan ke file jika perlu:

python testSolver.py -p input_file_path> output_file_path

sudoku.py (ya ada fitur tambahan di sini selain untuk menyelesaikan)

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)
Jonathan Allan
sumber
Mengesankan untuk solusi Python, saya akan mencoba melakukan benchmark hari ini.
Maks
1
Terima kasih; dan wow, jauh lebih cepat di sana!
Jonathan Allan
1
+1 untuk menggunakan tautan menari
Anush
3

Python 3 + Z3 - 10 menit skor resmi 45.657

sekitar 1000-an di laptop saya.

import time
start = time.time()

import z3.z3 as z3
import itertools
import datetime
import sys

solver = z3.Solver()
ceils = [[None] * 9 for i in range(9)]

for row in range(9):
    for col in range(9):
        name = 'c' + str(row * 9 + col)
        ceil = z3.BitVec(name, 9)
        solver.add(z3.Or(
            ceil == 0b000000001,
            ceil == 0b000000010,
            ceil == 0b000000100,
            ceil == 0b000001000,
            ceil == 0b000010000,
            ceil == 0b000100000,
            ceil == 0b001000000,
            ceil == 0b010000000,
            ceil == 0b100000000
        ))
        solver.add(ceil != 0)
        ceils[row][col] = ceil
for i in range(9):
    for j in range(9):
        for k in range(9):
            if j == k: continue
            solver.add(ceils[i][j] & ceils[i][k] == 0)
            solver.add(ceils[j][i] & ceils[k][i] == 0)
            row, col = i // 3 * 3, i % 3 * 3
            solver.add(ceils[row + j // 3][col + j % 3] & ceils[row + k // 3][col + k % 3] == 0)

row_col = list(itertools.product(range(9), range(9)))
lookup = { 1 << i: str(i + 1) for i in range(9) }

def solve(line):
    global solver, output, row_col, ceils, lookup
    solver.push()
    for value, (row, col) in zip(line, row_col):
        val = ord(value) - 48
        if val == 0: continue
        solver.add(ceils[row][col] == 1 << (val - 1))

    output = []
    if solver.check() == z3.sat:
        model = solver.model()
        for row in range(9):
            for col in range(9):
                val = model[ceils[row][col]].as_long()
                output.append(lookup[val])
    solver.pop()

    return ''.join(output)

count = int(input())
print(count)
for i in range(count):
    if i % 1000 == 0:
        sys.stderr.write(str(i) + '\n')
    line = input()
    print(line + "," + solve(line))
end = time.time()

sys.stderr.write(str(end - start))

Instal ketergantungan

instal pemecah z3

Lari

python3 resol.py <in.txt> out.txt

Saya tidak yakin bagaimana meningkatkan kinerjanya, karena itu baru saja dipecahkan secara ajaib ...

tsh
sumber
Cukup mengesankan untuk pemecah kendala umum. Implementasi pertama saya jauh lebih lambat dari ini. Menjalankan patokan sekarang, saya akan memperbarui pos setelah selesai.
Maks
@maxb baru saja melakukan pembersihan umum, dan saya percaya tidak perlu memperbarui patokan ...
tsh
3

C - 2.228s 1.690s skor resmi

berdasarkan @ Arnauld

#include<fcntl.h>
#define O const
#define R return
#define S static
#define  $(x,y...)if(x){y;}
#define  W(x,y...)while(x){y;}
#define fi(x,y...)for(I i=0,_n=(x);i<_n;i++){y;}
#define fj(x,y...)for(I j=0,_n=(x);j<_n;j++){y;}
#define fp81(x...)for(I p=0;p<81;p++){x;}
#define  fq3(x...)for(I q=0;q<3;q++){x;}
#define fij9(x...){fi(9,fj(9,x))}
#define m0(x)m0_((V*)(x),sizeof(x));
#define popc(x)__builtin_popcount(x)
#define ctz(x)__builtin_ctz(x)
#include<sys/syscall.h>
#define sc(f,x...)({L u;asm volatile("syscall":"=a"(u):"0"(SYS_##f)x:"cc","rcx","r11","memory");u;})
#define sc1(f,x)    sc(f,,"D"(x))
#define sc2(f,x,y)  sc(f,,"D"(x),"S"(y))
#define sc3(f,x,y,z)sc(f,,"D"(x),"S"(y),"d"(z))
#define wr(a...)sc3(write,a)
#define op(a...)sc3( open,a)
#define cl(a...)sc1(close,a)
#define fs(a...)sc2(fstat,a)
#define ex(a...)sc1( exit,a)
#define mm(x,y,z,t,u,v)({register L r10 asm("r10")=t,r8 asm("r8")=u,r9 asm("r9")=v;\
                         (V*)sc(mmap,,"D"(x),"S"(y),"d"(z),"r"(r10),"r"(r8),"r"(r9));})
typedef void V;typedef char C;typedef short H;typedef int I;typedef long long L;
S C BL[81],KL[81],IJK[81][3],m[81],t_[81-17],*t;S H rcb[3][9],cnt;
S V*mc(V*x,O V*y,L n){C*p=x;O C*q=y;fi(n,*p++=*q++)R x;}S V m0_(C*p,L n){fi(n,*p++=0);}
S I undo(C*t0){cnt+=t-t0;W(t>t0,C p=*--t;H v=1<<m[p];fq3(rcb[q][IJK[p][q]]^=v)m[p]=-1)R 0;}
S I play(C p,H v){$(m[p]>=0,R 1<<m[p]==v)I w=0;fq3(w|=rcb[q][IJK[p][q]])$(w&v,R 0)cnt--;
                  fq3(rcb[q][IJK[p][q]]^=v);m[p]=ctz(v);*t++=p;R 1;}
S I f(){$(!cnt,R 1)C*t0=t;H max=0,bp,bv,d[9][9][4];m0(d);
 fij9(I p=i*9+j;$(m[p]<0,
  I v=0;fq3(v|=rcb[q][IJK[p][q]])I w=v^511;$(!w,R 0)H g[]={1<<j,1<<i,1<<BL[p]};
  do{I z=ctz(w);w&=w-1;fq3(d[IJK[p][q]][z][q]|=g[q]);}while(w);
  I n=popc(v);$(max<n,max=n;bp=p;bv=v)))
 fij9(I u=d[i][j][0];$(popc(u)==1,I l=ctz(u);$(!play(   i*9+l ,1<<j),R undo(t0)))
        u=d[i][j][1];$(popc(u)==1,I l=ctz(u);$(!play(   l*9+i ,1<<j),R undo(t0)))
        u=d[i][j][2];$(popc(u)==1,I l=ctz(u);$(!play(KL[i*9+l],1<<j),R undo(t0))))
 $(t-t0,R f()||undo(t0))
 W(1,I v=1<<ctz(~bv);$(v>511,R 0)fq3(rcb[q][IJK[bp][q]]^=v)m[bp]=ctz(v);cnt--;$(f(),R 1)
     cnt++;m[bp]=-1;fq3(rcb[q][IJK[bp][q]]^=v)bv^=v)
 R 0;}
asm(".globl _start\n_start:pop %rdi\nmov %rsp,%rsi\njmp main");
V main(I ac,C**av){$(ac!=2,ex(2))
 fij9(I p=i*9+j;BL[p]=i%3*3+j%3;KL[p]=(i/3*3+j/3)*9+BL[p];IJK[p][0]=i;IJK[p][1]=j;IJK[p][2]=i/3*3+j/3)
 I d=op(av[1],0,0);struct stat h;fs(d,&h);C*s0=mm(0,h.st_size,1,0x8002,d,0),*s=s0;cl(d); //in
 C*r0=mm(0,2*h.st_size,3,0x22,-1,0),*r=r0; //out
 I n=0;W(*s!='\n',n*=10;n+=*s++-'0')s++;mc(r,s0,s-s0);r+=s-s0;
 fi(n,m0(rcb);cnt=81;t=t_;$(s[81]&&s[81]!='\n',ex(3))mc(r,s,81);r+=81;*r++=',';
      fp81(I v=m[p]=*s++-'1';$(v>=0,v=1<<v;fq3(rcb[q][IJK[p][q]]|=v)cnt--))
      s++;$(!f(),ex(4))fp81(r[p]=m[p]+'1')r+=81;*r++='\n')
 wr(1,r0,r-r0);ex(0);}

kompilasi dan jalankan:

gcc -O3 -march=native -nostdlib -ffreestanding
time ./a.out all_17_clue_sudokus.txt | md5sum
ngn
sumber
Selamat, Anda (dan Arnauld) berada di bawah pimpinan banyak saat ini.
Maks
@maxb saya mencoba menggunakan i / o yang lebih efisien (syscalls langsung tanpa libc) tetapi efeknya tidak sehebat yang saya harapkan. saya juga merapikan sisa kode. ini harus menghilangkan ~ 0.2s. apakah Anda keberatan mencetak ulang?
ngn
Tentu saja, saya akan mencoba menyelesaikannya hari ini
Maks
Saya juga berpikir tentang mencoba RAMdisk untuk semua I / O, hanya untuk melihat apakah itu membuat perbedaan. Saya ragu itu akan membuat perbedaan besar, karena membaca dan menulis adalah berurutan, dan SSD saya memiliki cache yang cukup besar untuk memenuhi semuanya.
Maks
@maxb mungkin tidak akan ada perbedaan sama sekali. kali kedua Anda menjalankan program, file input akan tetap di ram - di cache sistem file linux.
ngn
2

C - 12mnt 28.374s skor resmi

berjalan sekitar 30m 15m pada i5-7200U saya dan menghasilkan hash md5 yang benar

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<sys/time.h>
#define B break
#define O const
#define P printf
#define R return
#define S static
#define $(x,y...)  if(x){y;}
#define E(x...)    else{x;}
#define W(x,y...)  while(x){y;}
#define fi(x,y...) for(I i=0,_n=(x);i<_n;i++){y;}
#define fj(x,y...) for(I j=0,_n=(x);j<_n;j++){y;}
typedef void V;typedef char C;typedef short H;typedef int I;typedef long long L;
S C h[81][20]; //h[i][0],h[i][1],..,h[i][19] are the squares that clash with square i
S H a[81]      //a[i]: bitmask of possible choices; initially one of 1<<0, 1<<1 .. 1<<8, or 511 (i.e. nine bits set)
   ,b[81];     //b[i]: negated bitmask of impossible chioces; once we know square i has value v, b[i] becomes ~(1<<v)
S I f(){ //f:recursive solver
 I p=-1; //keep track of the popcount (number of 1 bits) in a
 W(1,I q=0;                                         //simple non-recursive deductions:
     fi(81,fj(20,a[i]&=b[h[i][j]])                  // a[i] must not share bits with its clashing squares
           $(!(a[i]&a[i]-1),$(!a[i],R 0)b[i]=~a[i]) // if a[i] has one bit left, update b[i].  if a[i]=0, we have a contradiction
           q+=__builtin_popcount(a[i]))             // compute new popcount
     $(p==q,B)p=q;)                                 // if the popcount of a[] changed, try to do more deductions
 I k=-1,mc=10;fi(81,$(b[i]==-1,I c=__builtin_popcount(a[i]);$(c<mc,k=i;mc=c;$(c==2,B)))) //find square with fewest options left
 $(k==-1,R 1) //if there isn't any such, we're done - success! otherwise k is that square
 fi(9,$(a[k]&1<<i,H a0[81],b0[81];                                        //try different values for square k
                  memcpy(a0,a,81*sizeof(*a));memcpy(b0,b,81*sizeof(*b));  // save a and b
                  a[k]=1<<i;b[k]=~a[k];$(f(),R 1)                         // set square k and make a recursive call
                  memcpy(a,a0,81*sizeof(*a));memcpy(b,b0,81*sizeof(*b)))) // restore a and b
 R 0;}
S L tm(){struct timeval t;gettimeofday(&t,0);R t.tv_sec*1000000+t.tv_usec;} //current time in microseconds
I main(){L t=0;I n;scanf("%d",&n);P("%d\n",n);
 fi(81,L l=0;fj(81,$(i!=j&&(i%9==j%9||i/9==j/9||(i/27==j/27&&i%9/3==j%9/3)),h[i][l++]=j))) //precompute h
 fi(n,S C s[82];scanf("%s",s);printf("%s,",s);                        //i/o and loop over puzzles
      fj(81,a[j]=s[j]=='0'?511:1<<(s[j]-'1');b[j]=s[j]=='0'?-1:~a[j]) //represent '1' .. '9' as 1<<0 .. 1<<8, and 0 as 511
      t-=tm();I r=f();t+=tm();                                        //measure time only for the solving function
      $(!r,P("can't solve\n");exit(1))                                //shouldn't happen
      fj(81,s[j]=a[j]&a[j]-1?'0':'1'+__builtin_ctz(a[j]))             //1<<0 .. 1<<8 to '1' .. '9'
      P("%s\n",s))                                                    //output
 fflush(stdout);dprintf(2,"time:%lld microseconds\n",t);R 0;}         //print self-measured time to stderr so it doesn't affect stdout's md5

kompilasi (sebaiknya dengan dentang v6) dan jalankan:

clang -O3 -march=native a.c
time ./a.out <all_17_clue_sudokus.txt | tee o.txt | nl
md5sum o.txt
ngn
sumber
3
Kenapa jelek sekali? Ini bukan kode-golf!
Jonathan Allan
3
@ JonathanAllan begitulah biasanya saya kode (kecuali saya berada di tim yang lebih suka melakukan sebaliknya). itu indah :)
ngn
1
Haha, "cantik", dan mudah untuk kembali dalam 6 bulan: p
Jonathan Allan
1
ya, sebenarnya. Saya telah melakukan ini selama beberapa tahun dan saya merasa lebih efisien. di dunia apl itu dikenal sebagai gaya incunabulum . dengan kode bengkak Anda menggerakkan mata Anda sebagian besar vertikal (tidak alami dan tidak layak untuk monitor lansekap kami) dan gulir banyak. dengan kode ketat Anda dapat melihat semuanya sekaligus, jadi lebih mudah untuk menemukan jalan keluarnya dan menilai kerumitannya sekilas.
ngn
Apakah ini solusi mundur? Saya melihat dua memcpydi sana dan beberapa rekursi terjadi. Saya akan mencoba memverifikasi hari ini.
Maks
2

Java - 4.056 skor resmi

Gagasan utama ini adalah untuk tidak pernah mengalokasikan memori ketika tidak diperlukan. Satu-satunya pengecualian adalah primitif, yang harus dioptimalkan oleh kompiler. Segala sesuatu yang lain disimpan sebagai masker dan array operasi yang dilakukan di setiap langkah, yang dapat dibatalkan ketika langkah rekursi selesai.

Sekitar setengah dari semua sudokus diselesaikan sepenuhnya tanpa mundur, tetapi jika saya mendorong angka itu lebih tinggi secara keseluruhan waktu tampaknya lebih lambat. Saya berencana om menulis ulang ini dalam C ++ dan mengoptimalkan lebih jauh, tetapi pemecah ini menjadi raksasa.

Saya ingin menerapkan cache sebanyak mungkin, yang mengarah pada beberapa masalah. Misalnya, jika ada dua sel pada baris yang sama yang hanya dapat memiliki nomor 6, maka kami telah mencapai kasus yang tidak mungkin, dan harus kembali ke pengulangan. Tetapi karena saya menghitung semua opsi dalam satu sapuan, dan kemudian menempatkan angka dalam sel dengan hanya satu kemungkinan, saya tidak mengecek apakah saya telah meletakkan angka di baris yang sama sebelumnya. Ini mengarah pada solusi yang mustahil.

Dengan segala sesuatu yang terkandung dalam array yang ditentukan di atas, penggunaan memori pemecah yang sebenarnya adalah sekitar 216 kB. Bagian utama dari penggunaan memori berasal dari array yang berisi semua teka-teki, dan penangan I / O di Jawa.

EDIT : Saya memiliki versi yang diterjemahkan ke C ++ sekarang, tetapi tidak jauh lebih cepat. Waktu resmi sekitar 3,5 detik, yang bukan peningkatan besar. Saya pikir masalah utama dengan implementasi saya adalah bahwa saya menjaga topeng saya sebagai array daripada bitmask. Saya akan mencoba menganalisis solusi Arnauld untuk melihat apa yang bisa dilakukan untuk memperbaikinya.

import java.util.HashMap;
import java.util.ArrayList;
import java.util.Arrays;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.File;
import java.io.PrintWriter;

public class Sudoku {   

    final private int[] unsolvedBoard;
    final private int[] solvedBoard; 
    final private int[][] neighbors;
    final private int[][] cells;

    private static int[] clues;
    final private int[][] mask;
    final private int[] formattedMask;
    final private int[][] placedMask;
    final private boolean[][][] lineMask;
    final private int[] lineCounters;
    final private int[][] sectionCounters;
    final private int[][] sectionMask;

    private int easySolved;
    private boolean isEasy;
    private int totEasy;
    private int placedNumbers;
    public long totTime = 0;
    private boolean solutionFound;
    public long lastPrint;
    private boolean shouldPrint;
    private boolean isImpossible = false;

    public Sudoku() {
        mask = new int[81][9];
        formattedMask = new int[81];
        placedMask = new int[64][64];
        lineMask = new boolean[64][81][9];
        sectionCounters = new int[9][27];
        sectionMask = new int[9][27];
        lineCounters = new int[64];
        neighbors = new int[81][20];
        unsolvedBoard = new int[81];
        solvedBoard = new int[81];
        cells = new int[][] {{0 ,1 ,2 ,9 ,10,11,18,19,20},
                             {3 ,4 ,5 ,12,13,14,21,22,23},
                             {6 ,7 ,8 ,15,16,17,24,25,26},
                             {27,28,29,36,37,38,45,46,47},
                             {30,31,32,39,40,41,48,49,50},
                             {33,34,35,42,43,44,51,52,53},
                             {54,55,56,63,64,65,72,73,74},
                             {57,58,59,66,67,68,75,76,77},
                             {60,61,62,69,70,71,78,79,80}};
    }

    final public long solveSudoku(int[] board, int clue) {

        long t1 = 0,t2 = 0;
        t1 = System.nanoTime();
        System.arraycopy(board, 0, unsolvedBoard, 0, 81);
        System.arraycopy(board, 0, solvedBoard, 0, 81);

        placedNumbers = 0;
        solutionFound = false;
        isEasy = true;
        isImpossible = false;

        for (int[] i : mask) {
            Arrays.fill(i, 0);
        }

        for (boolean[][] i : lineMask) {
            for (boolean[] j : i) {
                Arrays.fill(j, false);
            }
        }

        for (int i = 0; i < 81; i++) {
            if (solvedBoard[i] != -1) {
                put(i, solvedBoard[i]);
                placedNumbers++;
            }
        }

        solve(0, 0);
        t2 = System.nanoTime();
        easySolved += isEasy ? 1 : 0;

        if (solutionFound && placedNumbers == 81) {
            totTime += t2-t1;
            if (shouldPrint || t2-t1 > 5*1_000_000_000L) {
                System.out.print(String.format(
                    "Solution from %2d clues found in %7s", 
                    clue, 
                    printTime(t1, t2)
                ));
                shouldPrint = false;
                if (t2-t1 > 1*1000_000_000L) {
                    System.out.println();
                    display2(board, solvedBoard);
                }
            }
        } else {
            System.out.println("No solution");
            display2(unsolvedBoard, solvedBoard);
            return -1;
        }
        return t2 - t1;
    }

    final private void solve(int v, int vIndex) {

        lineCounters[vIndex] = 0;
        int easyIndex = placeEasy(vIndex);

        if (isImpossible) {
            resetEasy(vIndex, easyIndex);
            resetLineMask(vIndex);
            return;
        }

        if (placedNumbers == 81) {
            solutionFound = true;
            return;
        }
        // if (true) {
            // return;
        // }

        // either get the next empty cell
        // while (v < 81 && solvedBoard[v] >= 0) {
            // v++;
        // }
        // or get the cell with the fewest options
        generateFormattedMasks();
        int minOptions = 9;
        for (int i = 0; i < 81; i++) {
            int options = formattedMask[i] & 0xffff;
            if (options > 0 && options < minOptions) {
                minOptions = options;
                v = i;
            }
            if (options == 0 && solvedBoard[i] == -1) {
                isImpossible = true;
            }
        }
        if (!isImpossible) {
            for (int c = 0; c < 9; c++) {
                if (isPossible(v, c)) {
                    isEasy = false;
                    put(v, c);
                    placedNumbers++;
                    solve(v + 1, vIndex + 1); 
                    if (solutionFound) {
                        return;
                    }
                    unput(v, c);
                    placedNumbers--;
                }
            }
        }
        resetEasy(vIndex, easyIndex);
        resetLineMask(vIndex);
    }

    final private void resetEasy(int vIndex, int easyIndex) {
        for (int i = 0; i < easyIndex; i++) {
            int tempv2 = placedMask[vIndex][i];
            int c2 = solvedBoard[tempv2];
            unput(tempv2, c2);
            placedNumbers--;
        }
    }

    final private void resetLineMask(int vIndex) {
        if (lineCounters[vIndex] > 0) {
            for (int i = 0; i < 81; i++) {
                for (int c = 0; c < 9; c++) {
                    if (lineMask[vIndex][i][c]) {
                        enable(i, c);
                        lineMask[vIndex][i][c] = false;
                    }
                }
            }
        }       
        isImpossible = false;
    }

    final private int placeEasy(int vIndex) {
        int easyIndex = 0;
        int lastPlaced = 0, tempPlaced = 0, easyplaced = 0;
        int iter = 0;
        while (placedNumbers > lastPlaced+1) {
            lastPlaced = placedNumbers;
            tempPlaced = 0;
            while (placedNumbers > tempPlaced + 5) {
                tempPlaced = placedNumbers;
                easyIndex = placeNakedSingles(vIndex, easyIndex);
                if (isImpossible) {
                    return easyIndex;
                }
            }

            tempPlaced = 0;
            while (placedNumbers < 55*1 && placedNumbers > tempPlaced + 2) {
                tempPlaced = placedNumbers;
                easyIndex = placeHiddenSingles(vIndex, easyIndex);
                if (isImpossible) {
                    return easyIndex;
                }
            }

            tempPlaced = 0;
            while (placedNumbers < 65*1 && placedNumbers > tempPlaced + 1) {
                tempPlaced = placedNumbers;
                easyIndex = placeNakedSingles(vIndex, easyIndex);
                if (isImpossible) {
                    return easyIndex;
                }
            }

            if (iter < 2 && placedNumbers < 55*1) {
                checkNakedTriples(vIndex);
            }
            if (placedNumbers < 45*1) {
                checkNakedDoubles(vIndex);
                identifyLines(vIndex);
            }
            iter++;
        }
        return easyIndex;
    }

    final private int placeNakedSingles(int vIndex, int easyIndex) {
        generateFormattedMasks();
        for (int tempv = 0; tempv < 81; tempv++) {
            int possibilities = formattedMask[tempv];
            if ((possibilities & 0xffff) == 1) {
                possibilities >>= 16;
                int c = 0;
                while ((possibilities & 1) == 0) {
                    possibilities >>= 1;
                    c++;
                }
                if (isPossible(tempv, c)) {
                    put(tempv, c);
                    placedMask[vIndex][easyIndex++] = tempv;
                    placedNumbers++;
                } else {
                    isImpossible = true;
                    return easyIndex;
                }
            } else if (possibilities == 0 && solvedBoard[tempv] == -1) {
                isImpossible = true;
                return easyIndex;
            }
        }
        return easyIndex;
    }


    final private int placeHiddenSingles(int vIndex, int easyIndex) {
        for (int[] i : sectionCounters) {
            Arrays.fill(i, 0);
        }

        for (int c = 0; c < 9; c++) {
            for (int v = 0; v < 81; v++) {
                if (isPossible(v, c)) {
                    int cell = 3 * (v / 27) + ((v / 3) % 3);
                    sectionCounters[c][v / 9]++;
                    sectionCounters[c][9 + (v % 9)]++;
                    sectionCounters[c][18 + cell]++;
                    sectionMask[c][v / 9] = v;
                    sectionMask[c][9 + (v % 9)] = v;
                    sectionMask[c][18 + cell] = v;
                }
            }

            int v;

            for (int i = 0; i < 9; i++) {
                if (sectionCounters[c][i] == 1) {
                    v = sectionMask[c][i];
                    if (isPossible(v, c)) {
                        put(v, c);
                        placedMask[vIndex][easyIndex++] = v;
                        placedNumbers++;
                        int cell = 3 * (v / 27) + ((v / 3) % 3);
                        sectionCounters[c][9 + (v%9)] = 9;
                        sectionCounters[c][18 + cell] = 9;
                    } else {
                        isImpossible = true;
                        return easyIndex;
                    }
                }
            }

            for (int i = 9; i < 18; i++) {
                if (sectionCounters[c][i] == 1) {
                    v = sectionMask[c][i];
                    if (isPossible(v, c)) {
                        put(v, c);
                        placedMask[vIndex][easyIndex++] = v;
                        int cell = 3 * (v / 27) + ((v / 3) % 3);
                        placedNumbers++;
                        sectionCounters[c][18 + cell]++;
                    } else {
                        isImpossible = true;
                        return easyIndex;
                    }
                }
            }


            for (int i = 18; i < 27; i++) {
                if (sectionCounters[c][i] == 1) {
                    v = sectionMask[c][i];
                    if (isPossible(v, c)) {
                        put(v, c);
                        placedMask[vIndex][easyIndex++] = v;
                        placedNumbers++;
                    } else {
                        isImpossible = true;
                        return easyIndex;
                    }
                }
            }

        }
        return easyIndex;
    }

    final private int getFormattedMask(int v) {
        if (solvedBoard[v] >= 0) {
            return 0;
        }
        int x = 0;
        int y = 0;
        for (int c = 8; c >= 0; c--) {
            x <<= 1;
            x += mask[v][c] == 0 ? 1 : 0;
            y += mask[v][c] == 0 ? 1 : 0;
        }
        x <<= 16;
        return x + y;
    }

    final private int getCachedMask(int v) {
        return formattedMask[v];
    }

    final private void generateFormattedMasks() {
        for (int i = 0; i < 81; i++) {
            formattedMask[i] = getFormattedMask(i);
        }
    }

    final private void generateFormattedMasks(int[] idxs) {
        for (int i : idxs) {
            formattedMask[i] = getFormattedMask(i);
        }
    }


    final private void checkNakedDoubles(int vIndex) {
        generateFormattedMasks();
        for (int i = 0; i < 81; i++) {
            int bitmask = formattedMask[i];
            if ((bitmask & 0xffff) == 2) {
                for (int j = i+1; j < (i/9+1)*9; j++) {
                    int bitmask_j = formattedMask[j];
                    if (bitmask == bitmask_j) {
                        bitmask >>= 16;
                        int c0, c1, k = 0;
                        while ((bitmask & 1) == 0) {
                            k++;
                            bitmask >>= 1;
                        }
                        c0 = k;
                        bitmask >>= 1;
                        k++;
                        while ((bitmask & 1) == 0) {
                            k++;
                            bitmask >>= 1;
                        }
                        c1 = k;
                        for (int cell = (i/9)*9; cell < (i/9+1)*9; cell++) {
                            if (cell != i && cell != j) {
                                if (!lineMask[vIndex][cell][c0]) {
                                    disable(cell, c0);
                                    lineMask[vIndex][cell][c0] = true;
                                    lineCounters[vIndex]++;
                                }
                                if (!lineMask[vIndex][cell][c1]) {
                                    disable(cell, c1);
                                    lineMask[vIndex][cell][c1] = true;
                                    lineCounters[vIndex]++;
                                }
                            }
                        }
                    }
                }
            }
        }

        for (int idx = 0; idx < 81; idx++) {
            int i = (idx%9)*9 + idx/9;
            int bitmask = formattedMask[i];
            if ((bitmask & 0xffff) == 2) {
                for (int j = i+9; j < 81; j += 9) {
                    int bitmask_j = formattedMask[j];
                    if (bitmask == bitmask_j) {
                        bitmask >>= 16;
                        int c0, c1, k = 0;
                        while ((bitmask & 1) == 0) {
                            k++;
                            bitmask >>= 1;
                        }
                        c0 = k;
                        bitmask >>= 1;
                        k++;
                        while ((bitmask & 1) == 0) {
                            k++;
                            bitmask >>= 1;
                        }
                        c1 = k;
                        for (int cell = i % 9; cell < 81; cell += 9) {
                            if (cell != i && cell != j) {
                                if (!lineMask[vIndex][cell][c0]) {
                                    disable(cell, c0);
                                    lineMask[vIndex][cell][c0] = true;
                                    lineCounters[vIndex]++;
                                }
                                if (!lineMask[vIndex][cell][c1]) {
                                    disable(cell, c1);
                                    lineMask[vIndex][cell][c1] = true;
                                    lineCounters[vIndex]++;
                                }
                            }
                        }
                    }
                }
            }
        }

        for (int idx = 0; idx < 9; idx++) {
            for (int i = 0; i < 9; i++) {
                int bitmask = formattedMask[cells[idx][i]];
                if ((bitmask & 0xffff) == 2) {
                    for (int j = i+1; j < 9; j++) {
                        int bitmask_j = formattedMask[cells[idx][j]];
                        if (bitmask == bitmask_j) {
                            bitmask >>= 16;
                            int c0, c1, k = 0;
                            while ((bitmask & 1) == 0) {
                                k++;
                                bitmask >>= 1;
                            }
                            c0 = k;
                            bitmask >>= 1;
                            k++;
                            while ((bitmask & 1) == 0) {
                                k++;
                                bitmask >>= 1;
                            }
                            c1 = k;
                            for (int cellIdx = 0; cellIdx < 9; cellIdx++) {
                                if (cellIdx != i && cellIdx != j) {
                                    int cell = cells[idx][cellIdx];
                                    if (!lineMask[vIndex][cell][c0]) {
                                        disable(cell, c0);
                                        lineMask[vIndex][cell][c0] = true;
                                        lineCounters[vIndex]++;
                                    }
                                    if (!lineMask[vIndex][cell][c1]) {
                                        disable(cell, c1);
                                        lineMask[vIndex][cell][c1] = true;
                                        lineCounters[vIndex]++;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    final private void checkNakedTriples(int vIndex) {

        generateFormattedMasks();

        for (int i = 0; i < 81; i++) {
            int bitmask = formattedMask[i];
            if ((bitmask & 0xffff) == 3) {
                for (int j = i+1; j < (i/9+1)*9; j++) {
                    int bitmask_j = formattedMask[j];
                    if (bitmask_j > 0 && bitmask == (bitmask | bitmask_j)) {
                        for (int k = j+1; k < (i/9+1)*9; k++) {
                            int bitmask_k = formattedMask[k];
                            if (bitmask_k > 0 && bitmask == (bitmask | bitmask_k)) {

                                int bitmask_shifted = bitmask >> 16;
                                int c0, c1, c2, l = 0;
                                while ((bitmask_shifted & 1) == 0) {
                                    l++;
                                    bitmask_shifted >>= 1;
                                }
                                c0 = l;
                                bitmask_shifted >>= 1;
                                l++;
                                while ((bitmask_shifted & 1) == 0) {
                                    l++;
                                    bitmask_shifted >>= 1;
                                }
                                c1 = l;
                                bitmask_shifted >>= 1;
                                l++;
                                while ((bitmask_shifted & 1) == 0) {
                                    l++;
                                    bitmask_shifted >>= 1;
                                }
                                c2 = l;
                                for (int cell = (i/9)*9; cell < (i/9+1)*9; cell++) {
                                    if (cell != i && cell != j && cell != k) {
                                        if (!lineMask[vIndex][cell][c0]) {
                                            disable(cell, c0);
                                            lineMask[vIndex][cell][c0] = true;
                                            lineCounters[vIndex]++;
                                        }
                                        if (!lineMask[vIndex][cell][c1]) {
                                            disable(cell, c1);
                                            lineMask[vIndex][cell][c1] = true;
                                            lineCounters[vIndex]++;
                                        }
                                        if (!lineMask[vIndex][cell][c2]) {
                                            disable(cell, c2);
                                            lineMask[vIndex][cell][c2] = true;
                                            lineCounters[vIndex]++;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        for (int idx = 0; idx < 81; idx++) {
            int i = (idx%9)*9 + idx/9;
            int bitmask = formattedMask[i];
            if ((bitmask & 0xffff) == 3) {
                for (int j = i+9; j < 81; j += 9) {
                    int bitmask_j = formattedMask[j];
                    if (bitmask_j > 0 && bitmask == (bitmask | bitmask_j)) {
                        for (int k = j+9; k < 81; k += 9) {
                            int bitmask_k = formattedMask[k];
                            if (bitmask_k > 0 && bitmask == (bitmask | bitmask_k)) {

                                int bitmask_shifted = bitmask >> 16;
                                int c0, c1, c2, l = 0;
                                while ((bitmask_shifted & 1) == 0) {
                                    l++;
                                    bitmask_shifted >>= 1;
                                }
                                c0 = l;
                                bitmask_shifted >>= 1;
                                l++;
                                while ((bitmask_shifted & 1) == 0) {
                                    l++;
                                    bitmask_shifted >>= 1;
                                }
                                c1 = l;
                                bitmask_shifted >>= 1;
                                l++;
                                while ((bitmask_shifted & 1) == 0) {
                                    l++;
                                    bitmask_shifted >>= 1;
                                }
                                c2 = l;
                                for (int cell = i%9; cell < 81; cell += 9) {
                                    if (cell != i && cell != j && cell != k) {
                                        if (!lineMask[vIndex][cell][c0]) {
                                            disable(cell, c0);
                                            lineMask[vIndex][cell][c0] = true;
                                            lineCounters[vIndex]++;
                                        }
                                        if (!lineMask[vIndex][cell][c1]) {
                                            disable(cell, c1);
                                            lineMask[vIndex][cell][c1] = true;
                                            lineCounters[vIndex]++;
                                        }
                                        if (!lineMask[vIndex][cell][c2]) {
                                            disable(cell, c2);
                                            lineMask[vIndex][cell][c2] = true;
                                            lineCounters[vIndex]++;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        for (int idx = 0; idx < 9; idx++) {
            for (int i = 0; i < 9; i++) {
                int bitmask = formattedMask[cells[idx][i]];
                if ((bitmask & 0xffff) == 3) {
                    for (int j = i+1; j < 9; j++) {
                        int bitmask_j = formattedMask[cells[idx][j]];
                        if (bitmask_j > 0 && bitmask == (bitmask | bitmask_j)) {
                            for (int k = j+1; k < 9; k++) {
                                int bitmask_k = formattedMask[cells[idx][k]];
                                if (bitmask_k > 0 && bitmask == (bitmask | bitmask_k)) {

                                    int bitmask_shifted = bitmask >> 16;
                                    int c0, c1, c2, l = 0;
                                    while ((bitmask_shifted & 1) == 0) {
                                        l++;
                                        bitmask_shifted >>= 1;
                                    }
                                    c0 = l;
                                    bitmask_shifted >>= 1;
                                    l++;
                                    while ((bitmask_shifted & 1) == 0) {
                                        l++;
                                        bitmask_shifted >>= 1;
                                    }
                                    c1 = l;
                                    bitmask_shifted >>= 1;
                                    l++;
                                    while ((bitmask_shifted & 1) == 0) {
                                        l++;
                                        bitmask_shifted >>= 1;
                                    }
                                    c2 = l;
                                    for (int cellIdx = 0; cellIdx < 9; cellIdx++) {
                                        if (cellIdx != i && cellIdx != j && cellIdx != k) {
                                            int cell = cells[idx][cellIdx];
                                            if (!lineMask[vIndex][cell][c0]) {
                                                disable(cell, c0);
                                                lineMask[vIndex][cell][c0] = true;
                                                lineCounters[vIndex]++;
                                            }
                                            if (!lineMask[vIndex][cell][c1]) {
                                                disable(cell, c1);
                                                lineMask[vIndex][cell][c1] = true;
                                                lineCounters[vIndex]++;
                                            }
                                            if (!lineMask[vIndex][cell][c2]) {
                                                disable(cell, c2);
                                                lineMask[vIndex][cell][c2] = true;
                                                lineCounters[vIndex]++;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

    }

    final private void identifyLines(int vIndex) {

        int disabledLines = 0;
        int[][] tempRowMask = new int[3][9];
        int[][] tempColMask = new int[3][9];
        for (int i = 0; i < 9; i++) {
            for (int c = 0; c < 9; c++) {
                for (int j = 0; j < 3; j++) {
                    tempRowMask[j][c] = 0;
                    tempColMask[j][c] = 0;
                }
                for (int j = 0; j < 9; j++) {
                    if (mask[cells[i][j]][c] == 0) {
                        tempRowMask[j/3][c]++;
                        tempColMask[j%3][c]++;
                    }
                }

                int rowCount = 0;
                int colCount = 0;
                int rowIdx = -1, colIdx = -1;
                for (int j = 0; j < 3; j++) {
                    if (tempRowMask[j][c] > 0) {
                        rowCount++;
                        rowIdx = j;
                    }
                    if (tempColMask[j][c] > 0) {
                        colCount++;
                        colIdx = j;
                    }
                }
                if (rowCount == 1) {
                    for (int j = (i/3)*3; j < (i/3 + 1)*3; j++) {
                        if (j != i) {
                            for (int k = rowIdx*3; k < (rowIdx+1)*3; k++) {
                                int cell = cells[j][k];
                                if (!lineMask[vIndex][cell][c]) {
                                    disable(cell, c);
                                    lineMask[vIndex][cell][c] = true;
                                    lineCounters[vIndex]++;
                                }
                            }
                        }
                    }

                }
                if (colCount == 1) {
                    for (int j = i % 3; j < 9; j += 3) {
                        if (j != i) {
                            for (int k = colIdx; k < 9; k += 3) {
                                int cell = cells[j][k];
                                if (!lineMask[vIndex][cell][c]) {
                                    disable(cell, c);
                                    lineMask[vIndex][cell][c] = true;
                                    lineCounters[vIndex]++;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    final private boolean isPossible(int v, int c) {
        return mask[v][c] == 0;
    }

    final private int checkMask(int[][] neighbors, int v, int c) {
        int tempValue = 0;
        for (int n : neighbors[v]) {
            if (mask[n][c] > 0) {
                tempValue++;
            }
        }
        return tempValue;
    }

    final private void put(int v, int c) {
        solvedBoard[v] = c;
        for (int i : neighbors[v]) {
            mask[i][c]++;
        }
        for (int i = 0; i < 9; i++) {
            mask[v][i]++;
        }
    }

    final private void disable(int v, int c) {
        mask[v][c]++;
    }

    final private void unput(int v, int c) {
        solvedBoard[v] = -1;
        for (int i : neighbors[v]) {
            mask[i][c]--;
        }
        for (int i = 0; i < 9; i++) {
            mask[v][i]--;
        }       
    }

    final private void enable(int v, int c) {
        // enables++;
        mask[v][c]--;
    }

    public String getString(int[] board) {
        StringBuilder s = new StringBuilder();
        for (int i : board) {
            s.append(i+1);
        }
        return s.toString();
    }

    public long getTime() {
        return totTime;
    }

    public static String printTime(long t1, long t2) {
        String unit = " ns";
        if (t2-t1 > 10000) {
            unit = " us";
            t1 /= 1000; t2 /= 1000;
        }
        if (t2-t1 > 10000) {
            unit = " ms";
            t1 /= 1000; t2 /= 1000;
        }
        if (t2-t1 > 10000) {
            unit = " seconds";
            t1 /= 1000; t2 /= 1000;
        }
        return (t2-t1) + unit;
    }

    public void display(int[] board) {

        for (int i = 0; i < 9; i++) {
            if (i % 3 == 0) {
                System.out.println("+-----+-----+-----+");
            }
            for (int j = 0; j < 9; j++) {
                if (j % 3 == 0) {
                    System.out.print("|");
                } else {
                    System.out.print(" ");
                }
                if (board[i*9+j] != -1) {
                    System.out.print(board[i*9+j]+1);
                } else {
                    System.out.print(" ");
                }
            }
            System.out.println("|");
        }
        System.out.println("+-----+-----+-----+");
    }

    public void display2(int[] board, int[] solved) {

        for (int i = 0; i < 9; i++) {
            if (i % 3 == 0) {
                System.out.println("+-----+-----+-----+  +-----+-----+-----+");
            }
            for (int j = 0; j < 9; j++) {
                if (j % 3 == 0) {
                    System.out.print("|");
                } else {
                    System.out.print(" ");
                }
                if (board[i*9+j] != -1) {
                    System.out.print(board[i*9+j]+1);
                } else {
                    System.out.print(" ");
                }
            }

            System.out.print("|  ");

            for (int j = 0; j < 9; j++) {
                if (j % 3 == 0) {
                    System.out.print("|");
                } else {
                    System.out.print(" ");
                }
                if (solved[i*9+j] != -1) {
                    System.out.print(solved[i*9+j]+1);
                } else {
                    System.out.print(" ");
                }
            }

            System.out.println("|");
        }
        System.out.println("+-----+-----+-----+  +-----+-----+-----+");
    }

    private boolean contains(int[] a, int v) {
        for (int i : a) {
            if (i == v) {
                return true;
            }
        }
        return false;
    }

    public void connect() {
        for (int i = 0; i < 81; i++) {
            for (int j = 0; j < 20; j++) {
                neighbors[i][j] = -1;
            }
        }
        int[] n_count = new int[81];

        HashMap<Integer,ArrayList<Integer>> map 
            = new HashMap<Integer,ArrayList<Integer>>();

        for (int[] c: cells) {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            for (int v : c) {
                temp.add(v);
            }
            for (int v : c) {
                map.put(v,temp);
            }
        }

        for (int i = 0; i < 81; i++) {
            for (int j = (i/9)*9; j < (i/9)*9 + 9; j++) {
                if (i != j) {
                    neighbors[i][n_count[i]++] = j;
                }
            }
            for (int j = i%9; j < 81; j += 9) {
                if (i != j) {
                    neighbors[i][n_count[i]++] = j;
                }
            }
            for (int j : map.get(i)) {
                if (i != j) {
                    if (!contains(neighbors[i], j)) {
                        neighbors[i][n_count[i]++] = j;
                    }
                }
            }
        }
    }

    public static int[][] getInput(String filename) {
        int[][] boards;
        try (BufferedInputStream in = new BufferedInputStream(
            new FileInputStream(filename))) {

            BufferedReader r = new BufferedReader(
                new InputStreamReader(in, StandardCharsets.UTF_8));
            int n = Integer.valueOf(r.readLine());
            boards = new int[n][81];
            clues = new int[n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < 81; j++) {
                    int x = r.read();
                    boards[i][j] = x - 49;
                    clues[i] += x > 48 ? 1 : 0;
                }
                r.read();
            }
            r.close();
        } catch (IOException ex) {
            throw new RuntimeException(ex);
        }
        return boards;
    }

    private int getTotEasy() {
        return totEasy;
    }

    public String getSolution() {
        StringBuilder s = new StringBuilder(256);
        for (int i : unsolvedBoard) {
            s.append(i+1);
        }
        s.append(",");
        for (int i : solvedBoard) {
            s.append(i+1);
        }
        return s.toString();
    }

    public static void main (String[] args) {
        long t0 = System.nanoTime();
        Sudoku gc = new Sudoku();
        File f;
        PrintWriter p;
        try {
            f = new File("sudoku_output.txt");
            p = new PrintWriter(f);
        } catch (Exception e) {
            return;
        }
        if (args.length != 1) {
            System.out.println("Usage: java Sudoku <input_file>");
            return;
        }
        int[][] boards = gc.getInput(args[0]);
        long tinp = System.nanoTime();
        gc.connect();
        long t1 = System.nanoTime();
        p.println(boards.length);

        long maxSolveTime = 0;
        int maxSolveIndex = 0;
        long[] solveTimes = new long[boards.length];
        for (int i = 0; i < boards.length; i++) {
            long tempTime = System.nanoTime();
            if (tempTime - gc.lastPrint > 200_000_000 
                || i == boards.length - 1) {

                gc.shouldPrint = true;
                gc.lastPrint = tempTime;
                System.out.print(String.format(
                    "\r(%7d/%7d) ", i+1, boards.length));
            }
            long elapsed = gc.solveSudoku(boards[i], gc.clues[i]);
            if (elapsed == -1) {
                System.out.println("Impossible: " + i);
            }
            if (elapsed > maxSolveTime) {
                maxSolveTime = elapsed;
                maxSolveIndex = i;
            }
            solveTimes[i] = elapsed;
            p.println(gc.getSolution());
            // break;
        }

        p.close();
        long t2 = System.nanoTime();
        Arrays.sort(solveTimes);
        System.out.println();
        System.out.println("Median solve time: " 
            + gc.printTime(0, solveTimes[boards.length/2]));
        System.out.println("Longest solve time: " 
            + gc.printTime(0, maxSolveTime) + " for board " + maxSolveIndex);
        gc.display(boards[maxSolveIndex]);
        System.out.println();

        System.out.println("Total time (including prints): " 
            + gc.printTime(t0,t2));
        System.out.println("Sudoku solving time: " 
            + gc.printTime(0,gc.getTime()));
        System.out.println("Average time per board: " 
            + gc.printTime(0,gc.getTime()/boards.length));
        System.out.println("Number of one-choice digits per board: " 
            + String.format("%.2f", gc.getTotEasy()/(double)boards.length));  
        System.out.println("Easily solvable boards: " + gc.easySolved);
        System.out.println("\nInput time: " + gc.printTime(t0,tinp));
        System.out.println("Connect time: " + gc.printTime(tinp,t1));
        try {
            Thread.sleep(10000);
        } catch (InterruptedException e) {

        }
    }
}
maks
sumber
2

C ++ dengan Minisat (2.2.1-5) - skor resmi 11.735s

Ini sama sekali tidak secepat algoritma khusus, tetapi pendekatan yang berbeda, titik referensi yang menarik, dan mudah dimengerti.

$ clang ++ -o selesaikan -lminisat solver_minisat.cc

#include <minisat/core/Solver.h>

namespace {

using Minisat::Lit;
using Minisat::mkLit;
using namespace std;

struct SolverMiniSat {
    Minisat::Solver solver;

    SolverMiniSat() {
        InitializeVariables();
        InitializeTriadDefinitions();
        InitializeTriadOnnes();
        InitializeCellOnnes();
    }

    // normal cell literals, of which we have 9*9*9
    static Lit Literal(int row, int column, int value) {
        return mkLit(value + 9 * (column + 9 * row), true);
    }

    // horizontal triad literals, of which we have 9*3*9, starting after the cell literals
    static Lit HTriadLiteral(int row, int column, int value) {
        int base = 81 * 9;
        return mkLit(base + value + 9 * (column + 3 * row));
    }

    // vertical triad literals, of which we have 3*9*9, starting after the h_triad literals
    static Lit VTriadLiteral(int row, int column, int value) {
        int base = (81 + 27) * 9;
        return mkLit(base + value + 9 * (row + 3 * column));
    }

    void InitializeVariables() {
        for (int i = 0; i < 15 * 9 * 9; i++) {
            solver.newVar();
        }
    }

    // create an exactly-one constraint over a set of literals
    void CreateOnne(const Minisat::vec<Minisat::Lit> &literals) {
        solver.addClause(literals);
        for (int i = 0; i < literals.size() - 1; i++) {
            for (int j = i + 1; j < literals.size(); j++) {
                solver.addClause(~literals[i], ~literals[j]);
            }
        }
    }

    void InitializeTriadDefinitions() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 3; j++) {
                for (int value = 0; value < 9; value++) {
                    Lit h_triad = HTriadLiteral(i, j, value);
                    Lit v_triad = VTriadLiteral(j, i, value);
                    int j0 = j * 3 + 0, j1 = j * 3 + 1, j2 = j * 3 + 2;

                    Minisat::vec<Minisat::Lit> h_triad_def;
                    h_triad_def.push(Literal(i, j0, value));
                    h_triad_def.push(Literal(i, j1, value));
                    h_triad_def.push(Literal(i, j2, value));
                    h_triad_def.push(~h_triad);
                    CreateOnne(h_triad_def);

                    Minisat::vec<Minisat::Lit> v_triad_def;
                    v_triad_def.push(Literal(j0, i, value));
                    v_triad_def.push(Literal(j1, i, value));
                    v_triad_def.push(Literal(j2, i, value));
                    v_triad_def.push(~v_triad);
                    CreateOnne(v_triad_def);
                }
            }
        }
    }

    void InitializeTriadOnnes() {
        for (int i = 0; i < 9; i++) {
            for (int value = 0; value < 9; value++) {
                Minisat::vec<Minisat::Lit> row;
                row.push(HTriadLiteral(i, 0, value));
                row.push(HTriadLiteral(i, 1, value));
                row.push(HTriadLiteral(i, 2, value));
                CreateOnne(row);

                Minisat::vec<Minisat::Lit> column;
                column.push(VTriadLiteral(0, i, value));
                column.push(VTriadLiteral(1, i, value));
                column.push(VTriadLiteral(2, i, value));
                CreateOnne(column);

                Minisat::vec<Minisat::Lit> hbox;
                hbox.push(HTriadLiteral(3 * (i / 3) + 0, i % 3, value));
                hbox.push(HTriadLiteral(3 * (i / 3) + 1, i % 3, value));
                hbox.push(HTriadLiteral(3 * (i / 3) + 2, i % 3, value));
                CreateOnne(hbox);

                Minisat::vec<Minisat::Lit> vbox;
                vbox.push(VTriadLiteral(i % 3, 3 * (i / 3) + 0, value));
                vbox.push(VTriadLiteral(i % 3, 3 * (i / 3) + 1, value));
                vbox.push(VTriadLiteral(i % 3, 3 * (i / 3) + 2, value));
                CreateOnne(vbox);
            }
        }
    }

    void InitializeCellOnnes() {
        for (int row = 0; row < 9; row++) {
            for (int column = 0; column < 9; column++) {
                Minisat::vec<Minisat::Lit> literals;
                for (int value = 0; value < 9; value++) {
                    literals.push(Literal(row, column, value));
                }
                CreateOnne(literals);
            }
        }
    }

    bool SolveSudoku(const char *input, char *solution, size_t *num_guesses) {
        Minisat::vec<Minisat::Lit> assumptions;
        for (int row = 0; row < 9; row++) {
            for (int column = 0; column < 9; column++) {
                char digit = input[row * 9 + column];
                if (digit != '.') {
                    assumptions.push(Literal(row, column, digit - '1'));
                }
            }
        }
        solver.decisions = 0;
        bool satisfied = solver.solve(assumptions);
        if (satisfied) {
            for (int row = 0; row < 9; row++) {
                for (int column = 0; column < 9; column++) {
                    for (int value = 0; value < 9; value++) {
                        if (solver.model[value + 9 * (column + 9 * row)] ==
                            Minisat::lbool((uint8_t) 1)) {
                            solution[row * 9 + column] = value + '1';
                        }
                    }
                }
            }
        }
        *num_guesses = solver.decisions - 1;
        return satisfied;
    }
};

} //end anonymous namespace

int main(int argc, const char **argv) {
    char *puzzle = NULL;
    char solution[81];
    size_t size, guesses;

    SolverMiniSat solver;

    while (getline(&puzzle, &size, stdin) != -1) {
        int count = solver.SolveSudoku(puzzle, solution, &guesses);
        printf("%.81s:%d:%.81s\n", puzzle, count, solution);
    }
}
53x15
sumber