0

I'm working on my first game with Python and Pygame, and I have to create a binary puzzle.

I'm facing a problem generating a solved grid with these conditions:

  1. Each box should contain either a zero or a one.

  2. More than two equal numbers immediately next to or below each are not allowed.

  3. Each row and each column should contain an equal number of zeros and ones.

  4. Each row is unique and each column is unique. Thus, any row cannot be exactly equal to another row, and any column cannot be exactly equal to another column.

I tried somthing like

parents = []

unique_found = False
while not unique_found:
        candidate_array = np.random.choice([0, 1], size=(CELL,CELL))         
        if not any((candidate_array == x).all() for x in parents): 
          [(i, j) for i, j in enumerate(candidate_array)]
          unique_found = True
         
parents.append(candidate_array)

It's generating a random grid of one and zeros:

[[0 0 0 1 0 1]
 [1 0 0 1 1 1]
 [0 0 0 0 1 0]
 [1 0 0 0 1 0]
 [0 1 1 1 1 1]
 [0 1 1 0 1 1]]

but I don't know how to add the conditions I want to make this grid less random.

ggorlen
  • 44,755
  • 7
  • 76
  • 106
leo
  • 35
  • 6

2 Answers2

0

For a direct solution, there's basically no way to get around coding up those constraints. Once you do code them up, try backtracking: try putting a 0 in the first cell and check the constraints. If the constraints are satisfied, recursively step to the next cell and try a 0 there.

If a constraint is ever breached and you've tried all of the possible values on a square, one of the assumptions somewhere along the way must have been invalid, so undo the most recent 0 or 1 placed, pop the call stack and backtrack to the previous index to try the next possible value. This backtracking might unwind all of the moves, but eventually it'll hone in on a solution if a board is solvable. It's brute force with the optimization that it stops exploring impossible positions.

This is basically the same as the most straightforward way of solving Sudoku, but with different constraints and different values per square (much fewer, but more squares). The only difference between generating a solved board from scratch as you're doing and solving one with a few pre-filled values is that you skip the squares with pre-filled values. It's a trivial difference. Check out this gif which illustrates the backtracking algorithm working.

Looking into Sudoku solving can offer deeper ideas for domain-specific improvements you could apply to this puzzle to gain a speed increase, once you have a basic backtracking approach working. Even without any domain-specific knowledge, the backtracking approach can be multithreaded/multiprocessed for a speed increase, with each worker starting from a specific configuration of the first few top-level values for the first squares at the the root of the search.

By the way, following this method is deterministic on an empty board, so you'll get the same filled board every time. You could randomize the choices along the way, or even the order of visiting squares, if you want a non-deterministic result.

You can improve the backtracking approach by permuting a pre-filled grid that satisfies constraint 3 (equal numbers of 0s and 1s per row/column), but it's still basically backtracking (the granularity of a stack frame changes -- now it's a possible configuration of a row rather than a cell), and is purely an optimization, so I'd start with the cell-by-cell approach.

That said, I'd avoid blindly generating and testing random configurations. It's not much easier to code than backtracking, because you still need to code up and check all of the constraints, and a non-systematic approach would likely take much longer to find a solution than a systematic one.

If you're open to using external tools, you can add the constraints to an off-the-shelf constraint solver like PuLP or Z3 and it'll spit the answer out.

ggorlen
  • 44,755
  • 7
  • 76
  • 106
0

You could create initial solution like the one below which only satisfies condition 1 and 3.

[1 ,1, 1, 0, 0 ,0]
[1 ,1, 1, 0, 0 ,0]
[1 ,1, 1, 0, 0 ,0]
[0 ,0, 0, 1, 1 ,1] 
[0 ,0, 0, 1, 1 ,1]
[0 ,0, 0, 1, 1 ,1]

And then swap rows and columns randomly. As those wouldn't break the third condition.

The idea would then be to swap rows or columns until you hit a valid solution.

Albin Paul
  • 3,330
  • 2
  • 14
  • 30
  • @ggorlen The initial solution will break the 4rd condition and 2 condition will be satisfied. But after some random swaps. The 4rd condition will also be satisfied. – Albin Paul Aug 19 '21 at 19:07
  • @ggorlen I didnt notice that, there was only 3 condition before. But the idea remains the same. swap until it hits a valid solution. – Albin Paul Aug 19 '21 at 19:09
  • After the update, looks OK in terms of description and correctness and I like the idea of simplifying the search space to automatically ensure all configurations handle constraint 3, although randomization seems like it'd be much less optimal than a systematic backtracking approach that tries every unique permutation methodically. – ggorlen Aug 19 '21 at 20:50