Wednesday, August 31, 2005

sudoku

if you haven't heard of sudoku yet, then you're at a big loss! it's such a fun game. the idea is that you're given a 9x9 grid like below. In each row, column, and square you must place the numbers 1 through 9. so that each number appears only once per row, column and square. It can be surpirsingly difficult! see the wikipedia here



at the theory lunch today, the speaker talked about sudoku from a theory perspective. here's the idea behind a zero knowledge proof. suppose alice wants to show bob that she has the solution to a given sudoku puzzle (there is only 1 solution) without revealing the solution itself. the act of doing this is called giving a zero-knowledge proof, because alice has given no knowledge about the actual solution BUT has shown that there is a solution, and she knows it. i won't go into the details on this one, but ask me if you're interested. (for you techies, sudoku is an NP-hard problem).

if you want to play now, go here

2 comments:

om said...

hehehe.. well mine sweeper is also a very challenging game but this is different, and can be played with pen or pencil on paper, which makes it rock. i was talking to one guy who says he lost many hours a day to this game, and finally had to give it up to regain his sanity!

om said...

when you have to guess in sudoku, that means you're either doing a very hard puzzle or you suck. with you... anyway, sometimes you can't see far enough ahead, and that's why you're guessing. and sometimes you need to do that.

linking:

when you're posting, notice that there's a bunch of buttons above the posting area. one of them sort of looks like a link in a chain. hilite the text you want to add a link to, and then click the button, and enter your link!

Followers

Blog Archive