' ***********************************************************************
' Author   : ElektroStudios
' Modified : 28-October-2025
' ***********************************************************************

#Region " Option Statements "

Option Explicit On
Option Strict On
Option Infer Off

#End Region

#Region " Imports "

Imports System.Collections
Imports System.Collections.Generic
Imports System.Diagnostics
Imports System.Diagnostics.CodeAnalysis
Imports System.Linq
Imports System.Text

#End Region

#Region " UtilLightsOut "

Namespace Gaming.PuzzleSolving

    ''' <remarks>
    ''' Provides utility methods related with 'Lights Out' puzzles.
    ''' <para></para>
    ''' Lights Out (or Flip Tiles) is an electronic puzzle game consisting of a grid of illuminated 
    ''' (sometimes with light bulbs or switches) or numbered (originally 5x5) squares. 
    ''' The goal is to turn off all the lights in the grid.
    ''' <para></para>
    ''' At the start of the game, a pattern of squares is illuminated (in different states). 
    ''' Pressing one of the squares activates a switch, changing its state 
    ''' (from on to off, from off to on, or to a different color), 
    ''' as well as the four adjacent squares (up, right, down, and left).
    ''' <para></para>
    ''' The goal of the game is to turn off (or on) all the lights, 
    ''' preferably by pressing as few squares as possible.
    ''' </remarks>
    Public NotInheritable Class UtilLightsOut

#Region " Constructors "

        ''' <summary>
        ''' Prevents a default instance of the <see cref="UtilLightsOut"/> class from being created.
        ''' </summary>
        Private Sub New()
        End Sub

#End Region

#Region " Public Methods "

        ''' <summary>
        ''' Solves a 'Lights Out' puzzle board.
        ''' <para></para>
        ''' However, note that not all board configurations have a solution. 
        ''' If all rows have a solution except the last one—and this option can be disabled 
        ''' by clicking only on the last row—the configuration has a solution; 
        ''' otherwise, it is unsolvable.
        ''' <para></para>
        ''' Mathematically, solvability depends on the image of the matrix "A".
        ''' <para></para>
        ''' This is a visual representation of an unsolvable 3x3 board:
        ''' <para></para>◼◻◻   100
        ''' <para></para>◻◼◻   010
        ''' <para></para>◻◻◼   001
        ''' </summary>
        ''' 
        ''' <param name="board">
        ''' A two-dimensional <see cref="Byte(,)"/> array representing the initial configuration of the 'Lights Out' board grid.
        ''' <para></para>
        ''' Each element corresponds to a cell, where a value of zero indicates the cell is "off", 
        ''' and non-zero indicates the cell is "on".
        ''' <para></para>
        ''' For example:
        ''' <code>
        ''' Dim board5x5 As Byte(,) = {
        '''     {1, 1, 0, 1, 1}, ' ◼ ◼ ◻ ◼ ◼
        '''     {1, 1, 0, 0, 0}, ' ◼ ◼ ◻ ◻ ◻
        '''     {1, 0, 0, 1, 1}, ' ◼ ◻ ◻ ◼ ◼
        '''     {0, 1, 1, 0, 0}, ' ◻ ◼ ◼ ◻ ◻
        '''     {0, 0, 1, 0, 1}  ' ◻ ◻ ◼ ◻ ◼
        ''' }
        ''' </code>
        ''' </param>
        ''' 
        ''' <returns>
        ''' A two-dimensional <see cref="Byte(,)"/> array of the same dimensions as the input board.
        ''' <para></para>
        ''' Each element indicates whether the corresponding cell should be pressed to solve the puzzle:
        ''' 0 means the cell does not need to be pressed, 1 means it should be pressed once.
        ''' <para></para>
        ''' The order of pressing does not matter to solve the puzzle.
        ''' <para></para>
        ''' Example:
        ''' <code>
        ''' ' Input board (1 = on, 0 = off)
        ''' Dim board5x5 As Byte(,) = {
        '''     {1, 1, 0, 1, 1}, ' ◼ ◼ ◻ ◼ ◼
        '''     {1, 1, 0, 0, 0}, ' ◼ ◼ ◻ ◻ ◻
        '''     {1, 0, 0, 1, 1}, ' ◼ ◻ ◻ ◼ ◼
        '''     {0, 1, 1, 0, 0}, ' ◻ ◼ ◼ ◻ ◻
        '''     {0, 0, 1, 0, 1}  ' ◻ ◻ ◼ ◻ ◼
        ''' }
        ''' 
        ''' ' Solution returned by this function
        ''' Dim solution5x5 As Byte(,) = {
        '''     {0, 1, 1, 1, 0}, ' ◻ ◼ ◼ ◼ ◻
        '''     {0, 1, 1, 1, 0}, ' ◻ ◼ ◼ ◼ ◻
        '''     {0, 0, 0, 1, 1}, ' ◻ ◻ ◻ ◼ ◼
        '''     {1, 1, 0, 0, 1}, ' ◼ ◼ ◻ ◻ ◼
        '''     {0, 1, 0, 0, 0}  ' ◻ ◼ ◻ ◻ ◻
        ''' } ' ◼ = press once, 
        '''   ' ◻ = do not press
        ''' </code>
        ''' </returns>
        <DebuggerStepperBoundary>
        Public Shared Function SolveLightsOutPuzzle(board As Byte(,)) As Byte(,)

            ' Get board dimensions
            Dim rows As Integer = board.GetLength(0)
            Dim cols As Integer = board.GetLength(1)
            Dim cells As Integer = rows * cols ' total number of cells.

            ' --- 1) Build the influence matrix "A".
            ' Each row represents the effect of pressing a single cell:
            ' toggling itself and its immediate neighbors (up, down, left, right).
            Dim A As BitArray() = Enumerable.Range(0, cells).Select(
            Function(i)
                Dim r As Integer = i \ cols
                Dim c As Integer = i Mod cols
                Dim row As New BitArray(cells)

                ' Pressing the cell toggles itself.
                row(i) = True

                ' Define neighbor offsets: up, down, left, right.
                Dim dr As Integer() = {-1, 1, 0, 0}
                Dim dc As Integer() = {0, 0, -1, 1}

                ' Toggle neighbors if are inside board bounds.
                For k As Integer = 0 To 3
                    Dim nr As Integer = r + dr(k)
                    Dim nc As Integer = c + dc(k)
                    If nr >= 0 AndAlso nr < rows AndAlso nc >= 0 AndAlso nc < cols Then
                        row(nr * cols + nc) = True
                    End If
                Next k

                Return row
            End Function).ToArray()

            ' --- 2) Build the initial state vector "b".
            ' b(i) = True if the cell is "on" (non-zero), False if "off" (0).
            Dim b As New BitArray(cells)
            For r As Integer = 0 To rows - 1
                For c As Integer = 0 To cols - 1
                    b(r * cols + c) = (board(r, c) <> 0)
                Next c
            Next r

            ' --- 3) Forward elimination (Gaussian elimination mod 2).
            ' Solve the linear system: "A * x = b" (mod 2).
            For i As Integer = 0 To cells - 1
                ' If diagonal is zero, try to swap with a row below.
                If Not A(i)(i) Then
                    For k As Integer = i + 1 To cells - 1
                        If A(k)(i) Then
                            A(i).Xor(A(k)) ' XOR rows (addition mod 2).
                            b(i) = b(i) Xor b(k) ' XOR corresponding element in "b".
                            Exit For
                        End If
                    Next
                End If

                ' Eliminate current column for all rows below.
                For j As Integer = i + 1 To cells - 1
                    If A(j)(i) Then
                        A(j).Xor(A(i))
                        b(j) = b(j) Xor b(i)
                    End If
                Next j
            Next i

            ' --- 4) Back substitution.
            ' Solve for x starting from bottom row.
            Dim x As New BitArray(cells)
            For i As Integer = cells - 1 To 0 Step -1
                ' Start with right-hand side value.
                Dim sum As Boolean = b(i)

                ' Subtract contributions from already solved variables (XOR is subtraction mod 2).
                For j As Integer = i + 1 To cells - 1
                    sum = sum Xor (A(i)(j) AndAlso x(j))
                Next

                ' Assign solution for cell "i".
                x(i) = sum
            Next

            ' --- 5) Build result board (Integer(,)) of 1-based indices to press.
            Dim result(rows - 1, cols - 1) As Byte
            For i As Integer = 0 To cells - 1
                Dim r As Byte = CByte(i \ cols)
                Dim c As Byte = CByte(i Mod cols)
                result(r, c) = CByte(If(x(i), 1, 0)) ' 1 = press, 0 = don't press.
            Next

            Return result
        End Function

        ''' <summary>
        ''' Returns a visual representation of a 'Lights Out' board using custom characters for ON and OFF states.
        ''' </summary>
        ''' 
        ''' <param name="board">
        ''' A two-dimensional <see cref="Byte"/> array representing the 'Lights Out' board grid.
        ''' <para></para>
        ''' Each element corresponds to a cell, where a value of zero indicates the cell is "off", 
        ''' and non-zero indicates the cell is "on".
        ''' <para></para>
        ''' For example:
        ''' <code>
        ''' Dim board5x5 As Byte(,) = {
        '''     {1, 1, 0, 1, 1}, ' ◼ ◼ ◻ ◼ ◼
        '''     {1, 1, 0, 0, 0}, ' ◼ ◼ ◻ ◻ ◻
        '''     {1, 0, 0, 1, 1}, ' ◼ ◻ ◻ ◼ ◼
        '''     {0, 1, 1, 0, 0}, ' ◻ ◼ ◼ ◻ ◻
        '''     {0, 0, 1, 0, 1}  ' ◻ ◻ ◼ ◻ ◼
        ''' }
        ''' </code>
        ''' </param>
        ''' 
        ''' <param name="onChar">
        ''' Optional.The character used to represent an ON (active) light. 
        ''' <para></para>
        ''' Default is "◼"
        ''' </param>
        ''' 
        ''' <param name="offChar">
        ''' Optional. The character used to represent an OFF (inactive) light.
        ''' <para></para>
        ''' Default is "◻"
        ''' </param>
        ''' 
        ''' <returns>
        ''' A formatted <see cref="String"/> that visually represents the current 'Lights Out' board.
        ''' <para></para>
        ''' Example:
        ''' <code>
        ''' ' Input board (1 = on, 0 = off)
        ''' Dim board5x5 As Byte(,) = {
        '''     {1, 1, 0, 1, 1},
        '''     {1, 1, 0, 0, 0},
        '''     {1, 0, 0, 1, 1},
        '''     {0, 1, 1, 0, 0},
        '''     {0, 0, 1, 0, 1}
        ''' }
        ''' 
        ''' Format returned (◼ = on, ◻ = off):
        ''' 
        ''' ◼ ◼ ◻ ◼ ◼
        ''' ◼ ◼ ◻ ◻ ◻
        ''' ◼ ◻ ◻ ◼ ◼
        ''' ◻ ◼ ◼ ◻ ◻
        ''' ◻ ◻ ◼ ◻ ◼
        ''' </code>
        ''' </returns>
        <DebuggerStepperBoundary>
        Public Shared Function FormatLightsOutBoard(board As Byte(,),
                                                    Optional onChar As Char = "◼"c,
                                                    Optional offChar As Char = "◻"c) As String

            Dim rows As Integer = board.GetLength(0)
            Dim cols As Integer = board.GetLength(1)
            Dim maxCapacity As Integer = (rows * (cols * 2)) + rows ' (cells + white-spaces + line breaks)

            Dim sb As New StringBuilder(capacity:=maxCapacity, maxCapacity:=maxCapacity)

            For r As Integer = 0 To rows - 1
                For c As Integer = 0 To cols - 1
                    sb.Append(If(board(r, c) <> 0, onChar, offChar))
                    If c < (cols - 1) Then
                        sb.Append(" "c)
                    End If
                Next
                If r < (rows - 1) Then
                    sb.AppendLine()
                End If
            Next

            Return sb.ToString()
        End Function

        ''' <summary>
        ''' Returns a human-readable list of steps required to solve a 'Lights Out' puzzle board.
        ''' </summary>
        ''' 
        ''' <param name="board">
        ''' A two-dimensional <see cref="Byte"/> array representing the 'Lights Out' solution grid.
        ''' <para></para>
        ''' Each non-zero cell indicates that the corresponding cell should be pressed once.
        ''' <para></para>
        ''' For example:
        ''' <code>
        ''' Dim solution5x5 As Byte(,) = {
        '''     {0, 1, 1, 1, 0}, ' ◻ ◼ ◼ ◼ ◻
        '''     {0, 1, 1, 1, 0}, ' ◻ ◼ ◼ ◼ ◻
        '''     {0, 0, 0, 1, 1}, ' ◻ ◻ ◻ ◼ ◼
        '''     {1, 1, 0, 0, 1}, ' ◼ ◼ ◻ ◻ ◼
        '''     {0, 1, 0, 0, 0}  ' ◻ ◼ ◻ ◻ ◻
        ''' } ' 1/◼ = press once, 
        '''   ' 0/◻ = do not press
        ''' </code>
        ''' </param>
        ''' 
        ''' <returns>
        ''' A formatted <see cref="String"/> describing which cells to press, grouped by row.
        ''' <para></para>
        ''' Includes a total count of all required presses.
        ''' <para></para>
        ''' Example:
        ''' <code>
        ''' ' Input solution board.
        ''' Dim solution5x5 As Byte(,) = {
        '''     {0, 1, 1, 1, 0}, ' ◻ ◼ ◼ ◼ ◻
        '''     {0, 1, 1, 1, 0}, ' ◻ ◼ ◼ ◼ ◻
        '''     {0, 0, 0, 1, 1}, ' ◻ ◻ ◻ ◼ ◼
        '''     {1, 1, 0, 0, 1}, ' ◼ ◼ ◻ ◻ ◼
        '''     {0, 1, 0, 0, 0}  ' ◻ ◼ ◻ ◻ ◻
        ''' } ' 1/◼ = press once, 
        '''   ' 0/◻ = do not press
        '''   
        ''' ' Example output:
        ''' Row 1, Cells: 2, 3, 4
        ''' Row 2, Cells: 2, 3, 4
        ''' Row 3, Cells: 4, 5
        ''' Row 4, Cells: 1, 2, 5
        ''' Row 5, Cell: 2
        ''' 
        ''' Total presses: 12
        ''' </code>
        ''' </returns>
        <DebuggerStepperBoundary>
        Public Shared Function FormatLightsOutSolutionSteps(board As Byte(,)) As String

            Dim rows As Integer = board.GetLength(0)
            Dim cols As Integer = board.GetLength(1)

            Dim sb As New StringBuilder()
            Dim totalPresses As Integer = 0

            For r As Integer = 0 To rows - 1
                Dim pressedCells As New List(Of Integer)

                For c As Integer = 0 To cols - 1
                    If board(r, c) <> 0 Then
                        pressedCells.Add(c + 1)
                        totalPresses += 1
                    End If
                Next

                If pressedCells.Count > 0 Then
                    sb.AppendLine($"Row {r + 1}, Cells: {String.Join(", ", pressedCells)}")
                End If
            Next

            If totalPresses = 0 Then
                sb.AppendLine("No presses needed — all lights are already off.")
            Else
                sb.AppendLine().AppendLine($"Total presses: {totalPresses}")
            End If

            Return sb.ToString()
        End Function

#End Region

    End Class

End Namespace

#End Region

Dim board5x5 As Byte(,) = {
     {1, 1, 0, 1, 1}, ' ◼ ◼ ◻ ◼ ◼
     {1, 1, 0, 0, 0}, ' ◼ ◼ ◻ ◻ ◻
     {1, 0, 0, 1, 1}, ' ◼ ◻ ◻ ◼ ◼
     {0, 1, 1, 0, 0}, ' ◻ ◼ ◼ ◻ ◻
     {0, 0, 1, 0, 1}  ' ◻ ◻ ◼ ◻ ◼
}

Dim solvedBoard As Byte(,) = UtilLightsOut.SolveLightsOutPuzzle(board5x5)

Dim formattedSolution As String = UtilLightsOut.FormatLightsOutBoard(solvedBoard)
formattedSolution &= String.Concat(Enumerable.Repeat(Environment.NewLine, 2)) &
                                   "◼ = Press once" & Environment.NewLine &
                                   "◻ = Do not press"

MessageBox.Show(formattedSolution)

...
Dim solvedBoard As Byte(,) = UtilLightsOut.SolveLightsOutPuzzle(board5x5)
Dim formattedSolution As String = UtilLightsOut.FormatLightsOutSolutionSteps(solvedBoard)

Console.WriteLine(formattedSolution)

C:\Users\***\AppData\Roaming\Mozilla\Firefox\Profiles\***\storage\default\moz-extension+++641400e4-592e-46c4-aad3-d72870ebfeb9^userContextId=4294967295\idb