API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Sep 17th, 2019
100
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.22 KB | None | 0 0
raw download clone embed print report
  1. import os
  2. import random
  3. import math
  4. import time
  5. import keyboard
  6. import pickle
  7.  
  8. matriz = [8,0,0,0,0,3,0,0,0,0,0,0,0,0,8,6,0,7,0,0,0,0,6,0,0,0,0,5,0,0,0,0,0,0,0,0,9,7,0,5,0,1,4,0,0,0,0,0,0,0,0,1,0,3,0,6,5,0,4,0,0,3,0,3,0,0,0,0,0,9,1,0,2,0,0,1,0,0,0,0,0]
  9. matriz2 = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  10. 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  11. 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
  12.  
  13. matriz4 = [0, 6, 7, 8, 0, 2, 3, 4, 1, 0, 15, 16, 9, 14, 11, 12, 1, 2, 11, 12, 5, 6, 7, 8, 9, 14, 3, 0, 0, 0, 15, 16, 9, 10, 3, 4, 1, 14, 15, 16, 13, 2, 11, 12, 5, 6, 7, 8, 13, 14, 15, 16, 9, 0, 11, 12, 5, 6, 7, 8, 1, 2, 3, 4, 2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13, 16, 15, 6, 5, 8, 7, 2, 1, 4, 3, 14, 13, 16, 15, 10, 9, 12, 11, 10, 9, 12, 11, 14, 13, 16, 15, 2, 1, 4, 3, 6, 5, 8, 7, 14, 13, 16, 15, 10, 9, 12, 11, 6, 5, 8, 7, 2, 1, 4, 3, 3, 4, 1, 2, 7, 8, 5, 6, 11, 12, 9, 10, 15, 16, 13, 14, 7, 8, 5, 6, 3, 4, 1, 2, 15, 16, 13, 14, 11, 12, 9, 10, 11, 12, 9, 10, 15, 16, 13, 14, 3, 4, 1, 2, 7, 8, 5, 6, 15, 16, 13, 14, 11, 12, 9, 10, 7, 8, 5, 6, 3, 4, 1, 2, 4, 3, 2, 1, 8, 7, 6, 5, 0, 0, 10, 9, 16, 15, 0, 13, 8, 7, 6, 0, 4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 0, 0, 12, 11, 10, 9, 16, 15, 0, 13, 4, 3, 2, 1, 8, 7, 6, 5, 16, 15, 14, 13, 12, 11, 0, 9, 8, 0, 6, 5, 4, 3, 2, 0]
  14.  
  15. def cantidadDeUnMismoCaracter(str, char):
  16. total = 0
  17. for i in range(0, len(str) - 1):
  18. if str[i] == char:
  19. total += 1
  20. return total
  21.  
  22. def verificarSiArchivoContieneCeros(file):
  23. with open(file, 'rb') as input:
  24. try:
  25. strTemp = input.read()
  26. if strTemp.find(b'0') != -1:
  27. input.close()
  28. return True
  29.  
  30. except EOFError:
  31. pass
  32. except:
  33. raise
  34. input.close()
  35. return False
  36.  
  37. def save_object(obj, filename):
  38. with open(filename, 'wb') as output: # Overwrites any existing file.
  39. try:
  40. pickle.dump(obj, output, pickle.HIGHEST_PROTOCOL)
  41. except:
  42. print("Error in save_object")
  43. output.close()
  44.  
  45. def load_object(obj, filename):
  46. with open(filename, 'rb') as input:
  47. try:
  48. obj = pickle.load(input)
  49. except EOFError:
  50. pass
  51. except:
  52. raise
  53. input.close()
  54. return obj
  55.  
  56. class Sudoku:
  57. def __init__(self, file, N=0): #agregar un sub_i para decirle en qué pos debería estar.
  58. self.file = file
  59.  
  60. if N > 0:
  61. self.createANxNEmpty(N)
  62. return
  63.  
  64. self.cells = []
  65. self.stackSolver = []
  66.  
  67. self.key_down_c = False
  68. self.key_up_c = False
  69.  
  70. f = open(file, 'r')
  71. str = f.readline()
  72. self.n = cantidadDeUnMismoCaracter(str, ',')
  73. self.nsq = int(math.sqrt(self.n));
  74. self.nn = self.n * self.n;
  75. self.precalcA = self.n * self.nsq;
  76. self.solutionCounter = 0
  77. self.saliendo = False
  78.  
  79. for i in range(self.n):
  80. str = str.replace(" ", "")
  81. columna = 0
  82. while (str != '\n' and str != ''):
  83. separatorPos = str.find(',')
  84. strTemp = str[0:separatorPos]
  85. str = str[separatorPos + 1:len(str)]
  86. self.cells.insert(i * self.n + columna, int(strTemp))
  87. columna = columna + 1
  88.  
  89. str = f.readline()
  90. f.close()
  91.  
  92. self.firstEmptyPos = self.searchFirstEmpty()
  93. self.lastEmptyPos = self.searchLastEmpty()
  94.  
  95. def saveSudoku(self):
  96. strTemp = ""
  97. for i in range(self.nn):
  98. strTemp += str(self.cells[i]) + ","
  99. if i % self.n:
  100. strTemp += "\n"
  101.  
  102. os.remove(self.file)
  103. with open(self.file, 'wb') as output:
  104. try:
  105. return
  106. except:
  107. print("Error in saveSudoku")
  108. output.close()
  109.  
  110. def createANxNEmpty(self, N):
  111. self.cells = []
  112. self.stackSolver = []
  113. self.n = N
  114. self.nsq = int(math.sqrt(self.n));
  115. self.nn = self.n * self.n;
  116. self.precalcA = self.n * self.nsq;
  117. self.solutionCounter = 0
  118. self.saliendo = False
  119. self.key_down_c = False
  120. self.key_up_c = False
  121.  
  122. for i in range(self.nn):
  123. self.cells.insert(i, 0)
  124.  
  125. self.firstEmptyPos = self.searchFirstEmpty()
  126. self.lastEmptyPos = self.searchLastEmpty()
  127.  
  128. def filaValida(self, index, value):
  129. filaActualIndex = int(index / self.n) * self.n
  130.  
  131. for i in range(self.n):
  132. if self.cells[filaActualIndex + i] == value:
  133. return False
  134.  
  135. return True
  136.  
  137. def columnaValida(self, index, value):
  138. columnaActual = index % self.n
  139.  
  140. for i in range(self.n):
  141. if self.cells[columnaActual + (i * self.n)] == value:
  142. return False
  143.  
  144. return True
  145.  
  146. def cuadranteValido(self, index, value):
  147. cuadranteLeftIndex = int((index / self.nsq) % self.nsq) * self.nsq
  148. cuadranteTopIndex = int(index / self.precalcA) * self.precalcA
  149.  
  150. for i in range (self.n):
  151. offsetLeft = int(i / self.nsq)
  152. offsetTop = i % self.nsq
  153.  
  154. if self.cells[cuadranteTopIndex + cuadranteLeftIndex + (offsetTop * self.n) + offsetLeft] == value:
  155. return False
  156.  
  157. return True
  158.  
  159. def posicionEsValida(self, index, value):
  160. return (self.filaValida(index, value) and self.columnaValida(index, value) and self.cuadranteValido(index, value))
  161.  
  162. def showSolution(self):
  163. tempStr = " " + "_" * (self.n * (self.nsq - 1) - 1) + "\n"
  164. counterTop = 0
  165. for i in range(self.nn):
  166. left = i % self.nsq
  167.  
  168. if not left:
  169. tempStr += "| "
  170.  
  171. tempStr += str(self.cells[i]) + " "
  172.  
  173. if ((i + 1) % self.n) == 0:
  174. counterTop += 1
  175.  
  176. if counterTop == self.nsq:
  177. tempStr += " |\n|" + "_" * (self.n * (self.nsq - 1) - 1) + "| \n"
  178. counterTop = 0
  179. else:
  180. tempStr += " |\n"
  181.  
  182. print(tempStr)
  183.  
  184. def searchFirstEmpty(self):
  185. for i in range(0, self.nn, 1):
  186. if self.cells[i] == 0:
  187. return i
  188. return self.nn
  189.  
  190. def searchLastEmpty(self):
  191. for i in range(self.nn - 1, -1, -1):
  192. if self.cells[i] == 0:
  193. return i
  194. return self.nn
  195.  
  196. def next(self):
  197. for i in range(self.lastEmptyPos, self.firstEmptyPos - 1, - 1):
  198. if self.cells[i] == 0:
  199. self.lastEmptyPos = i
  200. return i
  201. return self.firstEmptyPos
  202.  
  203. def keyeventsManager(self):
  204. if self.saliendo:
  205. return
  206.  
  207. if keyboard.is_pressed('c'):
  208. self.key_down_c = True
  209. return
  210.  
  211. if not keyboard.is_pressed('c') and self.key_down_c:
  212. self.key_up_c = True
  213.  
  214. if self.key_up_c:
  215. self.key_up_c = False
  216. self.key_down_c = False
  217. path = input("Ingresa el directorio para el archivo temporal, con extensión '.bk': ")
  218. save_object(self, path)
  219. self.saliendo = True
  220.  
  221. return
  222.  
  223. def solve(self, p = 0):
  224. if not (self.cells[self.firstEmptyPos] == 0):
  225. self.showSolution()
  226. return True
  227.  
  228. self.keyeventsManager()
  229.  
  230. if self.saliendo:
  231. return False
  232.  
  233. pos = self.next()
  234.  
  235. for i in range(1, self.n + 1):
  236. if self.posicionEsValida(pos, i):
  237. self.cells[pos] = i
  238. self.stackSolver.append(pos)
  239. if self.solve():
  240. return True
  241.  
  242. self.cells[pos] = 0
  243. self.lastEmptyPos = pos
  244.  
  245. if self.saliendo:
  246. return False
  247.  
  248. return False
  249.  
  250. def solveAllSolutions(self):
  251. if not (self.cells[self.firstEmptyPos] == 0):
  252. self.showSolution()
  253. self.solutionCounter += 1
  254.  
  255. if self.solutionCounter >= 10:
  256. return
  257.  
  258. pos = self.next()
  259.  
  260. for i in range(1, self.n + 1):
  261. if self.posicionEsValida(pos, i):
  262. self.cells[pos] = i
  263. self.solveAllSolutions()
  264. self.cells[pos] = 0
  265. self.lastEmptyPos = pos
  266.  
  267. def solve_all_stack(self):
  268. pos = self.next()
  269. self.stackSolver.append(1)
  270.  
  271. while len(self.stackSolver) > 0:
  272. i = self.stackSolver.pop()
  273.  
  274. if i == 1:
  275. self.keyeventsManager()
  276. if self.saliendo or self.solutionCounter >= 10:
  277. return
  278. pos = self.next()
  279.  
  280. if i > self.n:
  281. i = self.stackSolver.pop()
  282. pos = self.stackSolver.pop()
  283. self.cells[pos] = 0
  284. self.lastEmptyPos = pos
  285. self.stackSolver.append(i + 1)
  286. elif self.posicionEsValida(pos, i):
  287. self.cells[pos] = i
  288. self.stackSolver.append(pos)
  289. self.stackSolver.append(i)
  290. self.stackSolver.append(1)
  291. else:
  292. self.stackSolver.append(i + 1)
  293.  
  294. if not (self.cells[self.firstEmptyPos] == 0):
  295. self.showSolution()
  296. self.solutionCounter += 1
  297.  
  298. return False
  299.  
  300. def solve_stack(self):
  301. pos = self.next()
  302. self.stackSolver.append(1)
  303.  
  304. #(*)
  305. #if len(self.stackSolver) > 2:
  306. #self.stackSolver.pop()#deleteamos el stack de arriba sólo si es una re-entrada al solve, así seguimos trabajando sobre el stack anterior.
  307.  
  308. while len(self.stackSolver) > 0:
  309. i = self.stackSolver.pop()
  310.  
  311. if i == 1:#cuando i==1, recién entra en el solve.
  312. self.keyeventsManager() #Lo meto acá, sino me consume todo el CPU.
  313. if self.saliendo:
  314. #self.stackSolver.append(i) #No lo agrego, ya que, como será append(1), concuerda con el stack inicial del programa. (*)
  315. return False
  316. pos = self.next()
  317.  
  318. if i > self.n: #acá hubo return False
  319. i = self.stackSolver.pop()
  320. pos = self.stackSolver.pop()
  321. self.cells[pos] = 0
  322. self.lastEmptyPos = pos
  323. self.stackSolver.append(i + 1) #acá ya hubo el return, por lo que está cargando los i que faltaban. Si estaba en i=6, sigue por el 7 hasta el N.
  324. elif self.posicionEsValida(pos, i): #acá llama al solve() y hace push en la pila.
  325. self.cells[pos] = i
  326. self.stackSolver.append(pos) #stack previo
  327. self.stackSolver.append(i) #stack previo
  328. #call solve()
  329. self.stackSolver.append(1)
  330. else:
  331. self.stackSolver.append(i + 1)
  332.  
  333. if not (self.cells[self.firstEmptyPos] == 0):
  334. self.showSolution()
  335. return True
  336.  
  337. return False
  338.  
  339. def __str__(self):
  340. return "Info. Sudoku: " + str(self.cells) + " first: " + str(self.firstEmptyPos) + " last: " + str(self.lastEmptyPos)
  341.  
  342. def modo_solver():
  343. path = input("Ingrese el directorio junto con el nombre del archivo a analizar y resolver: ")
  344. test = Sudoku
  345. if path[len(path) - 2 : len(path)] == "bk":
  346. test = load_object(test, path)
  347. else:
  348. test = Sudoku(path)
  349.  
  350. print(test.cells)
  351.  
  352. tstart = time.time()
  353. test.solve_stack()
  354. totaltime = time.time() - tstart
  355. nstr = str(test.n) + "x" + str(test.n)
  356. print("Resolución de Sudoku:", nstr, "Tiempo transcurrido =", totaltime)
  357.  
  358. def modo_creator():
  359. for i in range(3, 10):
  360. test = Sudoku("", i*i)
  361. test.solutionCounter = 0
  362. tstart = time.time()
  363. #test.solveAllSolutions()
  364. test.solve_all_stack()
  365. totaltime = time.time() - tstart
  366. print("NxN / N =", i*i, "=> Tiempo transcurrido =", totaltime)
  367.  
  368. if __name__ == "__main__":
  369. print(verificarSiArchivoContieneCeros("C:\\Users\\Fernando\\Desktop\\uno.txt"))
  370. print(verificarSiArchivoContieneCeros("C:\\Users\\Fernando\\Desktop\\cero.txt"))
  371.  
  372. print("Si desea entrar en modo solver (resolver sudokus desde un archivo dado), presione 1.")
  373. print("Si desea entrar en modo creator (crear 10 sudokus posibles NxN desde 0), presione 2.")
  374. print("Recuerde que si desea guardar la solución en progreso, puede presionar Ctrl + C, y guardará en un archivo temporal para luego cargarlo y seguir solucionando el problema.")
  375.  
  376. while (True):
  377. if keyboard.is_pressed('1'):
  378. modo_solver()
  379. break
  380. elif keyboard.is_pressed('2'):
  381. modo_creator()
  382. break
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!