Pentominoes, full solution, sadly still broken

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()