Page 1 of 1

[Challenge] - Sudoku Grid

Posted: Thu Apr 22, 2010 7:59 am
by Grizzzzzzzzzz
Afternoon chaps,

Thought of this after seeing one of these bad boys on a newspaper earlier, was wondering what solutions people could imagine.

No need to actually make it playable, just a randomly generated 9x9 grid that abides by the number layout rules!

http://en.wikipedia.org/wiki/Sudoku

For those of you that don't know, a typical sudoku grid looks like this

Image



have the basic idea of how to do it in my head, but think that this challenge is an absolute stonker! So i'd be pretty impressed if it's easily achievable.


enjoy!

Re: [Challenge] - Sudoku Grid

Posted: Thu Apr 22, 2010 8:57 am
by Eran
Brute forcing it is not a problem, here's my solution:

Code: Select all

<?php
class Sudoku {
	protected $hGrid = array();
	protected $vGrid = array();
	public function generate() {
		$this -> vGrid = $this -> hGrid = array();
		$numbers = range(1,9);
		for($x = 0; $x < 9; $x++) {
			for($y = 0; $y < 9; $y++) {
				$this -> hGrid[$x] = !isset($this -> hGrid[$x]) ? array() : $this -> hGrid[$x];
				$this -> vGrid[$y] = !isset($this -> vGrid[$y]) ? array() : $this -> vGrid[$y];
				$box = $this -> getbox($x,$y);
				$options = array_diff($numbers,$this -> hGrid[$x],$this -> vGrid[$y],$box);
				$key = array_rand($options);
				if(!isset($options[$key])) {
					return $this -> generate();
				}
				$val = $options[$key];
				$this -> hGrid[$x][$y] = $this -> vGrid[$y][$x] = $val;
			}
		}
		return $this -> hGrid;
	}
	public function getbox($x,$y) {
		$right = ceil(($x + 1) / 3) * 3 - 1;
		$left = $right - 2;
		$bottom = ceil(($y + 1) / 3) * 3 - 1;
		$top = $bottom - 2;
		$box = array();
		for($x = $left; $x <= $right;$x++) {
			for($y = $top; $y <= $bottom;$y++) {
				if(isset($this -> hGrid[$x][$y])) {
					$box[] = $this -> hGrid[$x][$y];
				}
			}
		}
		return $box;
	}
}
$sudoku = new Sudoku();
$grid = $sudoku -> generate();
?>
<table cellpadding="2" cellspacing="0">
<?php foreach($grid as $row) : ?>
	<tr>
	<?php foreach($row as $val) : ?>
		<td><?php echo $val; ?></td>
	<?php endforeach; ?>
	</tr>
<?php endforeach; ?>
</table>
I'm interested in seeing algorithmic approaches to this.

Re: [Challenge] - Sudoku Grid

Posted: Thu Apr 22, 2010 9:31 am
by Grizzzzzzzzzz
nicely done
pytrin wrote:Brute forcing it is not a problem

I'm interested in seeing algorithmic approaches to this.
likewise, that's what i'm really looking forward to seeing