Sudoku

Well, I have been cutting the sudoku puzzles on Michigan Daily and using that to kill time during boring lectures... But, after this project, I swear I will never see sudoku as an entertainment??!!

anyway...

just look at what I wrote for my sudoku C++code, this is not the code, just the comment for one function, how to generate a random suduko puzzle... Argh!

/*
Firstly we randomly generate the upper left subgrid(which will remain constant throughout).
There are BOARD_SIZE!(in this case 9! = 362880) different permutations of the first subgrid.
We can write out the entire sudoku from manipulating the first subgrid

***************************

Example:

first subgrid (also known as subgrid A00)
123
456
789

so we write down the entire sudoku grid as


123 | 456 | 789 - column 0
456 | 789 | 123 - column 1
789 | 123 | 456 - column 2
----------------------
234 | 567 | 891 - column 3
567 | 891 | 234 - column 4
891 | 234 | 567 - column 5
----------------------
345 | 678 | 912 - column 6
678 | 912 | 345 - column 7
912 | 345 | 678 - column 8


***************************

After that, we modify this entire sudoku grid so that a certain number is not always at the same place.
We will not modify the subgrid A00 as any changes has already been permutated in the first step.

We do the modification by swapping any corresponding colums
Column 3 and 6 are corresponding columns
Column 4 and 7 are corresponding columns
Column 5 and 8 are corresponding columns
there are BOARD_N*BOARD_N*BOARD_N (in this case 2^3=8) possible colums swappings which will generate a different sudoku board

and swapping any rows that are within the same horizontal subgrids
Rows in A01 A11 and A21
and/or
Rows in A02 A12 and A22
and there are (BOARD_N-1)*(BOARD_N!)*(BOARD_N!) (in this case 72) possible row swappings which will generate a different sudoku board

In total, our code will be able to generate
(BOARD_SIZE!)*(BOARD_N*BOARD_N*BOARD_N )*((BOARD_N-1)*(BOARD_N!)*(BOARD_N!))(in a 9*9 sudoku, it will be 209,018,880) different sudoku puzzles


In order to get random unknown space,
we force the value of rand()%2 into board[][].permanent
then reset the value of board[][].number to 0 if board[][].permanent is false

*/

posted by panda xuan @ 1:07 AM