andere opaven: acht koninginnen | boter, kaas en eieren | logiquiz | sudoku

Sudoku puzzel

Inhoud:
de puzzel
benadering
programma afloop
invoer
voorbeeld
code

Hoe zelfs de moeilijkste sudoku puzzel op te lossen (met een computer) ?

De puzzel:

De bedoeling van een sudoku puzzel is de 9x9 matrix zodanig in te vullen met de getallen 1 t/m 9 dat in iedere rij, kolom of 3x3-kwadrant die getallen maar èèn keer voorkomen. Een aantal posities al zijn ingevuld.
De gemakkelijke sudoku's kunnen opgelost worden door een kolom/rij/kwadrant te vergelijken, waarbij er nog maar een positie overblijft voor een bepaald getal. Bij de moeilijkere puzzels zijn andere strategiën nodig, bijvoorbeeld uitsluiting over meerdere kolommen/rijen/kwadranten.

Benadering:

De computer leent zich voor een ander aanpak. Aanvankelijk krijgt ieder vakje in de matrix alle mogelijke opties 1-9 toegewezen. Dan worden de reeds toegewezen (gevulde) vakjes gebruikt om de opties uit de aangrenzende vakjes weg te strepen. De resterende opties worden nu een voor een uitgeprobeerd, waarbij direkt de gekozen optie wordt doorgerekend in de aangrenzende vakjes. Soms (vaak) blijkt een ingeslagen weg niet te leiden tot een oplossing, waardoor moet worden terug gevallen naar een eerdere keuze. Dit wordt 'recursive backtracking' genoemd. Uiteindelijk resulteert dit in de (een) oplossing. Hiermee zijn zelfs de moeilijkste sudoku's op te lossen.

Programma afloop:

Allereerst wordt (eenmalig) voor ieder vakje alle aangrenzende vakjes bepaald def calcpeers(), de zgn. 'peers'. Dan wordt voor ieder vakje de resterende opties bepaald: calcpuzzle() en cleanup(). Nu wordt voor iedere cel die nog opties over heeft, deze opties een voor een doorgerekend voor de resterende opties van andere cellen: isvalidcandidate() en cleanup(). De nog 'geldige' puzzels worden opgeslagen op de 'stack' waar ze ook weer vanaf kunnen worden gehaald (pop() , last-in-first-out).

Invoeren van een puzzel:

Zie onderstaand voorbeeld. De 'task' is een getallenreeks die van links naar rechts, van boven naar beneden, aangeeft welke vakjes reeds gevuld zijn. Er zijn een aantal voorbeelden gegeven.
Door te kiezen voor disclosure = True (of False) kan de uitvoer en snelheid worden bepaald.

Voorbeeld

Voor een specifieke opgave dienen alleen de task en disclosure te worden aangepast. Zie hieronder.

De code


#!/usr/bin/env python
# -*- coding: utf-8 -*-
'''
solves a 9x9 sudoku puzzle
'''
from datetime import datetime
import sys
import time
import logging
import pytest

peers, puzzle = [], []

task = '3-65-84-- 52------- -87----31 --3-1--8- 9--863--5 -5--9-6-- 13----25- -------74 --52-63--'.replace(' ','').replace('-','0')
task = '5----31-- ---7----- --9---576 ----2493- 9---6---8 -4-89---- 162---3-- -9---1--- --56----9'.replace(' ','').replace('-','0') # easy
#task = '-------34 ---7--18- --76-4-2- 5-------- --4--8--- -2---931- -19-75--- -8-3---4- ---------'.replace(' ','').replace('-','0') # hard
# extreme   source: https://www.telegraph.co.uk/news/science/science-news/9359579/Worlds-hardest-sudoku-can-you-crack-it.html
#task = '8-------- --36----- -7--9-2-- -5---7--- ----457-- ---1---3- --1----68 --85---1- -9----4--'.replace(' ','').replace('-','0') 
#task = '--------- -----3-85 --1-2---- ---5-7--- --4---1-- -9------- 5------73 --2-1---- ----4---9'.replace(' ','').replace('-','0') # hard
task = [int(x) for x in task]

def ini_peers():
  # for each position [0..81>, make a list of peers
  # one-time operation with fixed outcome
  #  0  1  2  3  4  5  6  7  8
  #  9 10 11 12 13 14 15 16 17
  # 18 19 20 21 22 23 24 25 26
  # 27 28 29 30 31 32 33 34 35
  # 36 37 38 39 40 41 42 43 44
  # 45 46 47 48 49 50 51 52 53
  # 54 55 56 57 58 59 60 61 62
  # 63 64 65 66 67 68 69 70 71
  # 72 73 74 75 76 77 78 79 80  

  hor = [[x+y for x in [0,1,2,3,4,5,6,7,8]] for y in [0,9,18,27,36,45,54,63,72]]
  ver = [[x+y for x in [0,9,18,27,36,45,54,63,72]] for y in [0,1,2,3,4,5,6,7,8]]
  box = [[x for x in [y, y+1, y+2, y+9, y+10, y+11, y+18, y+19, y+20]] for y in [0,3,6,27,30,33,54,57,60]]
  hvb = hor+ver+box
  friends = []
  for indx in range(9**2): 
    neighbour = []
    for sublst in hvb:
      if indx in sublst:
        neighbour += sublst
    friends.append(sorted(set(neighbour) - set([indx])))
  return friends

def calcpuzzle(sudoku):
  # returns a two-dimensional list: the position in the grid, and the possible candidates for that position
  # one-time operation for this specific puzzle
  taskplus = []
  for indx in range(9**2):
    taskplus.append([9,8,7,6,5,4,3,2,1])
  for indx in range(9**2):
    if sudoku[indx] > 0:
      taskplus[indx]=[sudoku[indx]]
  return [x[:] for x in taskplus]

def printpuzzle(position):
  # outputs the puzzle in a user-friendly way, upto 'position'
  out = ''
  for x in range(9):
    for y in range(9):
      indx = 9*x + y 
      if indx <= position and len(puzzle[indx]) == 1:
        out += '{} '.format(str(puzzle[indx][0]))
      else: 
        out += '. '
    out += "\n"
  return out

def cleanup(grid, linked=None):
  # for each single candidate in the grid, remove that candidate from it's peers
  if linked is None:
    linked = peers[:]
  ischanged = True
  while ischanged:
    ischanged = False
    for indx in range(9**2):
      if len(grid[indx]) == 1:
        single = grid[indx][0]
        for neighbour in linked[indx]:
          if single in grid[neighbour] and len(grid[neighbour]) > 1:
             grid[neighbour].remove(single)
             ischanged = True
  return grid

def isvalidcandidate(positie, poging):
  # returns False if entering a candidate will corrupt the puzzle 
  # (without actually placing the candidate)
  for indx in peers[positie]:
    if puzzle[indx] == [poging]:
      #print('cannot place candidate {} in cell ({}), because there is a conflict with peer-cell ({}) with this value'.format(poging, positie, indx))
      return False
  return True

if __name__ == '__main__':
  disclosure = (input('would you like to see the intermediate steps [y] or only the end result ? ') in ['y', 'Y'])
  timerstart = datetime.now()
  peers = ini_peers()
  puzzle = calcpuzzle(task)
  puzzle = cleanup(puzzle)

  stack = []
  gridindx = 0
  stack.append([x[:] for x in puzzle])
  updatedisplay = 0
  while gridindx < 9**2:
    if len(puzzle[gridindx]) >= 1 and isvalidcandidate(gridindx, puzzle[gridindx][-1]):
      candidate = puzzle[gridindx].pop()
      stack.append([x[:] for x in puzzle])
      puzzle[gridindx] = [candidate]
      gridindx += 1
      puzzle = cleanup(puzzle)
      show = disclosure and updatedisplay != 1
      updatedisplay = 1
    else:
      puzzle = stack.pop()
      gridindx -= 1
      show = disclosure and updatedisplay != 0
      updatedisplay = 0
    if show:
      print(printpuzzle(gridindx))
      time.sleep(0.5)
      show = False

  print(printpuzzle(9**2))
  if disclosure: 
    print('done')
  else:
    timerend = datetime.now()
    delta = timerend - timerstart
    print('duration: {:0.3f} sec.'.format(delta.seconds + delta.microseconds/1000000))