Help with this game!

[alex067]

Hey everyone. I am re-writing the Oh n0 game, developed by Martin Kool in C++. If you are unfamiliar with how the game works, check it out: http://0hn0.com/

Basically, the game revolves around a matrix, where the value in the cell represents the cells visibility, going up, down, left and right, but not diagonal.

IE:
1 | 1 | 0
0 | 2 | 2
0 | 1 | 2

Is a valid board because each cell can see each other, however this is not valid:
1 | 1 | 0
0 | 2 | 1
0 | 1 | 2

because the "1" on [1][2] has a visibility of 1 but it can see 2 cells (cells that are > 0).

I am stuck on how to find an efficient way to randomly generate a board. I have the validation function made and it works, but I am stumped on how to generate a board so the player can play.

I initially tried a nested for loop and generate a random number on each cell, however you can clearly see how this is not effective. Actually, I let my computer run for 30 minutes and it just kept generating random boards that were not even close to being a valid board.

Can anyone give me any ideas?

I tried breaking it down, like generate a random number on a random cell rather than in an sequential order, however this did not work.

[lastchance]

Back-tracking?

[alex067]

What do you mean?

[lastchance]

https://en.m.wikipedia.org/wiki/Backtracking

[alex067]

Thank you for this, I will do more research!

[lastchance]

Hi @alex067, I have to warn you that the suggestion came from a feeling that it might work rather than actually having tried it! I wrote a Sudoku solver which worked quite well with backtracking, and yours seems a vaguely similar sort of problem.

You already have a board-validator, so I guess it would come down to what is the "next" trial each time.

If you get one valid board then you automatically get a whole lot more from the various symmetries.


BTW. I've just had a look at the web link for your game. Can you explain why you think

1 | 1 | 0
0 | 2 | 2
0 | 1 | 2

is a valid board? It doesn't meet the criteria of your game (assuming that the 0 represents a "blocking" red dot).

[lastchance]

OK, try this for generating some valid boards. There appear to be 250 of them if the grid size is NxN with N=3.

I didn't use backtracking here, just considered successive possible boards. You can increase N, but I don't know how long it will take to consider all valid boards.

#include <iostream>
#include <vector>
using namespace std;

using BOARD = vector< vector<int> >;

const int N = 3;


//======================================================================


void output( ostream& strm, const BOARD &board )
{
   for ( int i = 0; i < N; i++ )
   {
      for ( int j = 0; j < N; j++ ) strm << board[i][j] << " ";
      strm << '\n';
   }
   strm << '\n';
}


//======================================================================


bool isValid( const BOARD &board )
{
   for ( int i = 0; i < N; i++ )
   {
      for ( int j = 0; j < N; j++ )
      {
         if ( !board[i][j] ) continue;
         int visible = 0;
         // Count visible up to a blocking position in each cardinal direction
         for ( int k = j - 1; k >= 0; k-- ) 
         {
            if ( board[i][k] ) visible++;
            else               break;
         }
         if ( visible > board[i][j] ) return false;
         for ( int k = j + 1; k < N; k++ )
         {
            if ( board[i][k] ) visible++;
            else               break;
         }
         if ( visible > board[i][j] ) return false;
         for ( int k = i - 1; k >= 0; k-- )
         {
            if ( board[k][j] ) visible++;
            else               break;
         }
         if ( visible > board[i][j] ) return false;
         for ( int k = i + 1; k < N; k++ )
         {
            if ( board[k][j] ) visible++;
            else               break;
         }
         if ( visible != board[i][j] ) return false;
      }
   }
   return true;
}


//======================================================================


bool nextBoard( BOARD &board )
{
   int MAX = 2 * ( N - 1 );
   int i = 0;
   while ( i < N )
   {
      int j = 0;
      while ( j < N )
      {
         board[i][j]++;
         if ( board[i][j] <= MAX ) return true;
         board[i][j] = 0;
         j++;
      }
      i++;
   }
   return false;
}


//======================================================================


int main()
{
   cout << "Valid boards:\n";

   BOARD board( N, vector<int>( N, 0 ) );
   unsigned long long numBoard = 1, numValid = 1;
   output( cout, board );              // All zeroes is actually valid

   while ( nextBoard( board ) )
   {
      numBoard++;
      if ( isValid( board ) )
      {
         numValid++;
         output( cout, board );
      }
   }

   cout << "Number of boards: " << numBoard << '\n';
   cout << "Number of valid: " << numValid << '\n';
}

Valid boards:
0 0 0 
0 0 0 
0 0 0 

1 1 0 
0 0 0 
0 0 0 

0 1 1 
0 0 0 
0 0 0 

2 2 2 
0 0 0 
0 0 0 

1 0 0 
1 0 0 
0 0 0 

2 1 0 
1 0 0 
0 0 0 

3 2 2 
1 0 0 
0 0 0 

0 1 0 
0 1 0 
0 0 0 

1 2 0 
0 1 0 
0 0 0 

0 2 1 
0 1 0 
0 0 0 


............ LOTS OF LINES OMITTED ..............


4 2 4 
2 0 2 
4 2 4 

0 0 2 
0 2 3 
2 3 4 

0 0 2 
3 3 4 
3 3 4 

2 0 2 
4 3 4 
4 3 4 

0 3 3 
0 3 3 
2 4 4 

2 4 4 
0 3 3 
2 4 4 

0 3 3 
3 4 4 
3 4 4 

4 4 4 
4 4 4 
4 4 4 

Number of boards: 1953125
Number of valid: 250

[lastchance]

Oh dear! I rather over-complicated that.

Try this code for generating a solution board.

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;

using BOARD = vector< vector<int> >;

const int N = 5;


//======================================================================


void output( ostream& strm, const BOARD &board )
{
   for ( int i = 0; i < N; i++ )
   {
      for ( int j = 0; j < N; j++ ) strm << board[i][j] << " ";
      strm << '\n';
   }
   strm << '\n';
}


//======================================================================


BOARD generateBoard( int nblue )
{
   // Start with all zeroes
   BOARD board( N, vector<int>( N, 0 ) );

   // Place initial blue spot
   int i = rand() % N;
   int j = rand() % N;
   board[i][j] = 1;

   // Add the remaining blue spots; must connect
   for ( int n = 2; n <= nblue; n++ )
   {
      while ( true )                                       // Keep trying to find a new adjacent slot
      {
         i = rand() % N;
         j = rand() % N;
         int connected = ( i > 0 && board[i-1][j] ) + ( i < N - 1 && board[i+1][j] ) +
                         ( j > 0 && board[i][j-1] ) + ( j < N - 1 && board[i][j+1] );

         if ( connected && !board[i][j] )
         {
            board[i][j] = 1;
            break;
         }
      }
   }

   // Update with total visibility
   for ( int i = 0; i < N; i++ )
   {
      for ( int j = 0; j < N; j++ )
      {
         if ( !board[i][j] ) continue;
         int visible = 0;
         for ( int k = j - 1; k >= 0 && board[i][k]; k-- ) visible++;
         for ( int k = j + 1; k <  N && board[i][k]; k++ ) visible++;
         for ( int k = i - 1; k >= 0 && board[k][j]; k-- ) visible++;
         for ( int k = i + 1; k <  N && board[k][j]; k++ ) visible++;
         board[i][j] = visible;
      }
   }

   return board;
}


//======================================================================


int main()
{
   srand( time( 0 ) );
   int nblue;

   cout << "Grid size: " << N << " x " << N << '\n';
   cout << "How many blue dots do you want? ( 2 <= B <= " << N * N << " ): ";
   cin >> nblue;

   BOARD B = generateBoard( nblue );
   output( cout, B );
}


//====================================================================== 

Grid size: 5 x 5
How many blue dots do you want? ( 2 <= B <= 25 ): 20
8 8 6 6 4 
7 7 5 5 0 
7 7 5 5 0 
5 5 0 0 0 
8 8 4 4 4 

[dhayden]

Alex067, your first board does appear to be valid according to the rules in the website
[ edit: that should be "does not appear..."]:

      A   B   C
1:   1 | 1 | 0
2:   0 | 2 | 2
3:   0 | 1 | 2

B1 should be 3 because it sees B1, B2 and B3.
B2 should be 3 because it sees B1 C2 and B3
B3 should be 3 because it sees B1 B2 and C3

Following the rules in the website, generating a board is trivial:
1. Fill the board with blue and red squares at random.
2. For each red square, count the number that is has visible.

[lastchance]

Generating a solution board is, indeed, straightforward.

Generating a starting point for a game, with blanks in (like Sudoku) and proving it has a unique solution afterwards is not so trivial.

[alex067]

You are right the example I gave was incorrect.

However generating the random board is not so straight forward.

Your solution asks for a user input of how many blues. The game does not allow for that, and must generate the board with no user input.

Backtracking does not work as the cell visibility requires the full board to be made first. IE if [0][1] has a value of 2, that would require at least the second row to be created as well and validated, which wuold require the third row to be generated and validatd, etc.

Cheers for your input, Im gonna review it and see how it works! thanks

[dhayden]

lastchance, thanks for catching my error. I'll edit my post.

[lastchance]

alex067 wrote:

Your solution asks for a user input of how many blues. The game does not allow for that, and must generate the board with no user input.

That's fine - it was only an example. You can choose as many blue and red spots as necessary: a random number if you want (although I found the grids a bit more interesting if you have a large majority of blue). Actually, the web link seemed to want the user to choose the size of the grid.

My grid is random:

   int i = rand() % N;
   int j = rand() % N;
   board[i][j] = 1;

   // Add the remaining blue spots; must connect
   for ( int n = 2; n <= nblue; n++ )
   {
      while ( true )
      {
         i = rand() % N;
         j = rand() % N;

It wasn't clear what to do about "zero-visibility" blue spots (those surrounded entirely with reds). As you appeared to be using 0 for a blocking red spot I made sure that the blue spots were connected, or there would be no way of distinguishing between a red spot and a zero-visibility blue spot.

No, back-tracking isn't much use for designing a final valid solution, I admit, although it's a reasonable solution method for the actual game with spaces and "starters" in, as in the example given in the web link. It's also unclear whether they wanted the solution to be unique, or whether any valid solution given the starting conditions would do.

[alex067]

Hm the output of your solution that you posted doesn't generate a valid board

I forgot to mention, that the cell visiblity expands across the whole row, not until the cells value.

8 8 6 6 4
7 7 5 5 0
7 7 5 5 0
5 5 0 0 0
8 8 4 4 4

So for example, cell [4][4] has a value of 4, so there is 4 cells on its left, however there is another cell on top on [0][4] which makes it a total visibility of 5 cells, not 4.

[lastchance]

alex067 wrote:

I forgot to mention, that the cell visiblity expands across the whole row, not until the cells value.

Well, according to the rules on their website, it says "red cells block the view", so that's what I worked to. On that basis I'm quite happy with cell [4][4] having a total visibility of 4.

Their "how-to-play" example also looks like
2 5 2 0
0 3 0 1
0 5 2 3
1 4 0 0
So how would you arrive at the visibility of the [0][0] cell being 2 unless the zero below it was blocking the view of the bottom-left corner?


Thanks for the brilliant topic BTW! Simple rules, but some (rather too) addictive coding challenges.

[alex067]

Ah i am just confusing myself in this game haha!!

yes you are right, the 0 does block the visiblity of the cell so the range does not expand the whole row and column

[alex067]

int connected = ( i > 0 && board[i-1][j] ) + ( i < N - 1 && board[i+1][j] ) +
( j > 0 && board[i][j-1] ) + ( j < N - 1 && board[i][j+1] );

I have never seen this syntax before, can you explain this to me?

[lastchance]

Hello, @alex067.

The line counts the number of adjacent cells (e.g. [i-1][j]) that are already occupied by blue spots. A non-zero value of board[i-1][j] translates to boolean true when used in a boolean AND (&&) operation. Conversely, boolean true and false map to 1 and 0 respectively when used in an addition expression (+). The pre-emptive checks (i > 0 etc.) just make sure that I don't go out of array bounds when I get to edges.

With the glorious benefit of hindsight I could simply have made connected a bool, as it was sufficient to note whether ANY adjacent cell was occupied: I didn't actually need to count them. Then I could have used boolean OR (||) rather than adding.

The whole purpose was to ensure that I didn't end up with any isolated, and hence zero-visibility, blue dots, as I was using 0 to signify a red dot. I could, I suppose, have used a -1 to indicate red; however, the game examples didn't seem to use any zero-visibility blue dots, so I excluded them by maintaining connectedness.