Sudoku solver

Try it out: http://www.snarkpit.net/dev/sudoku/

And http://www.sudoku.com/ for those who don't know what I'm talking about.

It doesn't have any ?ber-advanced things going on (such as noticing invalid grids) but it solves the puzzle like a human would :smile:

My dads been doing loads of these recently, does like 2 a day. Might give him the link incase he cant solve one.

Lep, what's your algorithm?

At first glance, it looks like you're enumerating all possible
locations for each number from 1-9, and then picking the first
possibility. Is this guaranteed to work?

er, This is the first time I've heard of sudoku, but it looks interesting, so correct me if I'm wrong about something.

Wiat is yours a puzzle or just something to solve them lep?

You mean like, actually, thinking, as in the meaning of

[size=10]

[/size]

• To have or formulate in the mind.
• <ol type="a"><li type="a"> To reason about or reflect on; ponder: Think how complex language is. Think the matter through.
  <li type="a">To decide by reasoning, reflection, or pondering: thinking what to do. </li>

</li>[*] To judge or regard; look upon: I think it only fair.
[*] To believe; suppose: always thought he was right.
[*] <ol type="a"><li type="a">To expect; hope: They thought she'd arrive early.
<li type="a">To intend: They thought they'd take their time. </li></ol></li>[*] To call to mind; remember: I can't think what her name was.
[*] To visualize; imagine: Think what a scene it will be at the reunion.
[*] To devise or evolve; invent: thought up a plan to get rich quick.
[*] [size=10]To bring into a given condition by mental preoccupation: He thought himself into a panic over the impending examination.

[/size] </ol>
Nah.

---

:: Forceflow.be :: Nuclear Dawn developer

Its a puzzle that has to have 1 through 9 in vertical and horizontal axis- why can't it use those words instead of having some stupid explanation. It doesn't look hard, just time consuming, and I'm sure theres better ways to spend my time...

Oooooh I just noticed the spell checker!

---

-[Better to be Honest than Kind]-

Hey, this sh*t is cool! I never knew about sudoku before, but now I've
been like... solving 6 or like that a day! It really is a logic, takes
me about 10-15 minutes to solve one. it's kinda cool. And - after I
finished 2, I made my own new record with Powerball :smile:

---

HL2 tutorials 'n' stuff: http://madedog.pri.ee
217.159.236.34:27050 - CSS Server - Clean | koffer.ee

yay for spirals. recursive spirals at that.

edit: erm, nevermind that. My theory just died in the last set of 9.

---

http://maze5.net

fraggard said:
Lep, what's your algorithm?

At first glance, it looks like you're enumerating all possible locations for each number from 1-9, and then picking the first possibility. Is this guaranteed to work?

er, This is the first time I've heard of sudoku, but it looks interesting, so correct me if I'm wrong about something.

No of course it doesn't use brute force to solve it- it tells you what it's doing if you put one in (or try a 'default' one by submitting a blank grid). It scans and fills, but it doesn't yet do contingencies ('guesswork' of sorts, ruling out options by trying them) which is needed for some of the trickier versions :/

It scans and fills

I think that's what I said earlier... In each iteration, for each
number between 0-9, you scan the entire grid, check whether the current
number can be placed in the current grid position, and if so, place it
there. Then if the row is 8 entries full, you put in the 9th.

1) Are you backtracking if you hit a deadend?

2) What's the complexity like?

Edit: Hmm, a slightly-more-complex set of constraints on the n-queens problem might do the trick. I dunno, /me needs sleep.

Fraggard why don't you find out by looking at the source instead of asking questions you could answer yourself? :razz: Much easier that way than waiting for an answer too.

---

-[Better to be Honest than Kind]-

I was thinking more along the lines of something like this:
(semi-pseudocode)
Code:[quote]<div style="font-family:courier"><pre>
boolean solve (Board board, int row, int col)
{
for (int i=1; i<10; i++) //cycle through possibilities for the current cell
{
if ( board.isLegalMove(i, row, col) )
{
board.setCellContents(i, row, col);
cell c = board.nextOpenCell();
if (c == null)
return true;
if ( solve( board, c.row(), c.col() ) ) //yay recursion
return true;
}
}
board.setCellContents(0, row, col); //reset contents
return false;
}
[/pre][/quote]

---

http://maze5.net

We did a marginally similar thing to this for uni a while back. I had
to write a program in first year that figured out how many different
VALID board layouts were possible in noughts and crosses. Don't think
we ever did find out what the definate correct number was - if the
figure looked anywhere near right, and the rules you were using to
generate different boards and check for validity looked good, then we
passed :smile: Was quite an interesting task for those early steps in
programming.

---

[img]http://card.mygamercard.net/sig/Default/reno84.png[/img]
Designer @ Haiku Interactive | ReNo-vation.net