Quote (Foxic @ Mar 18 2014 04:14pm)
One more problem, the first row and column are always the same. Need them to be random
Edit: A pattern keeps appearing, first row/column are incremental and the diagonal is all the same number, I got this result 10 times in a row. This has to be a completely random variation
You did not state this. You said the entire grid had to be random. So, i chose a random cell and populated it with a random value to initialize the grid. I then solved the grid using this initial value. This generates a random grid. However, it may appear to be the same due to the fact that I am only initializing 1 square out of 81 (9x9). If you were to set n to be 3, the variance would change and you would see the randomness easiar. Would you like me to randomize the entire first row and then solve based on that?
Code
#include <stdio.h>
#include <time.h>
#include <conio.h>
#include <iostream>
bool randomize(int* row, int n)
{
for(int i = 0; i < n; i++) row[i] = i+1;
std::random_shuffle(&row[0],&row[n]);
}
bool unassigned(int** grid, int n, int& r, int& c)
{
for(r = 0; r < n; r++)
for(c = 0; c < n; c++)
if(grid[r][c] == 0)
return true;
return false;
}
bool conflicts(int** grid,int n, int r, int c, int x)
{
for(int i = 0; i < n; i++)
if(grid[r][i] == x || grid[i][c] == x) return true;
return false;
}
bool solve(int** grid, int n)
{
int r, c;
//if there are no unassigned cells then the
//grid has been completely solved
if(!unassigned(grid,n,r,c))
return true;
//otherwise, choose a value for the unassigned cell
for(int i = 1; i <= n; i++)
{
//ensure there are no conflicts with this value
if(!conflicts(grid,n,r,c,i))
{
//assign the value to this cell
grid[r][c] = i;
//attempt to recursively solve every remaining unassigned cell
if(solve(grid,n))
{
//if the board is completely solved we return true
return true;
}
//otherwise this value was not correct. reset and continue
grid[r][c] = 0;
}
}
//we have exhausted all possibilities for this cell and did not
//obtain a solved board, so backtrack and try again
return false;
}
int main()
{
srand (time(NULL));
int n = 9;
int* grid[n];
for(int i = 0; i < n; i++)
{
grid[i] = new int[n];
for(int j = 0; j < n; j++)
grid[i][j] = 0;
}
//randomize a random row to initialize the grid
int r = rand()%n;
randomize(grid[r],n);
//solve the board using backtracking
solve(grid,n);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
printf("%d",grid[i][j]);
printf("\n");
}
scanf("%d");
}
Here, I randomized a random row. I also added line comments to show you what the algorithm does. and to highlight the recursion and the backtracking.
This post was edited by Minkomonster on Mar 18 2014 04:20pm