Hi, I'm on Christmas Break and am bored out of my mind so i decided that i wanted to write a program that generates a SOLVED Sudoku board, i.e., it has all the numbers filled in. I'm going to write a program later to turn it into an unsolved puzzle. But, I can't think of any way to generate the 9 numbers once in each row and each column. I can get all of them in all of the rows, but not all of the columns , and vise versa.
any help would be greatly appreciated.
I had an idea once of how to do this but I didn't like it very much.
Here is what I have thought:
Each cell (81 cells) will be represented by a Vector (perhaps an array [9][9] of Vectors). Each Vector will have numbers from 1 to 9.
Suppose you want to decide what number to put at cell (i,j). You will take the values of that Vector and randomly pick one of those numbers. Once you have selected the number, You will remove that number from ALL the Vectors that are at the same row, column and square.
So when you want to decide what to put at cell (i,j+1), the Vector will have 1 less number since you removed from it the value you placed at (i,j), so again you will randomly choose a number from the existing values and you will remove that from the rest of Vectors.
In the end all the values will be removed except from one, the chosen one.
Like I said, as an initial thought it's not very smart (an array with 81 Vectors isn't very efficient).
Another thought is having a Vector with the available numbers for each row, column and square (27 Vectors) and whenever you place a number at the cell (i,j) you will remove that number from the available numbers of the specific row,column and square. Of course when you select a number for (i,j) you will need to check if it is among the Vectors that hold the available numbers for the specific row, column and square. Meaning that you will be doing some sort of logical Join with these 3 Vectors
>.< I just remembered that each 3x3 square could hold only 1-9 once too >.< (I've gotten 4 and 1/2 hours of sleep the last 2 nights.)
that second idea sounds a bit easier maybe hmm.....
what would you think of a [9][9][9] array? each row and column would have an array, and so would each cell. After a number is used, you could remove it from the rows and columns, then remove it from the positions within the 3x3 square... I don't know, it helps me to ramble out loud or in text, so that's why it sounds like i'm talking to myself >.<
i think it's a bit of a combination of your 2 ideas, javaAddict....
what would you think of a [9][9][9] array? each row and column would have an array, and so would each cell. After a number is used, you could remove it from the rows and columns, then remove it from the positions within the 3x3 square...
This is the same solution as my first.
Instead of an [9][9][9] array which would mean as you said an array [9][9] with each cell having an array with numbers and after a number is used remove it,
you could have an array [9][9] with a Vector in each cell. I thought it would be better because how do you intend to remove a number from an array?
If you had a Vector you could use the remove() method which removes the element and reduces the size of the Vector.
oooohhh, ok, i've never messed with vectors, i just glanced at them on the api a couple of months ago. now i get what you're saying. i think before i do anything else, i need some sleep. 4.5 hrs of sleep a night for 2 nights isn't the best idea.... thanks for the idea, i'l see what i can do with it
i think before i do anything else, i need some sleep. 4.5 hrs of sleep a night for 2 nights isn't the best idea....
If you're sleeping polyphasically that could be to much sleep :)
hahaha, i could use the extra hours, too bad i don't have time to sleep during school :(
Ok, I've been looking over my code, seeing if i can get it done with having to mess with vectors, and it fills the puzzle fine, but they aren't legitimate answers, my code seems sound (note that it doesn't check the 3x3 squares yet, that comes after i fix this). here it is
public class SudokuRunner extends Sudoku
{
public static void main(String[] args)
{
Sudoku game = new Sudoku();
game.emptyBoard();
game.fillBoard();
System.out.println(game.toString());
}
}import java.util.Random;
import java.lang.String;
public class Sudoku
{
// number of rows/columns in a Sudoku puzzle
final int ROWS = 9;
final int COLUMNS = 9;
// indecates the current row/column that is being edited
int currentRow, currentColumn;
// the int and string values of the number being placed
String number;
int num;
// 2D String that represents the board
public String[][] theBoard = new String[ROWS][COLUMNS];
Random randy = new Random();
// assign each spot on the board with a space (to counter nullPointerException)
public void emptyBoard()
{
for(int z=0;z<ROWS;z++)
{
for(int x=0;x<COLUMNS;x++)
{
theBoard[z][x] = " ";
}
}
}
// fills the board in a way that is allowed in sudoku puzzles
public void fillBoard()
{
int i=0;
// create a boolean array to store the true/false values for where a number can be placed
boolean[] legal = new boolean[2];
//go through every spot on the board, placing a number in each one.
for(currentRow=0;currentRow<ROWS;currentRow++)
{
for(currentColumn=0;currentColumn<COLUMNS;currentColumn++)
{
do
{
// Generate a number 1-9, then change it to a string
num = randy.nextInt(9)+1;
number = String.valueOf(num);
// go through and see if the number can be placed in the current spot
while(!legal[0] || !legal[1])
{
// default the booleans to true
legal[0]=true;
legal[1]=true;
// If the number already appears in the row and the column, change the booleans to false to check again
if(number.equals(theBoard[i][currentColumn])) legal[0]=false;
if(number.equals(theBoard[currentRow][i])) legal[1]=false;
}
// after the number is allowed to be placed there, place it there.
theBoard[currentRow][currentColumn] = number;
}while(!legal[0] || !legal[1]);
//once the number has been put into the board, increase the value of i
i++;
}
// after a column has been filled, reset i
i=0;
}
}
// return a single string of "theBoard"
public String toString()
{
String board = "";
for(int row=0;row<ROWS;row++)
{
for(int col=0;col<COLUMNS;col++)
{
board = board +" " +theBoard[row][col];
}
board = board + "\n";
}
return board;
}
}
Hello, llemes4011.
Hm ... interesting task. Your problem here:
// If the number already appears in the row and the column, change the booleans to false to check again
if(number.equals(theBoard[i][currentColumn])) legal[0]=false;
if(number.equals(theBoard[currentRow][i])) legal[1]=false;Here you should check, whether your element is already appears in row and column (from your words) ... and all that you do is comparing it only with 2 elements of your 'theBoard'. That is why you have repetitions in your result 'theBoard'.
Atenka, thanks, i completely overlooked that, lol.
I thought i fixed that with this updated version, but nothing changed :(
I'm not going to put the entire code in again, just the changes (theBoard is now an int[][] instead of a String[][], and i updated the fillBoard() method, everything else is the same)
public int[][] theBoard = new int[ROWS][COLUMNS];
// fills the board in a way that is allowed in sudoku puzzles
public void fillBoard()
{
//go through every spot on the board, placing a number in each one.
for(currentRow=0;currentRow<ROWS;currentRow++)
{
// booleans to check if the number is in the row/column already
boolean inColumn = false;
boolean inRow = false;
boolean doneCheckingRow = false;
boolean doneCheckingCol = false;
for(currentColumn=0;currentColumn<COLUMNS;currentColumn++)
{
do
{
// Generate a number 1-9, then change it to a string
num = randy.nextInt(9)+1;
// go through and see if the number can be placed in the current spot
while(!inRow || !inColumn)
{
// check the rows and columns for the same number as the random number
for(int i=0;i<9;i++)
{
// If the the number is not in the current row, and the possition has the value zero.
// doneCheckingRow/Col is used to make sure true isn't returned for inRow/Column
// after false has allready been returned
if(!inRow && theBoard[i][currentColumn]==0 && !doneCheckingRow)
{
if(num!=theBoard[i][currentColumn]) inRow=true;
else {doneCheckingRow=true; inRow=false;}
}
// If the the number is not in the current column, and the possition has the value zero.
if(!inColumn && theBoard[currentRow][i]==0 && !doneCheckingCol)
{
if(num!=theBoard[currentRow][i]) inColumn=true;
else {doneCheckingCol=true; inColumn=false;}
}
}
}
// after the number is allowed to be placed there, place it there.
theBoard[currentRow][currentColumn] = num;
}while(!inRow || !inColumn);
}
// reset booleans after checking and placing numbers in the current row
inColumn = false;
inRow = false;
doneCheckingRow = false;
doneCheckingCol = false;
}
}So your question is solved? If so, please mark thread as solved :)
no, sorry if i made it sound like it was. It still doesn't work. The same thing happens, multiples of the same number end up in the same rows and columns. That is updated code, but it still doesn't work........
I have a little variation on your 'old' code. It is not the best solution, but it is better than nothing. You can analyse it and make summary for yourself:
public void fillBoard()
{
int i=0;
//number of added numbers into row
int colAddedCount = 0;
//go through every spot on the board, placing a number in each one.
for(currentRow=0;currentRow<ROWS;currentRow++)
{
currentColumn = 0;
//'While' cycle instead 'for' to we have ability to change currentColumn inside it
while(currentColumn<COLUMNS)
{
//the column number for adding numbers into table
int col;
do
{
do
{
num = randy.nextInt(9)+1;
number = String.valueOf(num);
//cycle untill we find number, which is not in the row
}while(isAlreadyInRow(number,theBoard[currentRow]) == true);
//finding a valid column for our number
col = validColumn(number, theBoard, currentRow);
//about this: look later ...
if((colAddedCount == theBoard.length -1)&&(col==-1))
{
//clearing the whole row to fill it again
clearRow(currentRow, theBoard);
//reset the count of numbers, already added into row
colAddedCount = 0;
//resetting current column to refill the row
currentColumn = 0;
}
//if method validColumn returns '-1' it means, that we have to generate new number
}while(col == -1);
// after the number is allowed to be placed there, place it there.
theBoard[currentRow][col] = number;
//after adding new value to row we increasing the count of already added values
colAddedCount++;
i++;
currentColumn++;
}
// after a row has been filled, reset i
i=0;
// after a row has been filled, reset colAddedCount
colAddedCount = 0;
}
}
//clearing the row of the table
public void clearRow(int row, String[][] table)
{
for(int col = 0; col < table[0].length; col++)
{
table[row][col] = " ";
}
}
//Searching for valid column for generated number (if not find - return '-1')
public int validColumn(String value, String[][] table, int chosenRow)
{
int column = -1;
boolean isValid = true;
for(int col = 0; col < table[0].length; col++)
{
for(int row = 0; row < table.length; row++)
{
if((table[row][col].equals(value)))
{
isValid = false;
}
}
if((isValid)&&(table[chosenRow][col].equals(" ")))
{
column = col;
break;
}
isValid = true;
}
return column;
}
//checking if the generated number is already in row
public boolean isAlreadyInRow (String value, String[] row)
{
for(int column = 0; column < COLUMNS; column++)
{
if(number.equals(row[column]))
{
return true;
}
}
return false;
}Ok, now about situation, that I had prefer to describe later: when I was trying to generate table, there was such thing - I've generated a few rows (let it be 4) ... then on the 5th row, when I've already had 8 number in table, the 9th number didn't passed to be on that place (because it is already been in column).
So I'm checking, if the number added into row is pre-last and if we couldn't find the valid row for it ... and if that situation appears, I reload whole row. Good luck. I hope it'll help you :)
Hey Antenka, thanks for all the help, and the comments in the code! =D I think from there i can figure out how to get the 3x3 square to be correct also.
Solved
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.