Question 169619 in Javascript Question posted in
A very good W3school tutorial can be found here.

What data structure & algorithm should be used to efficiently generate solvable puzzles for a Double-Choco puzzle game?

I’m working on implementing a puzzle board game called Double-Choco published by Nikoli magazine

Where the board is a 2-dimensional matrix with cells that are either white or gray. The goal is to divide the grid into blocks by drawing solid lines over the dotted lines. Each block must contain a pair of areas of white cells and gray cells having the same form (size and shape), one area can be rotated or mirror of the opposite area, an area could have a number indicates the number of cells of that color in the block.

I’m looking for help in choosing a data structure and forming an algorithm to automatically generate solvable puzzles for this game.

I am implementing using JavaScript and Here’s the approach I’m currently considering:

  • Start with a blank 2-dimensional matrix with the desired size.
  • Choose a random area size for the white area, between 2 and half of the board size (rounded down to the nearest even number), where cells that form the area is available and not taken
  • Check if a matched opposite area can be acquired on the board with the same shape & size.
  • If not: check if there is a space for a rotated or mirrored area.
  • If not: return to step 2
  • If yes: recheck the whole board for violations (mainly if there is a surrounded odd-size block left
  • If there is a violation: go back to step 2
  • mark the cells of the block (of 2 areas) as taken
  • go to step 2 till board is filled

As for the data-structure I thought of using graph but I couldn’t wrap it around my head. maybe deal with areas as it is as 2-dim matrix?

I’m not sure if this approach is optimal or if there are better data structures and algorithms to use. What data structure and algorithm would you recommend for generating solvable puzzles for this board game? Any help or suggestions would be greatly appreciated.

Tags:

2

Answers


  1. 0

    I would go like:

    • 2 d XxY array of cells: 
          let cell = {
        x: Number, // just for passing them down easier, I assign coords too
        y: Number,
        color: "white" | "black",
        number: null | Number,
        top: true | false,
        bottom: true | false,
        left: true | false,
        right: true | false,
        taken: false, // | true
        block: []
    }
    • run and extract every block (its coordinates in array) 
      function take(cell, cellFor) {
    cell.taken = true
    if (!cell.top)    take(cells[cell.y-1][cell.x], cellFor)
    if (!cell.bottom) take(cells[cell.y+1][cell.x], cellFor)
    if (!cell.left)   take(cells[cell.y][cell.x - 1], cellFor)
    if (!cell.right)  take(cells[cell.y][cell.x + 1], cellFor)
}

for (let row of cells)
    for (let cell of row)
        if (!cell.taken) take(cell, cell)

    the shortest code I could think of.
    let say you have 2×2 and [(0,0),(1,0)] as block.

    • take(cell[0][0]):
      • take (1,0) to (0,0)‘s block because its .right is false
      • don’t add (1,0) because its .bottom is true
    • don’t take(cell[0][1]) because when (0,0) was running, it took (0,1) for its block
    • take(cell[0][1]) …

    I think you see the pattern. To be honest there can be bugs, I haven’t tried. its just a concept. also needs to be fine tuned for array length checks and other boring stuff.
    cellFor argument is used for having a reference to the cell who have started the take sequence.

    You have to "parse" it as cells.flat().filter(bock=>block.length).

    notice I didn’t use the .number and .color. Once you have the blocks, you can check it with the cells in your block.
    this take style is for creating blocks. I basically give a minimalist way to extract blocks.
    Took some time but if my algo has a flaw, I apologize.

    Login or Signup to reply.
  2. 0

    I would tackle this the other way around.

    • Generate a collection of blocks with different numbers, shapes and sizes.

    • Select at random a small set of blocks from the collection

    • Arrange the selected blocks at random, but avoiding overlap, in a board.

    • Fill in the unused parts of the board with random white and grey squares.

    Note that the last step may produce a puzzle that has more than one correct answer. If you do not want that, you will have replace the last step with a more careful filling in of unused parts.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search