rewrote the line validation algorithms

added current dev process in readme
jonaheinke · Nov 11, 2022 · ec3af3b · ec3af3b
1 parent 30bb2fe
commit ec3af3b
Show file tree

Hide file tree

Showing 4 changed files with 123 additions and 19 deletions.
diff --git a/README.md b/README.md
@@ -13,6 +13,11 @@ This program is superior to other nonogram solvers because it can solve way more
 
 There are plenty of examples in the `example_files` folder, hand-solved solutions and their transcriptions. Some of them are marked `hard` which cannot be solved with traditional methods.
 
+## Current stage of development
+
+It can currently solve any nonogram without assumptions. But that is not really useful, because you can solve those by hand.
+I don't know why but it can't solve nonograms with assumptions for the life of it.
+
 ## Usage
 
 ### Commandline

diff --git a/nonogram_solver.py b/nonogram_solver.py
@@ -12,7 +12,8 @@
 
 import os, time, argparse, profile, pstats
 from multiprocessing import Pool, Queue
-from typing import Union, Callable, Generator
+from typing import Union, Callable
+from collections.abc import Iterator
 
 os.environ["NUMPY_EXPERIMENTAL_ARRAY_FUNCTION"] = "0" #implement_array_function takes much time (see profiler): https://stackoverflow.com/questions/61983372/is-built-in-method-numpy-core-multiarray-umath-implement-array-function-a-per
 import numpy as np
@@ -40,6 +41,16 @@ def rle(array: np.ndarray) -> tuple[np.ndarray, np.ndarray]:
 def rle_box_lengths(array: np.ndarray) -> list[int]:
 	return [l for v, l in zip(*rle(array)) if v == BOX]
 
+def rle_between_crosses(array: np.ndarray) -> list[int]:
+	result = []
+	for value in zip(array + [None], [None] + array):
+		if value == CROSS:
+			result.append(0)
+		elif i == 0 or array[i - 1] == CROSS:
+			result.append(1)
+		else:
+			result[-1] += 1
+
 
 
 # -------------------------------------------------------------------------------------------------------------------- #
@@ -70,7 +81,7 @@ def __init__(self, from_board_or_filename: Union[Nonogram, str, bytes, os.PathLi
 	# ---------------------------------------------------- PROCESSING ---------------------------------------------------- #
 	@staticmethod
 	def __min_number_width(numbers: Union[np.ndarray, list, tuple]) -> int:
-		"""Calculates the minimum required width of an array of numbers on a hypothetical puzzle board.\n
+		"""Calculates the minimum required length of an array of numbers on a hypothetical puzzle board.\n
 		Examples:
 		- [6] -> 6
 		- [1, 4] -> 6
@@ -82,36 +93,97 @@ def __check_line_solvability(numbers: list[int], line: np.ndarray) -> bool:
 		if not numbers:
 			return True
 		if line.size == 0 or NonogramSolver.__min_number_width(numbers) > line.size:
-			#print("min_number_width triggers false")
 			return False
+		"""
 		lengths = rle_box_lengths(line)
 		if not lengths:
 			return True
 		i = 0
 		for number in numbers:
 			remaining_space = number
 			while remaining_space > 0:
+				if i == len(lengths):
+					return True
 				if lengths[i] <= number:
 					remaining_space -= lengths[i] + 1
 					i += 1
 				else:
 					break
-				if i == len(lengths):
-					return True
 		return False
+		"""
+		def idk(numbers: list[int], line: np.ndarray) -> bool:
+			i = 0
+			for number in numbers:
+				position = NonogramSolver.__get_first_possible_position(number, line, i)
+				if position == -1:
+					return False
+				i = position + number + 1
+			return True
+
+		#print("Vorwärts: ", idk(numbers, line))
+		#print("Rückwärts:", idk(reversed(numbers), line[::-1]))
+		return idk(numbers, line) and idk(reversed(numbers), line[::-1])
+		#try fitting from reverse is necessary because some of the following nonassigned boxgroups can prevent the fitting of the last number(s)
+		#(1, 2), [ ×  ×▯×]
 
 	@staticmethod
 	def __check_board_solvability(nonogram: Nonogram) -> bool:
+		#print("Row solvability:")
+		#print([NonogramSolver.__check_line_solvability(numbers, line) for numbers, line in zip(nonogram.row_numbers, nonogram.board)])
+		#print("Column solvability:")
+		#print([NonogramSolver.__check_line_solvability(numbers, line) for numbers, line in zip(nonogram.column_numbers, nonogram.board.T)])
 		return all(NonogramSolver.__check_line_solvability(numbers, line) for numbers, line in zip(nonogram.row_numbers, nonogram.board)) and all(NonogramSolver.__check_line_solvability(numbers, line) for numbers, line in zip(nonogram.column_numbers, nonogram.board.T))
 
 	@staticmethod
 	def __check_board_solved(nonogram: Nonogram) -> bool:
 		if np.any(nonogram.board == EMPTY):
 			return False
 		return NonogramSolver.__check_board_solvability(nonogram)
+
+	@staticmethod
+	def __find_next_box(line: np.ndarray, line_start_at: int = 0) -> int:
+		"""Finds the next box in a line."""
+		try:
+			position = np.where(line[line_start_at:] == BOX)[0][0] + line_start_at
+		except IndexError:
+			return len(line) + 1
+		return position
+
+	@staticmethod
+	def __get_all_possible_positions(number: int, line: np.ndarray, line_start_at: int = 0) -> Iterator[int]:
+		condition = lambda i: np.all(line[i:i+number] != CROSS) and not (i + number < len(line) and line[i+number] == BOX) and not (i > 0 and line[i-1] == BOX)
+		indecies = range(line_start_at, min(len(line) - number, NonogramSolver.__find_next_box(line, line_start_at)) + 1)
+		yield from filter(condition, indecies)
+
+	@staticmethod
+	def __get_first_possible_position(number: int, line: np.ndarray, line_start_at: int = 0) -> int:
+		"""Returns the first possible position of a number inside a (possibly filled) line. Returns -1 if no position is available.\n
+		Examples:
+		- 1, '× ×▯' -> 1
+		- 2, ' ×▯  ×' -> 2"""
+		return next(NonogramSolver.__get_all_possible_positions(number, line, line_start_at), -1)
 
 	@staticmethod
-	def __get_permutations(numbers: list[int], line: np.ndarray, numbers_start_at: int = 0, line_start_at: int = 0) -> Generator[np.ndarray, None, None]:
+	def __get_permutations(numbers: list[int], line: np.ndarray, numbers_start_at: int = 0, line_start_at: int = 0) -> Iterator[np.ndarray]:
+		if numbers_start_at >= len(numbers):
+			yield line
+			return
+		number = numbers[numbers_start_at]
+		#try to position the block at every available position
+		for i in NonogramSolver.__get_all_possible_positions(number, line, line_start_at):
+			temp = line.copy()
+			temp[i:i+number] = BOX
+			if i > 0:
+				temp[line_start_at:i] = CROSS
+			if i + number < len(line) and temp[i+number] != BOX:
+				temp[i+number] = CROSS	
+			#if not NonogramSolver.__check_line_solvability(numbers, temp):
+			#	continue
+			yield from NonogramSolver.__get_permutations(numbers, temp, numbers_start_at + 1, i + number + 1)
+
+	"""
+	@staticmethod
+	def __get_permutations(numbers: list[int], line: np.ndarray, numbers_start_at: int = 0, line_start_at: int = 0) -> Iterator[np.ndarray]:
 		if numbers_start_at >= len(numbers):
 			yield line
 			return
@@ -138,11 +210,7 @@ def __get_permutations(numbers: list[int], line: np.ndarray, numbers_start_at: i
 					temp[i+number] = CROSS
 				
 				yield from NonogramSolver.__get_permutations(numbers, temp, numbers_start_at + 1, i + number)
-
-	@staticmethod
-	def get_permutations(*args):
-		#TODO: implement sanity checks
-		return NonogramSolver.__get_permutations(*args)
+	"""
 
 	@staticmethod
 	def __solve_line(numbers: list[int], line: np.ndarray) -> set[int]:
@@ -170,7 +238,7 @@ def __solve_line(numbers: list[int], line: np.ndarray) -> set[int]:
 					line[i] = CROSS
 					changed_indeces.add(i)
 
-		#if all boxes are places, fill the rest with crosses
+		#if all boxes are placed, fill the rest with crosses
 		if rle_box_lengths(line) == numbers:
 			indeces = (line == EMPTY).nonzero()[0]
 			line[line == EMPTY] = CROSS
@@ -190,16 +258,20 @@ def __solve_permutation(nonogram: Nonogram, time_update_callback: Callable = lam
 			#try to solve every row that got updated (and is because of that in the row_queue)
 			for row in row_queue.copy():
 				row_queue.remove(row)
-				if not NonogramSolver.__check_line_solvability(nonogram.row_numbers[row], nonogram.board[row]):
-					return False
 				changed_indeces = NonogramSolver.__solve_line(nonogram.row_numbers[row], nonogram.board[row])
+				for index in changed_indeces:
+					if not list(next(NonogramSolver.__get_permutations(nonogram.column_numbers[index], nonogram.board[:, index]), [])):
+						return False
 				column_queue.update(changed_indeces)
 			#try to solve every column that got updated (and is because of that in the column_queue)
 			for column in column_queue.copy():
 				column_queue.remove(column)
-				if not NonogramSolver.__check_line_solvability(nonogram.column_numbers[column], nonogram.board[:, column]):
-					return False
+				#if not NonogramSolver.__check_line_solvability(nonogram.column_numbers[column], nonogram.board[:, column]):
+				#	return False
 				changed_indeces = NonogramSolver.__solve_line(nonogram.column_numbers[column], nonogram.board[:, column])
+				for index in changed_indeces:
+					if not list(next(NonogramSolver.__get_permutations(nonogram.row_numbers[index], nonogram.board[index]), [])):
+						return False
 				row_queue.update(changed_indeces)
 
 	@staticmethod
@@ -250,6 +322,9 @@ def __solve_disproof(nonogram: Nonogram, time_update_callback: Callable = lambda
 				if contradiction[0] or contradiction[1]:
 					#print("forced value".ljust(40))
 					nonogram.board[i][j] = CROSS if contradiction[0] else BOX
+					if NonogramSolver.__solve_permutation(nonogram, time_update_callback):
+						#after finding an assumption that works, it was solvable without further assumptions
+						return True
 					if NonogramSolver.__solve_disproof(nonogram, time_update_callback, depth):
 						return True
 				#else: no conclusive assumption could be made for this cell
@@ -328,7 +403,6 @@ def print_time(self):
 	else:
 		print("Unfinished nonogram:")
 	print(nonogram)
-	print(NonogramSolver._NonogramSolver__check_board_solvability(nonogram.nonogram))
 
 	if args.profiler:
 		with open("profile.txt", "w") as f:

diff --git a/test_permutations.py b/test_permutations.py
@@ -4,10 +4,33 @@
 from nonogram import EMPTY, CROSS, BOX
 
 
-
+"""
 line = np.array([EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, BOX, EMPTY, EMPTY, CROSS, BOX])
 print(line)
 perm = list(NonogramSolver.get_permutations([2, 1], line))
 print()
 print("Result:")
-print(perm)
+print(perm)
+"""
+
+
+def find_next_box(line: np.ndarray, line_start_at: int = 0) -> int:
+	"""Finds the next box in a line."""
+	try:
+		position = np.where(line[line_start_at:] == BOX)[0][0] + line_start_at
+	except IndexError:
+		return len(line) + 1
+	return position
+
+def get_all_possible_positions(number: int, line: np.ndarray, line_start_at: int = 0):
+	condition = lambda i: np.all(line[i:i+number] != CROSS) and not (i + number < len(line) and line[i+number] == BOX) and not (i > 0 and line[i-1] == BOX)
+	indecies = range(line_start_at, min(len(line) - number, find_next_box(line, line_start_at)) + 1)
+	yield from filter(condition, indecies)
+
+
+
+line = np.array([EMPTY, EMPTY, EMPTY, CROSS, BOX, CROSS, EMPTY, EMPTY, EMPTY, EMPTY])
+print(line)
+print("Result:")
+#print(NonogramSolver._NonogramSolver__check_line_solvability([1, 3], line))
+print(list(NonogramSolver._NonogramSolver__get_all_possible_positions(3, line, 2)))
diff --git a/todo.md b/todo.md
@@ -0,0 +1,2 @@
+- phase out __check_line_solvability and __check_board_solvability or put the contents of the new for loop inside of __solve_permutation into __check_line_solvability
+- currently assumptions don't work at all