This is a very good great free JavaScript Obfuscator (makes difficult to read) / Encrypt and it also compresses your code. I use it for my JavaScript code. It saved me from writing my own.
So we now have a 9 x 9 grid with numbers that fit the constraints of Sudoku rules:
1. Each row must contain the numbers 1 to 9.
2. Each column must contain the numbers 1 to 9.
3. Each 3 x 3 local square must contain the numbers 1 to 9.
Now we have to remove numbers from the board. We can’t just remove any numbers. We can only remove numbers that allow us to solve the puzzle with one solution.
One way to accomplish this is to randomly select a number, remove it then see if we can solve the puzzle. If we can’t, replace the number and try again. If we can, try again.
So obviously we need to write a Sudoku solving algorithm.
MY algorithm uses a while loop:
while ( ($blanksquaresleft == 1) and ($solvable == 1) ) {keep trying to solve the Sudoku grid}
Obviously if there are no blank squares left in our Sudoku’s 9 x 9 grid then our Sudoku grid is solvable as we have filled it in. Return a success code.
The $solvable variable is set to 1 if we have at least filled in one blank square during the last loop. This at least gives us the hope that this 9 x 9 grid is solvable. If, during the last loop, we did not fill in any blank squares, this Sudoku grid is not solvable, so quit and return our failure.
if ( ($LpNS > 0) or ($LpHS > 0) ) {$solvable = 1} #still might be solvable! keep going
else {$solvable = 0} #our algorithm can’t solve this board! quit and return a failure code
The next part we need to code are the algorithms to actually fill in the blank squares.
To my knowledge, there are 7 basic methods to try and solve Sudoku puzzles. Naked Singles (NS), Hidden Singles (HS), Naked Pairs (NP), Hidden Pairs (HP), Intersection Removal (IR), X-Wing (XW), and Y-Wing (YW).
Naked Singles (NS): Naked Singles iterates through all the squares on the board, calculating the possible values in each cell based on Sudoku’s rules listed above. When we find a cell with a single possibility we fill in the Sudoku board with that value. Then we recalculate all the possibilities based on the number we just added to the Sudoku board.
Hidden Singles (HS): Hidden Singles scan each row, column and 3 x 3 square for the ‘number of possibilities’ for each number ranging from one to nine. When it finds a cell containing a possibility which appears exactly once in a row, column or 3 x 3 square, we fill in the Sudoku board with that value. Then we recalculate all the possibilities based on the number we just added to theSudoku board.
Naked Pairs (NP):
The first version of Naked Pairs searches each region for two possibility values that occur only twice in, and share two cells, which may or may not contain other possibilities. Because they occur
only in these two cells, one of them must go in one cell and the other in the second. Therefore,
any other values in these two cells may be eliminated.
The second version scans each region for two cells, each containing ONLY the same two possibilities. Because one of these values must occur in each of the two cells, they cannot occur anywhere else in that region, and may be eliminated from the lists of possibilities for every other cell in the region.
Hidden Pairs (HP):
Hidden Pairs are taken care of by the combination of Naked Squares and Hidden Singles algorithms.
Intersection Removal (IR):
If exactly two or three possibilities exist for a single number in one row or column and they are also confined to one box, their values may be eliminated from the rest of the row or column.
If exactly two possibilities exist for a number in a row or column of a box, the number can be eliminated from the rest of the box.
X-Wing (XW):
Look for a single value that occurs exactly twice in two rows. If the cells containing
the value line up in two columns to form a rectangle, all occurrences of the value may be
removed from both columns. This also works the other way, starting with columns and eliminating
from rows.
Y-Wing (YW)
Y-wings work by eliminating possibilities from intersections of influence. Each cell exerts
a range of influence on all the others cells in the same row, column, and box. Y-wing is a
complex, advanced technique, so we present an example:
Suppose a cell has exactly two possibilities A and B. This cell AB is the pivot. Consider
two cells, AC and BC, which are influenced by AB, but do not influence each other. If they
each share exactly one possibility with AB and exactly one possibility with each other, then
the possibility held in common between AC and BC, C, can be eliminated from every cell in
the intersection of AC and BC’s ranges of influence.
If we finally fill in all the Sudoku squares, we return successfully and try to remove yet another square from the Sudoku board and try and solve that board.
My breakout condition for the Sudoku number removal loop, is set a time limit. My code is sufficiently fast that 2 seconds is plenty to get the Suduku board down to 25 visible numbers.
Step one of creating a Sudoku puzzle is obviously filling in the whole 9 x 9 grid with numbers that fit the constraints of Sudoku rules:
1. Each row must contain the numbers 1 to 9.
2. Each column must contain the numbers 1 to 9.
3. Each 3 x 3 local square must contain the numbers 1 to 9.
After staring at a blank page for a few hours, I decided to see how others tackled the task of creating Sudoku puzzles.
Some interesting pages I found were:
http://davidbau.com/archives/2006/09/04/sudoku_generator.html
http://www.sudokuonline.us/make_your_own_sudoku_puzzle.php
http://ostermiller.org/qqwing/
http://www.codeproject.com/KB/recipes/Abhishek_Sudoku.aspx
The last link is the one that sparked an idea for my own algorithm. In broken English the author attempts to explain how he wrote his program. I misinterpreted parts of his article, but it created a few good ideas to start my own Sudoku algorithm.
To fill the Sudoku grid, I use what I term a 9 x 9 Potential Array. What each cell in the Potential Array holds is a list of possible values that could potentially work in that cell based on Sudoku rules.
With a blank 9 x 9 Sudoku grid, each cell in the Potential Array must be (1..9) as there are no limitations yet.
I then go through every cell in the Potential Array looking for a list that only contains one number. If it contains one number, that cell in the Sudoku Game Array MUST become that number.
If there are no lists in the Potential Array containing a single number, then we find an empty cell in the Sudoku Game Array. In the corresponding Potential Array, we choose one of the numbers in the Potential list for that cell and place it in the Sudoku Game Array.
Each time we set a value in the Sudoku Game Array, we must recalculate the Potential Array based on the values placed in the Sudoku Game Array. For example, if there is a 7 in row 2, there can be no other 7’s in the rest of the row. Therefore the all the Potential Array lists for row 2 will be stripped of the number 7. The same holds true for the cells column and the local 3 x 3 square that the cell resides in.
If we find a list in the Potential Array that contains NO values, then our attempt at filling the Sudoku board has failed, and we must start again.
Using this method finds a workable Sudoku grid between 1 to ten try’s on average.
The next article will cover the task of removing numbers from the Sudoku Game Array so we can have a Sudoku puzzle with only one possible solution.
I had a written some code to generate dynamic images on our website. I soon discovered that my images were not being listed in Google’s image section.
The following URL generates the required image:
http://www.somewhereincanada.com/barcode/barcode.php?code=001600064300&mode=gif
However, when I tried to save it to my desktop it saves it as barcode.php.png . Google will not list it in it’s image section as ‘barcode.php?code=001600064300&mode=gif’ is not a valid name for an image file.
One solution was to have my script save the generated image to my server. Then I could redirect web browser’s to the generated image by returning the text:
<META HTTP-EQUIV=”Refresh” CONTENT=”0; URL=/barcode/images/001600064300.gif”>
But by doing that I am using up valuable space on our web host.
It would be nice if I could have the URL:
http://www.somewhereincanada.com/barcode/images/001600064300.gif
call my script and dynamically generate the image.
This is possible by using Apache’s Module mod_rewrite.
By using mod_rewrite, I can cause the previous URL to call the script barcode.php
See:
http://www.workingwith.me.uk/articles/scripting/mod_rewrite
for more information.
To see mod_rewrite in action, try replacing any of the digits in the following URL with another. Likewise try replacing .gif with .jpg or .png
http://www.somewhereincanada.com/barcode/images/001600064300.gif
Now Google will see links of this format as actual images on my site and index them.
To make it all work, the following was required:
In an .htaccess file in our /barcode/ directory is the following text:
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /barcode/images/
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /barcode/barcode.php [L]
</IfModule>
The previous .htaccess file tells Apache to turn web requests for:
/barcode/images/001600064300.gif
to
/barcode/barcode.php
Note that the folder ‘/barcode/images/’ does not even exist.
http://www.somewhereincanada.com/barcode/images/hjgksad/asd/asd/001600064300.gif
will generate an image also!
On my first attempt, I added the following code to barcode.php. It strips out the ‘001600064300′ and ‘gif’ parts from
/barcode/images/001600064300.gif
found in the PHP variable $_SERVER["REQUEST_URI"]. Then took those two values and fed them into the routines that would have normally obtained the values from
?code=001600064300&mode=gif
if ($code == ”)
{
$URIline = $_SERVER["REQUEST_URI"];
//split uri into parts
$urlparts = array();
$urlparts = split(”/”, $URIline);
//get last part image.jpg
$imagename = array_pop($urlparts);
$filenameparts = array();
$filenameparts = split(”\.”, $imagename);
$code = $filenameparts[0];
$mode = $filenameparts[1]; //file extension
if ($mode == ”)
{
$mode=’png’;
}
}
If you are comfortable with Regular Expressions, there is a better way to accomplish this.
I could have used mod_rewrite to turn:
http://www.somewhereincanada.com/barcode/images/001600064300.gif
directly into a call to:
http://www.somewhereincanada.com/barcode/barcode.php?code=001600064300&mode=gif
Then I would not have had to modify barcode.php
Here is how I obtained the same results by using Regular Expressions in .htaccess:
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /barcode/images/
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule ([0-9]+)\.([a-zA-Z]+)$ /barcode/barcode.php?code=$1&mode=$2 [L]
</IfModule>
Apache staff say mod_rewrite is difficult to master. So keep it simple.