How to resolve the algorithm Solve a Numbrix puzzle step by step in the C# programming language

Published on 12 May 2024 09:40 PM
#C_Sharp

How to resolve the algorithm Solve a Numbrix puzzle step by step in the C# programming language

Table of Contents

Problem Statement

Numbrix puzzles are similar to Hidato. The most important difference is that it is only possible to move 1 node left, right, up, or down (sometimes referred to as the Von Neumann neighborhood). Published puzzles also tend not to have holes in the grid and may not always indicate the end node. Two examples follow: Problem. Solution. Problem. Solution. Write a program to solve puzzles of this ilk, demonstrating your program by solving the above examples. Extra credit for other interesting examples.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Solve a Numbrix puzzle step by step in the C# programming language

This C# code provides a solver for Numbrix puzzles, a type of logic puzzle that involves placing numbers in a grid such that they form a continuous path while adhering to specific rules. Let's break down the code step by step:

  1. Namespace and Using Statements:

    • The code is in the System namespace.
    • It uses using statements to incorporate functionality from various system libraries, including collections, console I/O, math functions, and LINQ.

  2. Solver Class:

    • The Solver class defines the logic for solving Numbrix puzzles.
    • It has several member variables and methods:
      • numbrixMoves is a static array of tuples representing the possible moves (up, right, down, left) for Numbrix puzzles.
      • moves is an instance array of tuples representing the moves for the specific puzzle being solved.
      • Main method:
        • The Main method serves as the program's entry point.
        • It creates instances of the Solver class with appropriate move sets.
        • It solves two predefined Numbrix puzzles and prints the solutions.

  3. Initialization of the Solver:

    • In the constructor, the Solver class can be initialized with different move sets.

  4. Solve Method:

    • The Solve method is overloaded to take various input parameters:
      • bool circular: Indicates whether the puzzle wraps around from the last number to the first.
      • params string[] puzzle: Takes a string array representing the puzzle.
      • bool circular, int[,] puzzle: Takes a 2D array representing the puzzle.
    • The method parses the input puzzle, applies the given numbers, and attempts to solve it recursively.

  5. Solve Recursive Function:

    • This is a recursive function that explores the puzzle grid, filling in numbers while adhering to the puzzle rules.
    • It takes several parameters, including the puzzle board, given numbers, current position, etc.
    • It checks for boundary conditions, given numbers, and explores possible moves to find a valid solution.

  6. AreNeighbors Method:

    • This helper method checks if two positions in the grid are horizontally or vertically adjacent.

  7. Parse Method:

    • This method parses both string and 2D array input puzzles.
    • It initializes the puzzle board, identifies given numbers, and counts the number of numbers to be placed.

  8. Scan Method:

    • This method creates a BitArray to track which numbers have been placed in the puzzle.

  9. Print Method:

    • This method prints the solved puzzle board or an error message if no solution is found.

Overall, this code provides a comprehensive implementation of a Numbrix puzzle solver. It allows users to specify different types of puzzles and handles the recursive exploration, validation, and printing of solutions.

Source code in the csharp programming language

using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;
using static System.Linq.Enumerable;

public class Solver
{
    private static readonly (int dx, int dy)[]
        //other puzzle types elided
        numbrixMoves = {(1,0),(0,1),(-1,0),(0,-1)};

    private (int dx, int dy)[] moves;
        
    public static void Main()
    {
        var numbrixSolver = new Solver(numbrixMoves);
        Print(numbrixSolver.Solve(false, new [,] {
            {  0,  0,  0,  0,  0,  0,  0,  0,  0 },
            {  0,  0, 46, 45,  0, 55, 74,  0,  0 },
            {  0, 38,  0,  0, 43,  0,  0, 78,  0 },
            {  0, 35,  0,  0,  0,  0,  0, 71,  0 },
            {  0,  0, 33,  0,  0,  0, 59,  0,  0 },
            {  0, 17,  0,  0,  0,  0,  0, 67,  0 },
            {  0, 18,  0,  0, 11,  0,  0, 64,  0 },
            {  0,  0, 24, 21,  0,  1,  2,  0,  0 },
            {  0,  0,  0,  0,  0,  0,  0,  0,  0 },
        }));

        Print(numbrixSolver.Solve(false, new [,] {
            {  0,  0,  0,  0,  0,  0,  0,  0,  0 },
            {  0, 11, 12, 15, 18, 21, 62, 61,  0 },
            {  0,  6,  0,  0,  0,  0,  0, 60,  0 },
            {  0, 33,  0,  0,  0,  0,  0, 57,  0 },
            {  0, 32,  0,  0,  0,  0,  0, 56,  0 },
            {  0, 37,  0,  1,  0,  0,  0, 73,  0 },
            {  0, 38,  0,  0,  0,  0,  0, 72,  0 },
            {  0, 43, 44, 47, 48, 51, 76, 77,  0 },
            {  0,  0,  0,  0,  0,  0,  0,  0,  0 },
        }));
    }

    public Solver(params (int dx, int dy)[] moves) => this.moves = moves;

    public int[,] Solve(bool circular, params string[] puzzle)
    {
        var (board, given, count) = Parse(puzzle);
        return Solve(board, given, count, circular);
    }

    public int[,] Solve(bool circular, int[,] puzzle)
    {
        var (board, given, count) = Parse(puzzle);
        return Solve(board, given, count, circular);
    }

    private int[,] Solve(int[,] board, BitArray given, int count, bool circular)
    {
        var (height, width) = (board.GetLength(0), board.GetLength(1));
        bool solved = false;
        for (int x = 0; x < height && !solved; x++) {
            solved = Range(0, width).Any(y => Solve(board, given, circular, (height, width), (x, y), count, (x, y), 1));
            if (solved) return board;
        }
        return null;
    }

    private bool Solve(int[,] board, BitArray given, bool circular,
        (int h, int w) size, (int x, int y) start, int last, (int x, int y) current, int n)
    {
        var (x, y) = current;
        if (x < 0 || x >= size.h || y < 0 || y >= size.w) return false;
        if (board[x, y] < 0) return false;
        if (given[n - 1]) {
            if (board[x, y] != n) return false;
        } else if (board[x, y] > 0) return false;
        board[x, y] = n;
        if (n == last) {
            if (!circular || AreNeighbors(start, current)) return true;
        }
        for (int i = 0; i < moves.Length; i++) {
            var move = moves[i];
            if (Solve(board, given, circular, size, start, last, (x + move.dx, y + move.dy), n + 1)) return true;
        }
        if (!given[n - 1]) board[x, y] = 0;
        return false;

        bool AreNeighbors((int x, int y) p1, (int x, int y) p2) => moves.Any(m => (p2.x + m.dx, p2.y + m.dy).Equals(p1));
    }

    private static (int[,] board, BitArray given, int count) Parse(string[] input)
    {
        (int height, int width) = (input.Length, input[0].Length);
        int[,] board = new int[height, width];
        int count = 0;
        for (int x = 0; x < height; x++) {
            string line = input[x];
            for (int y = 0; y < width; y++) {
                board[x, y] = y < line.Length && char.IsDigit(line[y]) ? line[y] - '0' : -1;
                if (board[x, y] >= 0) count++;
            }
        }
        BitArray given = Scan(board, count, height, width);
        return (board, given, count);
    }

    private static (int[,] board, BitArray given, int count) Parse(int[,] input)
    {
        (int height, int width) = (input.GetLength(0), input.GetLength(1));
        int[,] board = new int[height, width];
        int count = 0;
        for (int x = 0; x < height; x++)
            for (int y = 0; y < width; y++)
                if ((board[x, y] = input[x, y]) >= 0) count++;
        BitArray given = Scan(board, count, height, width);
        return (board, given, count);
    }

    private static BitArray Scan(int[,] board, int count, int height, int width)
    {
        var given = new BitArray(count + 1);
        for (int x = 0; x < height; x++)
            for (int y = 0; y < width; y++)
                if (board[x, y] > 0) given[board[x, y] - 1] = true;
        return given;
    }

    private static void Print(int[,] board)
    {
        if (board == null) {
            WriteLine("No solution");
        } else {
            int w = board.Cast<int>().Where(i => i > 0).Max(i => (int?)Ceiling(Log10(i+1))) ?? 1;
            string e = new string('-', w);
            foreach (int x in Range(0, board.GetLength(0)))
                WriteLine(string.Join(" ", Range(0, board.GetLength(1))
                    .Select(y => board[x, y] < 0 ? e : board[x, y].ToString().PadLeft(w, ' '))));
        }
        WriteLine();
    }

}

You may also check:How to resolve the algorithm CSV data manipulation step by step in the Euphoria programming language
You may also check:How to resolve the algorithm Distributed programming step by step in the UnixPipes programming language
You may also check:How to resolve the algorithm Rot-13 step by step in the Visual Basic programming language
You may also check:How to resolve the algorithm Mutual recursion step by step in the PL/I programming language
You may also check:How to resolve the algorithm Long primes step by step in the Scala programming language