programming sudoku java

[erikpc43]

So I am programming game sudoku and I'm at the checking point. Its 25x25 sudoku. Do i need to check every 5x5 square and every row and every column for duplicated numbers? Or is it okay just to check the sum of every column and row? It has to be 325 else its false. I'm enclosing picture for easier visualization.

 

 

[mariushm]

I would imagine you have to check each row and each column to have numbers showing up just once.

then also each individual 5x5 must have each number only once.

Not sure where you get that 325 value from.

 

 

[reniat]

computationally, you have to check each cell to sum the row/column anyway. You could also add some duplicate checking without additional big O time complexity if you use a hash table.

 

edit: derp you'd still need to check the 5x5 groups for duplicates, but you could do something clever with something like a Trie structure to ensure there are no collisions in each 5x5 group while you do your row/column summing. Basically when you check a cell, keep track of which part of the grid its in and add it to the the appropriate trie bucket, and the have that bucket containing a hash table of all cells.

[erikpc43]

7 hours ago, mariushm said:

I would imagine you have to check each row and each column to have numbers showing up just once.

then also each individual 5x5 must have each number only once.

Not sure where you get that 325 value from.

 

 

If you sum number from 1-25 you will get exactly 325. I kinda tried to get some cases when there sum also 325 and there are numbers duplicating, but with no success. I also tried this on 9x9 sudoku which is easier and easier to handle, but also when I try to switch up numbers the sum of row/column came out wrong.

[erikpc43]

5 hours ago, reniat said:

computationally, you have to check each cell to sum the row/column anyway. You could also add some duplicate checking without additional big O time complexity if you use a hash table.

 

edit: derp you'd still need to check the 5x5 groups for duplicates, but you could do something clever with something like a Trie structure to ensure there are no collisions in each 5x5 group while you do your row/column summing. Basically when you check a cell, keep track of which part of the grid its in and add it to the the appropriate trie bucket, and the have that bucket containing a hash table of all cells.

I'm not that far into java yet and I'm still learing the basic. I didn't even heard about hash table or trie structure before. It's managable with basic java and I want to keep it that way. But thanks for help anyway. Better to practice basics to perfection, before moving on.

[mariushm]

If you allow player to enter any number between 1 and 25 in each square, what would stop him from entering in 4 cells values 2,2,3,3 (total=10) instead of 1,2,3,4 (total=10)?

so checking if sum is 325 would only work if you actually make a check each time a cell changes and refuse new value if another cell in the 5x5 square has that number.

sounds easier to just check that a number does not appear twice.

 

in php I would do it like this ...

 

<?php
// two-dimensional array holding the values of each cell 
// ex cells[0,0] - top left cell 
$cells = array(); 

// read the numbers from a horizontal or vertical line or a region 
// and see if they're all unique and showing only once
// ex for 25x25 grid you would say 0,0,0,24 to get the first vertical column

function isValidLineOrCell($x,$y,$width,$height) {
	global $cells;
	$numbers_total = ($width-$x+1)*($height-$y+1);
	$numbers = array();
	for ($i=1;$i<=$numbers_total;$i++) {
		$numbers[$i] = 0;
	}
	for ($j=$y;$j<=$height;$j++) {
		for ($i=$x;$i<=$width;$i++) {
			$value = $cells[$i,$j];
			$numbers[$value]++;
		}
	}
	for ($i=1;$i<=$numbers_total;$i++) {
		// either number wasn't used, or used more than once, so bad line or cell
		if ($numbers[$i]!=1) return FALSE; 
	}
	return TRUE;
}

// check each horizontal line :
for ($j=0;$j<25;$j++) {
	if (isValidLineOrCell(0,$j,24,$j)==FALSE) die('Error on horizontal line '.$j);
}
// check each vertical line :
for ($i=0;$i<25;$i++) {
	if (isValidLineOrCell($i,0,$i,24)==FALSE) die('Error on vertical line '.$i);
}
// check individual 5x5 cells :
for ($j=0;$j<5;$j++) {
 for ($i=0;$i<5;$i+=) {
	 $posx = $i*5;
	 $posy = $j*5;
	 if (isValidLineOrCell($posx,$posy,$posx+4,$posy+4)==FALSE) die('Error in cell with left corner at '.$i.'x'.$j);
 }
}
?>

 

[erikpc43]

8 minutes ago, mariushm said:

If you allow player to enter any number between 1 and 25 in each square, what would stop him from entering in 4 cells values 2,2,3,3 (total=10) instead of 1,2,3,4 (total=10)?

so checking if sum is 325 would only work if you actually make a check each time a cell changes and refuse new value if another cell in the 5x5 square has that number.

sounds easier to just check that a number does not appear twice.

 

in php I would do it like this ...

 

<?php
// two-dimensional array holding the values of each cell 
// ex cells[0,0] - top left cell 
$cells = array(); 

// read the numbers from a horizontal or vertical line or a region 
// and see if they're all unique and showing only once
// ex for 25x25 grid you would say 0,0,0,24 to get the first vertical column

function isValidLineOrCell($x,$y,$width,$height) {
	global $cells;
	$numbers_total = ($width-$x+1)*($height-$y+1);
	$numbers = array();
	for ($i=1;$i<=$numbers_total;$i++) {
		$numbers[$i] = 0;
	}
	for ($j=$y;$j<=$height;$j++) {
		for ($i=$x;$i<=$width;$i++) {
			$value = $cells[$i,$j];
			$numbers[$value]++;
		}
	}
	for ($i=1;$i<=$numbers_total;$i++) {
		// either number wasn't used, or used more than once, so bad line or cell
		if ($numbers[$i]!=1) return FALSE; 
	}
	return TRUE;
}

// check each horizontal line :
for ($j=0;$j<25;$j++) {
	if (isValidLineOrCell(0,$j,24,$j)==FALSE) die('Error on horizontal line '.$j);
}
// check each vertical line :
for ($i=0;$i<25;$i++) {
	if (isValidLineOrCell($i,0,$i,24)==FALSE) die('Error on vertical line '.$i);
}
// check individual 5x5 cells :
for ($j=0;$j<5;$j++) {
 for ($i=0;$i<5;$i+=) {
	 $posx = $i*5;
	 $posy = $j*5;
	 if (isValidLineOrCell($posx,$posy,$posx+4,$posy+4)==FALSE) die('Error in cell with left corner at '.$i.'x'.$j);
 }
}
?>

 

perhaps I wasn't careful enough to add that I'm only checking if already written sudoku is correct or not. The whole table is already filled with numbers and there is no changes. I just have to check if its false or not. Nothing else. But also thanks for help. I can also try your method, should work aswell.