Skip to content

Instantly share code, notes, and snippets.

@ttennebkram

ttennebkram/stack-question.py

Created August 2, 2020 21:02
Show Gist options
  • Save ttennebkram/a16a6a1dc6a1062bb9930f57280f6ae2 to your computer and use it in GitHub Desktop.
Save ttennebkram/a16a6a1dc6a1062bb9930f57280f6ae2 to your computer and use it in GitHub Desktop.
Download ZIP
Pentominoes, full solution, sadly still broken
Raw
stack-question.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Problem Method
# ---------------
# Similar to previous gist, but this uses the full 12 Pentominoes pieces,
# and is still generating invalid solutions
#
# I believe I've followed the Wikipedia example to the letter
# but the VERY FIRST attempt at dancing links knocks out ALL ROWS.
# So I must be doing something wrong, misunderstanding something.
#
# On advice of one Stack Overflow user I still keep going
# to also see when I have zero columns AS WELL.
# (In this case I have header row/col, so I can track columns with zero records.
# This change did change the behavior, but not convinvence that it's correct.
#
# The Problem to Solve: In English
# =================================
# I'm following this example to the letter, exact with
# a simple 3-piece Pentominoes puzzle.
# My bible for this project:
# https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X#Example
# Asking folks on Stack overflow here:
# https://stackoverflow.com/help/minimal-reproducible-example
# Note about Implementation
# ---------------------------
# This third implementation I've done of the Wikipedia Dancing Links Demo,
# this time using NumPy arrays instead of linked lists.
# So I can "cover" rows and columns with simple array delete commands.
# To backtrack and restore state, where you "uncover" previously covered rows & cols,
# instead you just keep a fresh copy of the np array as a pre-move-copy to put back in place
# if there's a need for a backtrack. The numpy copy is VERY fast, no worries.
# IMPORTS
def ___Imports___(): pass
# =============================
import re
import numpy as np
# Don't change these!
NUM_ROTAION_POSITIONS = 4
NUM_REFLECTION_VALUES = 2
SHOW_BAD_BOARDS = True
# Using this to create a very small example
USE_REDUCED_PENTO_PUZZLE = False # L, T, Y
# TODO: ^-- doesn't switch everything over
USE_SECONDARY_REDUCED_PUZZLE = False # P, U, V
# ^-- Careful with this variable, it changes a lot of things
# Tiny examples:
# * only 3 pieces vs 12
# * board is only 3x5
# Tiny Set 1: 3x5
# l l l l t
# l y t t t
# y y y y t
#
# Tiny Set 2: 3x5
# u u v v v
# u p p p v
# u u p p v
class Piece:
def clone( self ):
newPiece = Piece( self.name, self.width, self.height, self.bitmap[:] )
# state
newPiece.r = self.r
newPiece.c = self.c
newPiece.rotation = self.rotation
newPiece.reflection = self.reflection
return newPiece
def _x_clone( self, src ):
self.name = src.name
self.height = src.height
self.width = src.width
# special
self.bitmap = src.bitmap[:]
# state
self.r = src.r
self.c = src.c
self.rotation = src.rotation
self.reflection = src.reflection
# For Piece
def __repr__(self):
heading = f"Piece \"{self.name}\" is {self.height} rows by {self.width} columns.\n"
heading2 = f"at r,c {self.r},{self.c}, rotation={self.rotation}, reflection={self.reflection}\n"
buffer = '\n'.join( [ "".join( [ str(self.bitmap[y][x]) for x in range(self.width)] ) for y in range(self.height) ] )
output = heading + heading2 + buffer
return output
# For Piece
def __init__( self, name, height, width, bitmap ):
self.name = name
self.height = height
self.width = width
self.bitmap = bitmap
# ? _self.transformedBitmap = None # added by Board, since it does transforms
# can track board placement coord stats
self.r = 0
self.c = 0
self.rotation = 0
self.reflection = 0
self.possible_rotations = 0
self.possible_reflections = 0
# STATIC
def getBlankPieceBitmap( rows, cols ):
# newPiece = [ [ ' ' for x in range(cols)] for y in range(rows) ]
newPiece = [ [ 0 for x in range(cols)] for y in range(rows) ]
return newPiece
# def rotate90CounterClockwise( self, pieceObj ):
# STATIC
def rotate90CounterClockwise( pieceObj ):
# Note: Intentionally swapping height and width, to support rotated piece
dstBitmap = Piece.getBlankPieceBitmap( pieceObj.width, pieceObj.height )
srcBitmap = pieceObj.bitmap
for srcR in range( pieceObj.height ):
for srcC in range( pieceObj.width ):
value = srcBitmap[ srcR ][ srcC ]
# map to new coordinates
dstC = srcR
# In 3x3, 0->2, 1->1, 2->0
complimentC = pieceObj.width - srcC - 1
dstR = complimentC
dstBitmap[ dstR ][ dstC ] = value
# again, NOTICE we're making sure to swap row & col
newPiece = Piece( pieceObj.name, pieceObj.width, pieceObj.height, dstBitmap )
newPiece.rotation = ( pieceObj.rotation + 1 ) % NUM_ROTAION_POSITIONS # 4
newPiece.bitmap = dstBitmap
return newPiece
# cloning happens in rotate90 --^
# def rotateAsNeeded( self, pieceObj, rotation ):
# STATIC
def rotateAsNeeded( pieceObj, rotation ):
outPiece = pieceObj
for _ in range( rotation ): # 4 directions, 0,1,2,3
# outPiece = self.rotate90CounterClockwise( outPiece )
outPiece = Piece.rotate90CounterClockwise( outPiece )
return outPiece
# def reflectAsNeeded( self, pieceObj, reflection ):
# STATIC
def reflectAsNeeded( pieceObj, reflection ):
# if even number (including 0) just return original piece
if reflection % NUM_REFLECTION_VALUES == 0:
# return pieceObj
# TODO: clone, so we can add reflection state
# ^-- actually, "no reflection" is 0 anyway
# but consumer might change others...
# Ultimately I think expectation is that you're getting a copy
# TODO: wasteful to keep doing... caching -> moot point... ?
outPiece = pieceObj.clone()
# will already have bitmap filled in
return outPiece
newBitmap = []
for rowData in pieceObj.bitmap:
# reversedRowData = rowData.reverse()
rowData.reverse()
# newBitmap.append( reversedRowData )
newBitmap.append(rowData)
outPiece = Piece( pieceObj.name, pieceObj.height, pieceObj.width, newBitmap )
outPiece.reflection = reflection % NUM_REFLECTION_VALUES
outPiece.bitmap = newBitmap
return outPiece
# STATIC
# def generateAllPieceVariations( self ):
def generateAllPieceVariations():
allPieceVariations = [] # local
print( f"Debug: generateAllPieceVariations: pieces has {len(pieces)} entries", flush=True )
for i, piece in enumerate( pieces ): # alphabetical order
for rotation in range( piece.possible_rotations ):
for reflection in range( piece.possible_reflections ):
transformedPieceObj = None
if rotation == 0 and reflection == 0:
# piece already has bitmap
transformedPieceObj = piece.clone()
else:
# these do cloning
transformedPieceObj = Piece.rotateAsNeeded( piece, rotation )
transformedPieceObj = Piece.reflectAsNeeded( transformedPieceObj, reflection )
piece.transformedPiece = transformedPieceObj
allPieceVariations.append( transformedPieceObj )
## newMove = StackEntry( r, c, piece.name, rotation, reflection )
## newMove.transformedPiece = transformedPieceObj
## newMove.newBitmap = self.cloneBitmap( transformedPieceObj.bitmap )
## possibleMovesQueue.append( newMove )
return allPieceVariations
F = Piece( "f", 3, 3, [
[ 0, 1, 1 ],
[ 1, 1, 0 ],
[ 0, 1, 0 ],
]
)
F.possible_rotations = 4
F.possible_reflections = 2
I = Piece( "i", 5, 1, [
[ 1 ],
[ 1 ],
[ 1 ],
[ 1 ],
[ 1 ],
]
)
I.possible_rotations = 2
I.possible_reflections = 1
L = Piece( "l", 4, 2, [
[ 1, 0 ],
[ 1, 0 ],
[ 1, 0 ],
[ 1, 1 ],
]
)
L.possible_rotations = 4
L.possible_reflections = 2
N = Piece( "n", 2, 4, [
[ 1, 1, 0, 0 ],
[ 0, 1, 1, 1 ],
]
)
N.possible_rotations = 4
N.possible_reflections = 2
P = Piece( "p", 3, 2, [
[ 1, 1 ],
[ 1, 1 ],
[ 1, 0 ],
]
)
P.possible_rotations = 4
P.possible_reflections = 2
T = Piece( "t", 3, 3, [
[ 1, 1, 1 ],
[ 0, 1, 0 ],
[ 0, 1, 0 ],
]
)
T.possible_rotations = 4
T.possible_reflections = 1
U = Piece( "u", 2, 3, [
[ 1, 0, 1 ],
[ 1, 1, 1 ],
]
)
U.possible_rotations = 4
U.possible_reflections = 1
V = Piece( "v", 3, 3, [
[ 1, 0, 0 ],
[ 1, 0, 0 ],
[ 1, 1, 1 ],
]
)
V.possible_rotations = 4
V.possible_reflections = 1
W = Piece( "w", 3, 3, [
[ 1, 0, 0 ],
[ 1, 1, 0 ],
[ 0, 1, 1 ],
]
)
W.possible_rotations = 4
W.possible_reflections = 1
X = Piece( "x", 3, 3, [
[ 0, 1, 0 ],
[ 1, 1, 1 ],
[ 0, 1, 0 ],
]
)
X.possible_rotations = 1
X.possible_reflections = 1
Y = Piece( "y", 2, 4, [
[ 0, 0, 1, 0 ],
[ 1, 1, 1, 1 ],
]
)
Y.possible_rotations = 4
Y.possible_reflections = 2
Z = Piece( "z", 3, 3, [
[ 1, 1, 0 ],
[ 0, 1, 0 ],
[ 0, 1, 1 ],
]
)
Z.possible_rotations = 2
Z.possible_reflections = 2
# Full Set
# ===========
# the 12 pieces, Alphabetical
# Uppercase letters are actual objects of type Piece
piecesAlphabetical = [ F, I, L, N, P, T, U, V, W, X, Y, Z ]
# Code knows not to put f in the upper left corner, for example,
# since it would create a one-block hole
piecesNames = [ 'f', 'i', 'l', 'n', 'p', 't', 'u', 'v', 'w', 'x', 'y', 'z', ]
piecesStr = "filnptuvwxyz"
piecesByName = {
'f': F,
'i': I,
'l': L,
'n': N,
'p': P,
't': T,
'u': U,
'v': V,
'w': W,
'x': X,
'y': Y,
'z': Z,
}
# Tiny Examples
# -----------------
# input some tiny solutions
#
# Tiny Set 1: 3x5
# l l l l t
# l y t t t
# y y y y t
#
# Tiny Set 2: 3x5
# u u v v v
# u p p p v
# u u p p v
#
# 3x5
pieces_3x5_tinySet1 = [ L, T, Y ]
pieces_3x5_tinySet2 = [ P, U, V ]
#
# 6x5
pieces_6x5_stacked_top_bottom = [ L, P, T, U, V, Y, ]
#
# 3x10
pieces_3x10_stacked_left_right = [ L, P, T, U, V, Y, ]
# TODO: could do other combos
piecesStr_tinySet1 = "lty"
piecesNames_tinySet1 = [ 'l', 't', 'y', ]
piecesAlphabeticalReduced1 = [ L, T, Y ]
piecesByName_Reduced1 = {
'l': L,
't': T,
'y': Y,
}
piecesStr_tinySet2 = "puv"
piecesNames_tinySet2 = [ 'p', 'u', 'v', ]
piecesAlphabeticalReduced2 = [ P, U, V ]
piecesByName_Reduced2 = {
'p': P,
'u': U,
'v': V,
}
pieces = None
piecesStr = None
piecesByName = None
# Choose which piece set
# pieces = piecesAlphabetical
if USE_REDUCED_PENTO_PUZZLE:
print( f"Debug: Using REDUCED logic", flush=True )
if not USE_SECONDARY_REDUCED_PUZZLE:
print( f"Debug: Using primary reduced logic example", flush=True )
pieces = piecesAlphabeticalReduced1 # L, T, Y
piecesStr = piecesStr_tinySet1 = "lty"
piecesByName = piecesByName_Reduced1
# else DO use Secondary
else:
print( f"Debug: Using secondary reduced logic example", flush=True )
pieces = piecesAlphabeticalReduced2 # P, U, V
piecesStr = piecesStr_tinySet2 # p, u, v?
piecesByName = piecesByName_Reduced2
else:
print( f"Debug: Using FULL (vs. reduced) logic", flush=True )
pieces = piecesAlphabetical
piecesStr = "filnptuvwxyz"
piecesByName = piecesByName
# Global Variables
def ___Globals___(): pass
# ============================
# REDUCED Test mode
if USE_REDUCED_PENTO_PUZZLE:
MOVES_FILE = "moves-file-experimental.txt"
HEIGHT = 3
WIDTH = 5
# REDUCED/REDACTED Test Mode
BOARD_HEIGHT = 3
BOARD_WIDTH = 5
NUM_BLOCKS_PER_PIECE = 5
NUMBER_BOARD_CELLS = 15
# NUM_BITS = NUMBER_BOARD_CELLS + len(blocks3.pieces)
NUM_BITS = NUMBER_BOARD_CELLS + len(pieces)
print( f"Debug: globals: NUM_BITS = {NUM_BITS}" )
DATA_FILE = "moves-file-experimental.txt"
else:
# Normal / Full MODE
MOVES_FILE = "moves-file.txt"
HEIGHT = 6
WIDTH = 10
BOARD_HEIGHT = 6
BOARD_WIDTH = 10
NUM_BLOCKS_PER_PIECE = 5
NUMBER_BOARD_CELLS = 60
# NUM_BITS = NUMBER_BOARD_CELLS + len(blocks3.pieceNames)
# NUM_BITS = NUMBER_BOARD_CELLS + len(piecesNames)
NUM_BITS = NUMBER_BOARD_CELLS + len( pieces )
# STANDARD MODE
# Warning: Not everything tested for changing these...
BOARD_HEIGHT = 6
BOARD_WIDTH = 10
DATA_FILE = "moves-file.txt"
g_debug = False
# g_debug = True
DEFAULT_STACK_HEIGHT = 100
# wc -l --> 1928 moves-file.txt
# TODO: may not be used, need to trace through
_MOVES_HEIGHT = 1_928
_MOVES_WIDTH = 72
g_allPossibleMoves = []
g_rowNames = []
g_rowNamesToBitMoves = {}
g_bitMovesToRowNames = {}
# Maintains All Of Our State!
# ---------------------------
# Original NumPy board after init but before solve
g_npOrigArray = None
g_PendingSolutionPerLevel = [ None for _ in range(DEFAULT_STACK_HEIGHT) ]
# Raw Stats
g_attemptedPlacementCounter = 0
g_holesCheckCounter = 0
#
# Every valid move, including piece, position, rotation & reflection
# First 12 bits are for each piece name
# last 60 bits are for each space on the board
#
g_allPossibleMoves = []
g_rowNames = []
# Custom Exceptions
def ___Custom_Exceptions___(): pass
# =================================
class ZeroValueColumn(Exception): pass
class EmptyBoard_NoColumns(Exception): pass # this is GOOD --> check for solution
class ZeroColumns(Exception): pass
class EmptyBoard_NoRows(Exception): pass # whereas this is BAD --> backtrack
class NoIntersectingRows(Exception): pass
class NoIntersectingCols(Exception): pass
class UnexpectedPentosBoardCollision(Exception): pass
class InvalidPentosBoard(Exception): pass
class WontFitOnBoard(Exception): pass
class BlockedByPreviousPiece(Exception): pass
class InvalidHoleSize(Exception): pass
# Class
# =====================================================
# Tiny Examples
# -----------------
# input some tiny solutions
#
# Tiny Set 1: 3x5
# l l l l t
# l y t t t
# y y y y t
#
# Tiny Set 2: 3x5
# u u v v v
# u p p p v
# u u p p v
#
# the normal 12 pieces, Alphabetical
piecesAlphabetical = [ F, I, L, N, P, T, U, V, W, X, Y, Z ]
#
# 3x5
pieces_3x5_tinySet1 = [ L, T, Y ]
pieces_3x5_tinySet2 = [ P, U, V ]
#
# 6x5
pieces_6x5_stacked_top_bottom = [ L, P, T, U, V, Y, Z ]
#
# 3x10
pieces_3x10_stacked_left_right = [ L, P, T, U, V, Y, Z ]
# TODO: could do other combos
# Choose which piece set
pieces = piecesAlphabetical
# pieces = pieces_3x5_tinySet1
piecesNames = [ 'f', 'i', 'l', 'n', 'p', 't', 'u', 'v', 'w', 'x', 'y', 'z', ]
# piecesNames = [ 'l', 't', 'y', ]
_piecesStr = "filnptuvwxyz"
_piecesByName = {
'f': F,
'i': I,
'l': L,
'n': N,
'p': P,
't': T,
'u': U,
'v': V,
'w': W,
'x': X,
'y': Y,
'z': Z,
}
# aka Node, StackEntry
class Move:
# def __init__( self, encodedString ):
# "static"
def generateMoveFromString( encodedString ):
if not ( m := re.match(DECODE_MOVE_NAME_REGEX, encodedString ) ):
raise ValueError( f'Input string "{encodedString}" did not match Regex "{DECODE_MOVE_NAME_REGEX}"' )
else:
pieceName = m.group(1)
r = int( m.group(2) )
c = int( m.group(3) )
rotation = int( m.group(4) )
reflection = int( m.group(5) )
return Move( pieceName, r, c, rotation, reflection )
# self.piece = g_piecesByName[ pieceName ]
# self.transformedPiece = None
# self.prevBoardBitmap = None
# self.newBoardBitmap = None
# self.possibleMovesPointer = -1
# def __init__( self, r, c, pieceName, rotation, reflection ):
# For Move
def __init__( self, pieceName, r, c, rotation, reflection ):
self.r, self.c = r, c
self.pieceName = pieceName
def prepareBitmaps():
pass
# "color" is just a digit 1 to 9 or string
def findFirstPixel( boardBitmap, targetColor ):
for r in range( len(boardBitmap) ):
for c in range( len(boardBitmap[0]) ):
value = boardBitmap[ r ][ c ]
if value == targetColor:
return ( r, c )
return ( -1, -1 )
#
# see also https://www.geeksforgeeks.org/flood-fill-algorithm-implement-fill-paint/
# Does check for invalid r,c coordinates
#
# Used to spot holes in the board that are not a multiple of 5 spaces
def floodFill( boardBitmap, r, c, oldColor, newColor ):
if r < 0 or r >= len(boardBitmap):
return
if c < 0 or c >= len(boardBitmap[0]):
return
currColor = boardBitmap[ r ][ c ]
if currColor != oldColor:
return
else:
# The Target is a match, so change color
boardBitmap[ r ][ c ] = newColor
# Now do the recursion for the 4 Edge neighbors
# North
north_row = r - 1
north_col = c
floodFill( boardBitmap, north_row, north_col, oldColor, newColor )
# South
south_row = r + 1
south_col = c
floodFill( boardBitmap, south_row, south_col, oldColor, newColor )
# East
east_row = r
east_col = c + 1
floodFill( boardBitmap, east_row, east_col, oldColor, newColor )
# West
west_row = r
west_col = c - 1
floodFill( boardBitmap, west_row, west_col, oldColor, newColor )
# No need to "return" the board
return
# Used to spot holes in the board that are not a multiple of 5 spaces
def histogramOfNumericColors( boardBitmap ):
histogram = {}
for r in range( len(boardBitmap) ):
for c in range( len(boardBitmap[0]) ):
currValue = boardBitmap[ r ][ c ]
if re.match( "[0-9]+", currValue ):
prevCount = histogram[ currValue ] if currValue in histogram.keys() else 0
newCount = prevCount + 1
histogram[ currValue ] = newCount
return histogram
# Used to spot holes in the board that are not a multiple of 5 spaces
def checkHoleSizes( boardBitmap ):
global g_holesCheckCounter
g_holesCheckCounter += 1
# boardBitmapClone = boardBitmap[:]
boardBitmapClone = cloneBitmap( boardBitmap )
colorNumeric = 1
# Label and fill all empty-space blobs
while True:
spaceR, spaceC = findFirstPixel( boardBitmapClone, ' ' )
if spaceR < 0 or spaceC < 0:
break
colorStr = str( colorNumeric )
floodFill( boardBitmapClone, spaceR, spaceC, ' ', colorStr )
colorNumeric += 1
# Now check all hole sizes
histogram = histogramOfNumericColors( boardBitmapClone )
# print( "Trying:" )
# printBoard( boardBitmapClone )
for k,v in histogram.items():
if not v % NUM_BLOCKS_PER_PIECE == 0:
# print( "... and it Failed", flush=True )
raise InvalidHoleSize( f"Hole '{k}' size ({v}) not evenly divisible by {NUM_BLOCKS_PER_PIECE}" )
# either throws exception or returns board bitmap
# print( "... and it WORKED!", flush=True )
return boardBitmapClone
# Lowest Level of Board/Piece logic
# X, No: Modifies the board in place, so caller may wish to clone
# Returns many types of Exceptions
# Note: "name" of piece is the same string as we use to "color" the board
# Note 2: Can throw a BUNCH of Exceptions, see also Custom Exceptions
def placePieceOnBoard( bitmap, pieceObj, r, c, rotation, reflection ):
global g_attemptedPlacementCounter
g_attemptedPlacementCounter += 1
# newBoard = clone()
# newBoard = board.clone()
# newBoardBitmap = _boardBitmap[:]
newBoardBitmap = cloneBitmap( bitmap )
# Error: pieceObj.bitmap has extra None rows
for pieceR, piece_row_data in enumerate( pieceObj.bitmap ):
for pieceC, piece_value in enumerate( piece_row_data ):
# Piece bitmaps are numeric, Board bitmaps are strings/chars
#if piece_value != ' ':
if piece_value > 0:
# TODO: these will include offsets
boardR = pieceR + r
boardC = pieceC + c
# bounds checking
if boardR < 0:
raise WontFitOnBoard( f"Board Row offset less than 0 ({boardR})" )
# if boardR >= board.height:
if boardR >= len(newBoardBitmap):
# raise WontFitOnBoard( f"Board Row OFFSET too large, got {boardR} but max is only height-1 = {board.height-1}" )
raise WontFitOnBoard( f"Board Row OFFSET too large, got {boardR} but max is only height-1 = {len(newBoardBitmap)-1}" )
if boardC < 0:
raise WontFitOnBoard( f"Board Column offset less than 0 ({boardC})" )
# if boardC >= board.width:
if boardC >= len( newBoardBitmap[0] ):
# raise WontFitOnBoard( f"Board Column OFFSET too large, got {boardC} but max is only width-1 = {board.width-1}" )
raise WontFitOnBoard( f"Board Column OFFSET too large, got {boardC} but max is only width-1 = {len(newBoardBitmap[0])-1}" )
currPieceName = newBoardBitmap[ boardR ][ boardC ] # remember single-char "name" is also the "color" on the board
if currPieceName != ' ':
raise BlockedByPreviousPiece( f"Position r,c = {boardR},{boardC} already contains \"{currPieceName}\" when trying to place \"{pieceObj.name}\" pixel." )
newBoardBitmap[ boardR ][ boardC ] = pieceObj.name
# else piece value is a zero / empty space, so OK
return newBoardBitmap
## # for Board
## def __init__( self ):
## self.height = MOVES_HEIGHT
## self.width = MOVES_WIDTH
## def __init__( self, height = HEIGHT, width = WIDTH ):
## if height * width != NUMBER_BOARD_CELLS: # 60
## raise ValueError( f"{height} x {width} = {height*width} is incorrect area, must be {NUMBER_BOARD_CELLS}" )
## self.height = height
## self.width = width
## self.height = height
## self.width = width
## self.bitmap = self.getBlankBoard_asBitmap()
# v1 is the more elegant code
# v2 was very manual wrt to literal arrays
# Upgraded code goes back to v1 and adds in piece variations
def generateAllPossibleMoves_v2():
global g_allPossibleMoves # shouldn't need this since it's a reference
global g_rowNames
# allPieceVariations = blocks1.Piece.generateAllPieceVariations()
allPieceVariations = Piece.generateAllPieceVariations()
print( f"Debug: generateAllPossibleMoves_v2: New: len(v1+.generateAllPieceVariations()) = {len(allPieceVariations):,}" )
#print( f"Debug: generateAllPossibleMoves_v2: Exp: len(v3+.generateAllPieceVariations()) = {len(expPieceVariations):,}" )
# Foreach Base Piece
for i,p in enumerate( allPieceVariations ):
# for i,p in enumerate( expPieceVariations ):
# print( f"Debug: piece variation #{i+1}: {p}")
# print( f"Debug: piece variation #{i+1}: for piece {p.name}")
for r in range( BOARD_HEIGHT ):
for c in range( BOARD_WIDTH ):
# ALWAYS start with new board
# newBoard = Board()
newBitmap = getBlankBoard_asBitmap()
TODO: impl
name = p.name
nameBits = pieceNameToBinaryNumber( name )
# rowName will encode the piece/move information
rowName = p.name + '_' + str(r) + ',' + str(c) + "_rr" + str(p.rotation) + str(p.reflection)
try:
# newBitmap = newBoard.placePieceOnBoard( newBitmap, p, r, c, p.rotation, p.reflection )
newBitmap = placePieceOnBoard( newBitmap, p, r, c, p.rotation, p.reflection )
# Often won't get here due to very comm exceptions, eg: won't fit
# TODO: also check hole sizes
bitmap = newBitmap
# Check hole sizes
_ = checkHoleSizes( bitmap )
boardBits = boardBitmapToBinaryNumber( bitmap )
# Success, keep this one
finalBitmask = (nameBits << NUMBER_BOARD_CELLS) | boardBits
g_allPossibleMoves.append( finalBitmask )
g_rowNames.append( rowName )
# catch (WontFitOnBoard, BlockedByPreviousPiece) as e1:
except (WontFitOnBoard, BlockedByPreviousPiece) as e1:
# Don't even report it
# No need to save state, new board each time
# bitmap = savedBitmap
continue
except InvalidHoleSize as e2:
# bitmap = savedBitmap
continue
# end for col
# Input: grid of characters
# Output: long int with bits set
def boardBitmapToBinaryNumber( bitmap ):
counter = 0
answer = 0x0
for r in range( BOARD_HEIGHT ):
for c in range( BOARD_WIDTH ):
counter += 1
currValue = bitmap[ r ][ c ]
bit = 1 if currValue != ' ' else 0
# offset = r * BOARD_WIDTH + c
offset = (BOARD_HEIGHT - r - 1) * BOARD_WIDTH + (BOARD_WIDTH - c - 1)
# print( f"Debug: r,c {r},{c} offset={offset} counter={counter}", flush=True )
bit = bit << offset
answer |= bit
return answer
# Gives back a shifted bitmask of 12 bits
# in the proper left-to-right order
def pieceNameToBinaryNumber( name ):
# nameOffset = blocks3.piecesNames.index( name )
nameOffset = piecesNames.index( name )
# 12 -> 0, 0 -> 12
# complimentNumber = len(blocks3.piecesNames) - nameOffset - 1
complimentNumber = len(piecesNames) - nameOffset - 1
answer = 1 << complimentNumber
return answer
def ___BOARD_Init_Blanks_Clones_and_Print___(): pass
# ====================================================
# Use List Comprehensions
# Pentos Board
def printBoard_toString( boardBitmap ):
buffer = '\n'.join( [ " ".join( [ boardBitmap[y][x] for x in range(len(boardBitmap[0]))] ) for y in range(len(boardBitmap)) ] )
return buffer
# Pentos Board
def printBoard( boardBitmap ):
buffer = printBoard_toString( boardBitmap )
print( buffer, flush=True )
# Should work with either board or piece bitmap
# even though board has char-based entries and pieces have numeric bitmaps
# we don't mess with that level, just copy it over
# def cloneBoardBitmap( self, inBitmap ):
def cloneBitmap( inBitmap ):
#print( f"Debug: cloneBitmap: inBitmap IS_A {type(inBitmap)}", flush=True )
newBoard = [ [ inBitmap[y][x] for x in range(len(inBitmap[0])) ] for y in range(len(inBitmap)) ]
return newBoard
# getEmptyBoard sic
def getBlankBoard_asBitmap():
newBoard = [ [ ' ' for x in range(BOARD_WIDTH)] for y in range(BOARD_HEIGHT) ]
return newBoard
### def __repr__(self):
### heading = f"Board is {BOARD_HEIGHT} rows by {BOARD_WIDTH} columns.\n"
### buffer = '\n'.join( [ " ".join( [ bitmap[y][x] for x in range(self.width)] ) for y in range(BOARD_HEIGHT) ] )
### output = heading + buffer
### return output
def writeMovesToFile( fname=MOVES_FILE ):
print( f'Writing all possible moves ({len(g_allPossibleMoves):,}) to "{fname}"', flush=True )
with open( fname, "w" ) as fout:
for i,move in enumerate( g_allPossibleMoves ):
rowName = g_rowNames[ i ] # don't feel like using zip...
print( f"{rowName}|{move:0{NUM_BITS}b}", file=fout )
def ___Printing___(): pass
# -------------------------------
def printBoard_np( board=g_npOrigArray ):
print( board )
# Human readable move names: f_2,3_rr31
# raises UnexpectedPentosBoardCollision
# unless you tell it to shut up
# rowNumber vs. rowOffset: the data is sortof 1-based due to headers
# NumPy version
def plotMoveToBoard_np( pentoBoard, rowNumber, ignoreExceptions=False ):
fancyRowHeaderName = g_rowNames[ rowNumber-1 ]
moveName = fancyRowHeaderName
# v-- Error: IndexError: invalid index to scalar variable.
# and if it's a string, it would still work, so what is it then?
# v-- "<class 'numpy.int16'>"
#print( f"Debug: moveName IS_A {type(moveName)}", flush=True )
pieceName = moveName[ 0 ]
fullBitmap = g_rowNamesToBitMoves[ moveName ]
# boardBitmap = fullBitmap[ 12 : ]
# boardBitmap = fullBitmap[ 3 : ]
boardBitmap = fullBitmap[ len(pieces) : ]
for fullOffset, value in enumerate( boardBitmap ):
if value == "1":
rowOffset = fullOffset // BOARD_WIDTH
colOffset = fullOffset % BOARD_WIDTH
prevValue = pentoBoard[ rowOffset ][ colOffset ]
pentoBoard[ rowOffset ][ colOffset ] = pieceName
if prevValue != ' ':
# print( f"COLLISION: was '{prevValue}' now '{pieceName}'", flush=True )
if not ignoreExceptions:
raise UnexpectedPentosBoardCollision( f"At {rowOffset},{colOffset}: There was already a '{prevValue}' present when trying to place '{pieceName}'" )
# Human readable move names: f_2,3_rr31
# raises UnexpectedPentosBoardCollision
def _plotMoveToBoard( pentoBoard, rowHeaderNode, ignoreExceptions=False ):
moveName = rowHeaderNode.name
pieceName = moveName[ : 1 ]
fullBitmap = g_rowNamesToBitMoves[ moveName ]
boardBitmap = fullBitmap[ 12 : ]
for fullOffset, value in enumerate( boardBitmap ):
if value == "1":
rowOffset = fullOffset // BOARD_WIDTH
colOffset = fullOffset % BOARD_WIDTH
prevValue = pentoBoard[ rowOffset ][ colOffset ]
pentoBoard[ rowOffset ][ colOffset ] = pieceName
if prevValue != ' ':
# print( f"COLLISION: was '{prevValue}' now '{pieceName}'", flush=True )
if not ignoreExceptions:
raise UnexpectedPentosBoardCollision( f"At {rowOffset},{colOffset}: There was already a '{prevValue}' present when trying to place '{pieceName}'" )
# raises some InvalidPentosBoard
# Note: Most errors are already tripped over when trying to plot to a non-empty spot,
# so this method might not trigger.
# Conversely, although it checks the size of a piece (number of letters),
# it doesn't check their arrangement, so a few weird edges might slip by,
# but again even those would likely have already hit a plot collision as well.
def checkBoard( pentoBoard ):
histogramOfBoard = {}
for r in range( len(pentoBoard) ):
for c in range( len(pentoBoard[0]) ):
letter = pentoBoard[ r ][ c ]
if letter == ' ':
raise InvalidPentosBoard( f"Blank space found in what should be a fully-populated board at {r},{c}" )
prevCount = histogramOfBoard[ letter ] if letter in histogramOfBoard else 0
newCount = prevCount + 1
histogramOfBoard[ letter ] = newCount
for letter,count in histogramOfBoard.items():
if count % 5 != 0:
raise InvalidPentosBoard( f"Invalid character count '{letter}' = {count}, not evenly divisible by 5" )
# otherwide we're all set
# allows passthrough of UnexpectedPentosBoardCollision and InvalidPentosBoard to caller
def plotSolutionToBoard( ignoreExceptions=False ):
pentoBoard = getBlankPentominoesBoard( BOARD_HEIGHT, BOARD_WIDTH )
#for i,s in enumerate( g_PendingSolutionPerLevel ):
for i,moveRowNumber in enumerate( g_PendingSolutionPerLevel ):
if moveRowNumber is None:
break
# self.plotMoveToBoard( pentoBoard, move, ignoreExceptions=ignoreExceptions )
plotMoveToBoard_np( pentoBoard, moveRowNumber, ignoreExceptions=ignoreExceptions )
if not ignoreExceptions:
checkBoard( pentoBoard )
buffer = '\n'.join( [ " ".join( [ pentoBoard[y][x] for x in range(len(pentoBoard[0]))] ) for y in range(len(pentoBoard)) ] )
return buffer
# aka def printPendingSolution
# aka def printTentativeSolution
def printCandidateSolution():
print( "Potential Solution:" )
for i,moveOffset in enumerate( g_PendingSolutionPerLevel ):
if moveOffset is None:
break
# fancyName = g_rowNames[ moveOffset ]
fancyName = g_rowNames[ moveOffset-1 ]
print( f"\t{i:2}: {moveOffset} ({fancyName})" )
# print( "For reference, here's the original board:" )
# printBoard_v2( g_rootNodeDeepCopy )
try:
buffer = plotSolutionToBoard()
print( "Valid Solution:" )
print( 'v' * (BOARD_WIDTH * 2 - 1) )
print( buffer )
print( '^' * (BOARD_WIDTH * 2 - 1) )
except (UnexpectedPentosBoardCollision, InvalidPentosBoard) as err:
print( "INVALID SOLUTION: Problem when plotting Pentos Board:", err )
if SHOW_BAD_BOARDS:
buffer = plotSolutionToBoard( ignoreExceptions=True )
print( "INVALID Solution:" )
print( 'v' * (BOARD_WIDTH * 2 - 1) )
print( buffer )
print( '^' * (BOARD_WIDTH * 2 - 1) )
def ___Mid_Level_Logic___(self): pass
# ========================================
# updated to handle col/row numeric headers
# though it doesn't directly handle them
# gets called first (before getIntersectingColsFor...)
def findIntersectingRowsForColByColOffset_np( npArray, colOffset ):
debug = False
fullColData = npArray[ :, colOffset ]
colHeader = fullColData[ 0 ]
colData = fullColData[ 1 : ]
outRows = []
# We speak in actual offsets for the np array
# when passing between functions, so that header is INCLUDED
# but below, remember that r is off by one
for r, value in enumerate(colData):
if value:
if debug: print( f"Debug: findIntersectingRowsForColByColOffset_np: if value: BOUNDS checking: npArray has {len(npArray)} rows", flush=True )
# outRows.append( r ) # ? or not... TODO:
outRows.append( r+1 ) # compensate for header
if len(outRows) < 1:
raise NoIntersectingRows( f"Debug: findIntRowsForCol: raw colOffset={colOffset}, colHeader={colHeader}; colData={colData}" )
return outRows
# updated to handle col/row numeric headers
# gets called second
def findIntersectingColsForRowByRowOffset_np( npArray, rowOffset ):
debug = False
if debug: print( f"Debug: findIntersectingColsForRowByRowOffset_np: Top: BOUNDS checking: npArray has {len(npArray)} rows", flush=True )
# Grab the full row
fullRowData = npArray[ rowOffset ]
rowHeader = fullRowData[ 0 ]
rowData = fullRowData[ 1 : ]
outCols = []
for c, value in enumerate(rowData):
if value:
if debug: print( f"Debug: findIntersectingColsForRowByRowOffset_np: if value: BOUNDS checking: npArray has {len(npArray[0])} cols, c = {c}", flush=True )
#outCols.append( c ) # TODO: revisit
outCols.append( c+1 )
if len(outCols) < 1:
raise NoIntersectingCols( f"Debug: findIntColsForRow: raw rowOffset={rowOffset}, rowHeader={rowHeader}; rowData={rowData}" )
return outCols
def getMinColumnCountAndColumnOffset_np( npArray ):
minCount = -1
firstColWithMin = -1
# foreach column (except header)
height = npArray.shape[0]
width = npArray.shape[1]
# Check size, reminder that we have a header row and column
if width <= 1:
raise EmptyBoard_NoColumns( f"Empty Matrix (Columns); now {height} rows high x {width} cols wide, INCLUDING Headers; now data columns --> check for possible solution!" )
if height <= 1:
raise EmptyBoard_NoRows( f"Empty Matrix (Rows); now {height} rows high x {width} cols wide, INCLUDING Headers; invalid solution, backtrack" )
for c in range( 1, npArray.shape[1] ):
colData = npArray[ :, c ]
colData = colData[ 1 : ]
currColCount = sum( colData )
if minCount < 0 or currColCount < minCount:
minCount = currColCount
firstColWithMin = c
if minCount < 1:
raise ZeroValueColumn( f"Found column w sum/count of 0, this means we're not on a path to a valid solution, column={firstColWithMin}; Backtrack?" )
return minCount, firstColWithMin
def ___Counting___(): pass
# ==============================
def _updateColumnCounts():
colHeaderNode = g_rootNode.right
# For every Column
while True:
counter = 0
currNode = colHeaderNode.down
# For each data node in this column
while True:
if not currNode.isHeaderNode:
counter += 1
currNode = currNode.down
else:
break
colHeaderNode.currNodesInColumnCount = counter
colHeaderNode = colHeaderNode.right
if colHeaderNode.isRootNode:
break
return counter
# For any cell we can always go to the header
def _countColumns():
currColHeader = g_rootNode.right
# if header.next == header ... then empty
if currColHeader.isRootNode:
return 0
count = 0
seenColumnNames = set()
seenColumnNames.add( g_rootNode.name )
while True:
if currColHeader.name in seenColumnNames:
break
else:
count += 1
seenColumnNames.add( currColHeader.name )
currColHeader = currColHeader.right
return count
def ___High_Level_Logic___(self): pass
# ======================================
# Modifies array; caller's job to make copy; also returns same array instance for convenience
# reminder: arrays now have header row & col
def deleteRow_np( npArray, rowOffset ):
debug = False
# if debug: print( f"Debug: deleteRow_np: target offset = {rowOffset}, \nvvv\n{npArray}" )
if debug: print( f"Debug: deleteRow_np: target offset = {rowOffset}", flush=True )
outArray = np.delete( npArray, rowOffset, 0 )
# if debug: print( f"Debug: After: \nvvv\n{outArray}" )
return outArray
# reminder: arrays now have header row & col
def deleteCol_np( npArray, colOffset ):
debug = False
if debug: print( f"Debug: deleteCol_np: target offset = {colOffset}, \nvvv\n{npArray}" )
outArray = np.delete( npArray, colOffset, 1 )
if debug: print( f"Debug: After: \nvvv\n{outArray}" )
return outArray
"""
start w lowCount column
find intersecting rows
iterate through rows, foreach row
consider as part of the solution
get intersecting columns
^-- mark each for deletion
get intersecting rows from those cols
^-- delete all of those too!
--
TODO: idea: be careful about empty board in 1st vs 2nd try/catch
TODO: generate moves.txt from more advanced model (non-extended, now w rot/refl metadata)
"""
"""
0: In one level/iteration of Solve
we choose one column
then foreach of the intersecting rows becomes a trial branch
1: If the matrix A has no columns, (empty, no rows either)
the current partial solution is a valid solution; terminate successfully.
2: Otherwise choose a column c (deterministically).
choose the column with the fewest 1's in it
if this turns out to be a column with ZERO 1's in it then
Bad solution, backtrack, throw exception, etc
3: Choose a row r such that Ar, c = 1 (nondeterministically).
3a: Choose all rows that intersect with that column
3b: Each row represents a branch to try and solf recursively
4: Include row r in the partial solution.
see also g_PendingSolutionPerLevel and printCandidateSolution()
5: For each column j such that Ar, j = 1,
for each row i such that Ai, j = 1,
delete row i from matrix A.
delete column j from matrix A.
6: Repeat this algorithm recursively on the reduced matrix A.
"""
# updated to work w header row & col
def solve_np( inArray, level ):
debug = True # local, even if global, bad idea!?
debug_display_matrix = True
if debug: print( f"Debug: solve_np: =============\n\tLevel {level}: inMatrix dims/shape={inArray.shape}", flush=True )
if debug_display_matrix:
print( "Debug: solve_np: input array =\n", inArray, flush=True )
origArray = inArray.copy()
# Step 1: if no columns (or rows), report possible solution
height = inArray.shape[ 0 ] # do we use these vars later? other than in debug statements??
width = inArray.shape[ 1 ]
# allow room for header nodes
#if height<=1 or width<=1:
# raise EmptyBoard( f"rows={height}, cols={width}; likely indicates a Solution!" )
# Change per suggestion here: https://stackoverflow.com/a/63066717/295802
if width <= 1:
raise EmptyBoard_NoColumns( f"Empty Matrix (Columns); now {height} rows high x {width} cols wide, INCLUDING Headers; now data columns --> check for possible solution!" )
if height <= 1:
raise EmptyBoard_NoRows( f"Empty Matrix (Rows); now {height} rows high x {width} cols wide, INCLUDING Headers; invalid solution, backtrack" )
# Step 2: Choose a column
# this also gets a count and can throw exceptions
minCount = -1
chosenColumn = -1
# It's the 2nd try/except, aka try/catch, block that's got the the main logic
try:
( minCount, chosenColumn ) = getMinColumnCountAndColumnOffset_np( inArray )
if minCount < 1:
raise ZeroValueColumn( f"0 count in column {chosenColumn}" )
if debug: print( f'Debug: solve_np: Choosing Column "{chosenColumn}", Col HEADER "{inArray[0,chosenColumn]}", bit count = {minCount}', flush=True )
# Bad News: invalid solution
except ZeroValueColumn as e1:
# there's nothing that can be done here, so return the exception
# Backtracking
# clear out state
g_PendingSolutionPerLevel[ level ] = None
if debug: print( "Debug: solve_np: BACKTRACK: Encountered ZeroValueColumn, cleared state and returning exception to caller" )
raise e1
# return
# Potential GOOD NEWS
except EmptyBoard_NoColumns as e2:
# resetStateForLevel( level )
g_PendingSolutionPerLevel[ level ] = None
# We can't make a move, so must return
return
# Bad News
except EmptyBoard_NoRows as e3:
# resetStateForLevel( level )
g_PendingSolutionPerLevel[ level ] = None
# We can't make a move, so must return
# We can't make a move, so must return
# raise e3
return
# if debug: print( f'Debug: solve_np: At Level {level}, chose Column "{chosenColumn}" with {minCount} non-zero entries', flush=True )
# Step 3: Get all intersecting rows
# ---------------------------------------
rowOffsetList = findIntersectingRowsForColByColOffset_np( inArray, chosenColumn )
if debug: print( f"Debug: solve_np: Will iterate on intersecting Rows:\n\t{rowOffsetList}", flush=True )
# Each of these is a possible solution branch
for i,candidateRowOffset in enumerate(rowOffsetList):
if debug: print( f'Debug: solve_np: -----\n\tIteration {i+1} of {len(rowOffsetList)}: Trying Solution with Row "{candidateRowOffset}", and will temp add to tentative solution list. (Level = {level})', flush=True )
try:
# Create a board for this test
currCopyOfArray = origArray.copy()
# if debug: print( f"Debug: solve_np: BOUNDS checking: currCopyOfArray has {len(currCopyOfArray)} rows", flush=True )
if debug: print( f'Debug: solve_np: Raw Row offset = "{candidateRowOffset}", Row HEADER = "{currCopyOfArray[candidateRowOffset,0]}"', flush=True)
# Tracking what we will eventually remove,
# but only once, and in high to low order.
deleteRowsSet = set()
deleteColsSet = set()
# Step 4: include this row as this level's potential solution
# ------------------------------------------------------------
# g_PendingSolutionPerLevel[ level ] = candidateRowOffset
# Pull from our header column
g_PendingSolutionPerLevel[ level ] = origArray[ candidateRowOffset, 0 ]
# Step 5: Cover/DELETE all intersecting Columns and Rows and reduce the matrix
# PROBLEM STARTS HERE
# and on the first iteration
# too many things are deleted from the matrix
# -------------------------------------------------------------------------------
# if debug: print( f"Debug: solve_np: Will now DELETE all intersecting Columns and Rows (at Level {level})" )
# if debug: print( f"Debug: solve_np: BEFORE deletes: Now dims/shape={currCopyOfArray.shape}", flush=True )
intersectingCols = findIntersectingColsForRowByRowOffset_np( currCopyOfArray, candidateRowOffset )
if len(intersectingCols) < 1:
raise NoIntersectingCols( f"for candidateRowOffset={candidateRowOffset}" )
deleteColsSet.update( intersectingCols )
for c in intersectingCols:
intersectingRows = findIntersectingRowsForColByColOffset_np( currCopyOfArray, c )
deleteRowsSet.update( intersectingRows )
if len(intersectingRows) < 1:
raise NoIntersectingRows( f"For intersectingCols = {intersectingCols}")
# Now delete all the rows and cols, but in high to low order
# targetColsList = deleteColsSet[:]
targetColsList = list( deleteColsSet )
targetColsList.sort() # <-- attemping work around as .reverse is not always sorted correctly
targetColsList.reverse() # in-place reverse sorting
if debug: print( f"Debug: solve_np: will DELETE Columns {targetColsList}")
for c in targetColsList:
# currCopyOfArray = np.delete( currCopyOfArray, c, 1 ) # "axis 1" = col
currCopyOfArray = deleteCol_np( currCopyOfArray, c )
# ^-- TODO: doubt we need that
# targetRowsList = deleteRowsSet[:]
targetRowsList = list( deleteRowsSet )
targetRowsList.sort()
targetRowsList.reverse() # in-place reverse sorting TODO: though reverse would work by itself
if debug: print( f"Debug: solve_np: will DELETE {len(targetRowsList):,} Rows...")
for r in targetRowsList:
# currCopyOfArray = np.delete( currCopyOfArray, c, 0 ) # "axis 0" = row
currCopyOfArray = deleteRow_np( currCopyOfArray, r )
if debug: print( f"Debug: solve_np: AFTER deletes: Now dims/shape={currCopyOfArray.shape}", flush=True )
# Step 6: Solve the Reduced Matrix
# ---------------------------------------
# print( f"Debug: solve_np: Since no exceptions so far, will recursively call solve with level+1 = {level+1}" )
print( f"Debug: solve_np: Recursively calling solve with level+1 = {level+1}" )
solve_np( currCopyOfArray, level + 1 )
except (ZeroColumns, EmptyBoard_NoColumns):
print( "Debug: solve_np: POTENTIAL SOLUTION:" )
printCandidateSolution()
continue
# return
except (ZeroValueColumn, EmptyBoard_NoRows) as e:
# reset state
g_PendingSolutionPerLevel[ level ] = None
# Backtrack
# return or continue
# We will have already backtracked once
# And another move inside this iteration loop might be OK
# It's not the "current" board at this level, but the reduced board of move we were trying
# that was no good
continue
except Exception as err:
# cleanup this state..., not much to do ???
# the copy of the array we're using was already a burner, so let that fall out of scope and be collected, etc
g_PendingSolutionPerLevel[ level ] = None
raise err
# reset state
g_PendingSolutionPerLevel[ level ] = None
# end foreach Candidate Row
def ___Init_and_Generate_Board___(self): pass
# =======================================
def getBlankPentominoesBoard( height, width ):
newBoard = [ [ ' ' for x in range(width)] for y in range(height) ]
return newBoard
# REMINDER to Caller: add +1 for row and col due to header row
def getBlankBoard_asNumPy( height, width ):
# newNumPyBoard = np.zeros( (height, width), dtype=np.bool_ )
newNumPyBoard = np.zeros( (height, width), dtype=np.short )
print( f"Debug: New numpy array is {newNumPyBoard.shape}" )
return newNumPyBoard
def _getBlankMovesBoard_asBitmap( height, width ):
newBoard = [ [ Node(0) for x in range(width)] for y in range(height) ]
return newBoard
#
# step 1: read file in plain Python array...
# then we look at stats and request a numpy array
# need to know size first, so python first
def setupMovesBoard_np():
dataArray = []
with open( DATA_FILE, 'r' ) as fin:
while True:
line = fin.readline()
if line is None or line == "":
break
line = line.rstrip()
( rowName, rowBitsStr ) = line.split( '|' )
g_allPossibleMoves.append( rowBitsStr )
g_rowNames.append( rowName )
g_rowNamesToBitMoves[ rowName ] = rowBitsStr
g_bitMovesToRowNames[ rowBitsStr ] = rowName
newRow = []
for c in rowBitsStr:
value = int( c )
newRow.append( value )
dataArray.append( newRow )
print( f'Debug: setupMovesBoard_np: file "{DATA_FILE}" had {len(dataArray):,} elements', flush=True )
# Promote from ints to Nodes
# Also leaving room for header column and row
currNpArray = getBlankBoard_asNumPy( len(dataArray)+1, len(dataArray[0])+1 )
npHeight = currNpArray.shape[0]
npWidth = currNpArray.shape[1]
# Do the headers first
# OK that the node at 0,0 is overwritten, both call that slot 0 anyway
for r in range(npHeight):
currNpArray[ r, 0 ] = r
for c in range(npWidth):
currNpArray[ 0, c ] = c
# Now do the data nodes
for r,rowData in enumerate( dataArray ):
for c,nodeData in enumerate( rowData ):
currValue = dataArray[ r ][ c ]
currNpArray[ r+1, c+1 ] = currValue
return currNpArray
# near bottom
def main():
# Part 1: Generate all the valid Moves
# (it still writes and reads the file, cool for debugging)
# Part 2: Use the valid moves bitmask to solve Pentos
#
# Part 1:
# Generate all the moves
# (and write to a file)
# ------------------------
moves = generateAllPossibleMoves_v2()
print( f"Debug: g_allPossibleMoves ({len(g_allPossibleMoves):,}) entries: (details commented out)" )
writeMovesToFile()
#
# Part 2:
# Use the moves to solf the puzzle
# This is the "Dancing Links"/DLX stuff that I'm having trouble with
# Solve the puzzle
g_npOrigArray = setupMovesBoard_np()
print( f"Debug: main: Init array =\n{g_npOrigArray}" )
try:
print( "Debug: main: Calling solve_np ...", flush=True )
currArray = g_npOrigArray
solve_np( currArray, 0 )
except EmptyBoard_NoColumns: # TODO: don't think we can get here, if so, could add _NoRows block too
if g_debug: print( "Main: Debug: about to print solution" )
o.printCandidateSolution()
if __name__ == "__main__":
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment