Generate Solved Double Chocolate Puzzles: A Guide to Data Structures and Algorithms

This article explores in-depth how to automatically generate solveable puzzles for the Double-Choco puzzle game. We will introduce an efficient data structure - a cell object based on a 2D grid that contains boundary information, color, and state. On this basis, we will elaborate on a recursive block recognition algorithm (similar to depth-first search) and how to integrate it into the iterative puzzle generation process to ensure that the generated puzzles meet the rules of the game and are solveable. The article will provide sample code and discuss key considerations and optimization strategies in the generation process.

Overview of Double Chocolate Puzzle

"Double-Choco" is a unique logic puzzle launched by Nikoli magazine. The game plays on a 2D grid of white and gray cells. The player's goal is to divide the grid into several "blocks" by drawing lines. Each block must contain a pair of white and gray areas of exactly the same shape and size. These two areas can be rotated or mirrored to each other. Some areas may have numbers indicating the number of cells that the color is in the block.

The key challenge in automatically generating such puzzles is not only creating blocks that meet the basic rules, but also ensuring that the entire puzzle is solveable and there are no isolated areas left behind that cannot form legal blocks.

Core data structure design

To efficiently represent puzzle boards and support generation algorithms, we recommend using a two-dimensional array to store custom "cell" objects. Each Cell object should contain the following properties to fully describe its state and boundary information:

 let Cell = {
    x: Number, // X coordinate y: Number, // Y coordinate color: "white" | "gray", // The color of the cell can be empty or undefined during initialization: null | Number, // If there is a numeric prompt, it is a number, otherwise it is null

    // Boundary flag: true means there is a boundary line (wall) in this direction, false means that it is connected to adjacent cells top: Boolean, // Is there a boundary above bottom: Boolean, // Is there a boundary below left: Boolean, // Is there a boundary on the left right: Boolean, // Is there a boundary on the right blockId: null, // Used to mark the block ID to which the cell belongs, null means that is not allocated isOccupied: Boolean // During the generation process, mark the cell has been occupied by a block};

Data structure explanation:

• x, y: Coordinate information is easy to reference and debug.
• color: Stores the color of the cell, which will be assigned during the generation stage.
• number: used to store puzzle prompt numbers.
• top, bottom, left, right: These boolean values are the key to defining the shape of the block. true means there is a solid line in that direction, separating the current cell from the adjacent cells. false means they are connected and belong to the same block. In the initial state, all of this can be set to false, indicating a completely open grid.
• blockId: used in block recognition algorithm to ensure that each cell belongs to only one block and can quickly query the block to which it belongs.
• isOccupied: During the generation process, mark whether the cell has been assigned to a final puzzle block, avoiding repeated processing.

The puzzle board itself can be represented as a two-dimensional array of Cell objects: let board = Array(rows).fill(0).map(() => Array(cols).fill(0).map(() => ({...Cell})));

Block recognition algorithm: Extract blocks from grid

The core of generating puzzles is to be able to accurately identify the "blocks" formed in the current grid state. This can be achieved by a traversal algorithm similar to depth-first search (DFS) or breadth-first search (BFS). The algorithm starts with an unvisible cell, along a path without boundaries, collects all connected cells to form a complete block.

 /**
 * Recursive function: Starting from the specified cell, searching for and collecting all connected cells to form a block.
 * @param {Array<array>>} grid - puzzle grid* @param {number} x - X coordinates of the current cell* @param {number} y - Y coordinates of the current cell* @param {number} currentBlockId - unique ID of the current block
 * @param {Array<object>} blockCellsList - Used to collect lists of all cells in the current block*/
function findBlockCells(grid, x, y, currentBlockId, blockCellsList) {
    // Boundary check: Make sure the coordinates are within the grid range if (x = grid[0].length || y = grid.length) {
        return;
    }
    const cell = grid[y][x];
    // Check: If the cell has been assigned to a block, or has been accessed in the current traversal, stop if (cell.blockId !== null) {
        return;
    }

    cell.blockId = currentBlockId; // Assign the current cell to the current block blockCellsList.push(cell); // Add the cell to the list of the current block// Recursively explore adjacent cells, provided that there is no boundary line between them if (!cell.top) findBlockCells(grid, x, y - 1, currentBlockId, blockCellsList);
    if (!cell.bottom) findBlockCells(grid, x, y 1, currentBlockId, blockCellsList);
    if (!cell.left) findBlockCells(grid, x - 1, y, currentBlockId, blockCellsList);
    if (!cell.right) findBlockCells(grid, x 1, y, currentBlockId, blockCellsList);
}

/**
 * Extract all independent blocks from the entire grid.
 * @param {Array<array>>} grid - Puzzle grid* @returns {Array<array>>} A list of all identified blocks, each block is a list of cells*/
function extractAllBlocks(grid) {
    let allBlocks = [];
    let blockCounter = 0;

    // Before each extraction, reset the blockId of all cells and make sure to re-identify grid.forEach(row => row.forEach(cell => cell.blockId = null));

    for (let y = 0; y  0) {
                    allBlocks.push(currentBlockCells);
                }
            }
        }
    }
    return allBlocks;
}</array></array></object></array>

Notes:

• The findBlockCells function is recursive and is used to explore a single connected component.
• The extractAllBlocks function traverses the entire grid, ensuring that all unallocated cells are used as the starting point for the new block, thus finding all independent blocks.
• Resetting the blockId is crucial before each call to extractAllBlocks to ensure that each analysis is a completely new identification based on the current boundary state.

Puzzle generation algorithm process

Puzzle generation is a process of iterative and backtracking, with the core idea of gradually filling the grid, placing a pair of white and gray areas that conform to the rules at a time, and defining their boundaries at the same time.

1. Initialize the grid:

   • Create a two-dimensional array of MxN Cell objects. The isOccupied of all cells is set to false, the color is not defined, and the top/bottom/left/right boundaries are all set to false (indicates that there is no boundary at the beginning).

The above is the detailed content of Generate Solved Double Chocolate Puzzles: A Guide to Data Structures and Algorithms. For more information, please follow other related articles on the PHP Chinese website!