Currently I have a sudoku puzzle solver program and I've tried all the puzzles I can find that are labeled the "hardest" on various sudoku video games and puzzle books. My solver has solved them all. It currently uses the following 4 polynomial time rules (i.e. polynomial time if the board was $N^2 \times N^2$ instead of $9 \times 9$).
1) Check each cell to see if only one value is possible for the cell
2) Check to see for each row/column/block whether there is a value that only one cell can have
3) Check to see for each row/column/block whether there are 2 cells that can only have the same 2 values. (Then no other squares in the same group can have those values)
4) For each row/column and block that intersects it, see if there is a value that can only appear in the intersection 3 cells either for the row/column or for the block. Then no other squares in the row/column or block can have that value.
After these rules are applied repeatedly, if the puzzle is not solved, then the program guesses a value for a cell and sees if this leads to a solution or contradiction when the above four rules are applied repeatedly. If a contradiction is found, then the value is removed from the possible values for the cell. This guessing is applied separately for each cell+possible value if the number of possible values for the cell is 3 or less. There is no simultaneous guessing for multiple cells. If at least one possible value is removed for some cell, then the above 4 rules are again applied repeatedly until guessing is required again. And repeat. If it ever happens that the 4 rules and guessing don't provide any additional information, then the program gives up and prints out the partial solution it found.
Now, there are about 10 or 20 different polynomial time rules that have been devised to rule out possibilities and infer cells' values in sudoku, and I only implemented 4. Furthermore, the guessing only guesses one cell's value at a time and merely removes the value from the possible values for the cell if a contradiction is found. So it's weird to me that this solves all the hardest puzzles I can find. Can someone produce a puzzle hard enough that my program can't solve it?