my try for https://www.codewars.com/kata/mine-sweeper/train/python

minesweeper.py

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
# file from https://github.com/Nircek/minesweeper-solver [edited during solving https://www.codewars.com/kata/mine-sweeper/train/python]
# licensed under MIT license

# MIT License

# Copyright (c) 2018 Nircek

# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:

# The above copyright notice and this permission notice shall be included in all
# copies or substantial portions of the Software.

# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.

from copy import deepcopy
# import random

class Minesweeper_solver:
  p = [(-1, -1), (0, -1), (1, -1),
            (-1,  0), (0,  0), (1, 0) ,
            (-1,  1), (0,  1), (1, 1) ]
  def safe_open(self,x,y):
    if x<0 or x>=self.W or y<0 or y>=self.H:
      return -1 # -1 = out of range
    return open(y,x)
  def __init__(self, W, H):
    self.returned = False
    self.W = W
    self.H = H
    self.color = True
    self.s = []
    for y in range(H):
      self.s += [[]]
      for x in range(W):
        self.s[y] += [[-2, 0, 0, u'']] # -2 = not known
  def add(self, x, y, s):
    self.s[y][x] = [s, 0, 0, self.s[y][x][3]]
  def good(self):
    for y in range(self.H):
      for x in range(self.W):
        a = self.get(x,y)[0]
        if a < 0:
          continue
        b = 0
        for p in range(1, 10):
          if self.get(x,y,p)[0] == -3:
            b += 1
        if a != b:
          return False
    return True
  def get(self, x, y, p=5):
    p -= 1
    x += self.p[p][0]
    y += self.p[p][1]
    if x<0 or x>=self.W or y<0 or y>=self.H:
      return [-1] # -1 = out of range
    return self.s[y][x]
  def set(self, x, y, z, p=5):
    p -= 1
    x += self.p[p][0]
    y += self.p[p][1]
    if x<0 or x>=self.W or y<0 or y>=self.H:
      return
    self.s[y][x] = [z, 0, 0, u'']
  def update(self):
    b = 0
    ob = -1
    while b != ob:
      for y in range(self.H):
        for x in range(self.W):
          bs = 0
          nk = 0
          for p in range(1, 10):
            if p == 5:
              continue
            a = self.get(x, y, p)
            if a[0] == -2: # not known
              nk += 1
            if a[0] == -3: # bombs
              bs += 1
          self.s[y][x][1] = bs
          self.s[y][x][2] = nk
          a = self.get(x, y)
          if a[0]-bs > nk:
            print('WARN: impossible (x', x, ' y', y, ' a', a, ')', sep='')
          elif a[0]-bs == nk:
            for p in range(1,10):
              if p == 5:
                continue
              c = self.get(x, y, p)
              if c[0] == -2:
                self.set(x, y, -3, p)
                b += 1
          elif a[0] == bs:
            for p in range(1,10):
              if p == 5:
                continue
              c = self.get(x, y, p)
              if c[0] == -2:
                self.set(x, y, -4, p) # -4 = clear
      ob = b
    rnd_bool = True
    for y in range(self.H):
      for x in range(self.W):
        if self.get(x,y)[0] == -4:
          rnd_bool = False
    if rnd_bool:
      rnd = []
      for y in range(self.H):
        for x in range(self.W):
          if self.get(x,y)[0] == -2:
            tb = True
            for p in range(1,10):
             if self.get(x,y,p)[0] > -1:
               tb = False
            if tb:
              continue
            rnd += [(x,y)]
      if len(rnd) == 0:
        return
      jj = [0]*len(rnd)
      if len(rnd) < 12:
        for i in range(2**len(rnd)):
          m = Minesweeper_solver(self.W, self.H)
          m.s = deepcopy(self.s)
          ij = []
          for j in range(len(rnd)):
            ii = i%2
            i //= 2
            ij += [ii]
          for j in range(len(rnd)):
            if ij[j]:
              m.set(rnd[j][0],rnd[j][1],-3)
          if m.good():
            for j in range(len(rnd)):
              jj[j] += ij[j]
      else:
        for i in range(2**11):
          i = random.randrange(2**len(rnd))
          m = Minesweeper_solver(self.W, self.H)
          m.s = deepcopy(self.s)
          ij = []
          for j in range(len(rnd)):
            ii = i%2
            i //= 2
            ij += [ii]
          for j in range(len(rnd)):
            if ij[j]:
              m.set(rnd[j][0],rnd[j][1],-3)
          if m.good():
            for j in range(len(rnd)):
              jj[j] += ij[j]
      rndc = rnd[jj.index(min(jj))]
      if max(jj) == 0:
        self.msg = '0/0 0%'
        self.returned = True
        return False
      else:
        self.msg = str(min(jj)) + '/' + str(max(jj)) + ' ' + str(int(1000*min(jj)/max(jj))/10) + '%'
        if int(1000*min(jj)/max(jj))/10 < 25:
          self.set(rndc[0],rndc[1],-4)
        else:
          self.returned = True
          return False


    c = False
    for y in range(self.H):
      for x in range(self.W):
        if self.get(x, y)[0] == -4:
          self.set(x, y, self.safe_open(x,y))
          c = True
    return c

def solve_mine(map, n):
  map = map.split('\n')
  for x in range(len(map)):
    map[x] = map[x].split()
  s = Minesweeper_solver(len(map[1]), len(map))
  for x in range(len(map)):
    for y in range(len(map[0])):
      a = map[x][y]
      if a == 'x':
        a = -3
      elif a == '?':
        a = -2
      else:
        a = int(a)
      s.set(y,x,a)
  while s.update():
    while s.update():
      while s.update():
        while s.update():
          pass
  if s.returned:
    return '?'
  m = ''
  for y in range(len(map)):
    for x in range(len(map[0])):
      a = s.get(x,y)[0]
      if a == -3:
        a = 'x'
      elif a == -2:
        a = '?'
      else:
        a = str(a)
      m += a + ' '
    m = m[:-1] +'\n'
  return m[:-1]