*681*3***
*5**64*3*
2*****846
7**2**18*
1*56**7**
8**75***4
****8**52
*84*9***7
*72**63**

$ wc grid_solver.py
 100  314 3174 grid_solver.py
$

#include<iostream>
#include<string>
using namespace std;


int main(){
        int r[9],c[9],i,j,arr[9][9],rev[512];
        char ch;
        bool flag;
        memset(r,0,sizeof(r));  // row sum
        memset(c,0,sizeof(c)); // col sum
        for (i=0;i<9;i++)
                for (j=0;j<9;j++){
                        cin>>ch;
                        if (ch=='*')
                                arr[i][j]=-1;
                        else
                        {
                                arr[i][j]=ch-'1';  //0 based
                                r[i]+=1<<arr[i][j];  //sum row
                                c[j]+=1<<arr[i][j];  // sum col
                        }
                }
       
        for (i=0;i<512;i++)
                rev[i]=-1;          //reverse log table
        for (i=0;i<10;i++)
                rev[1<<i]=i;
        arr[0][0]=-1;   
        flag = true;
        int cnt=0;
        while(flag){
                flag = false;
                for (i=0;i<9 && !flag;i++)
                        for (j=0;j<9 && !flag;j++){
                                int tmp = 511-(r[i]|c[j]);
                                if (rev[tmp]>=0)
                                {
                                        arr[i][j]=rev[tmp];
                                        flag=true;
                                        r[i]+=tmp;
                                        c[j]+=tmp;
                                }
                        }
        for (i=0;i<9;i++){
                for (j=0;j<9;j++)
                        cout<<arr[i][j]+1;
                cout<<endl;
                }
        cout<<endl;
        for (i=0;i<9;i++) cout<<r[i]<<" "; cout<<endl;
        for (i=0;i<9;i++) cout<<c[i]<<" "; cout<<endl;
        }
       
       
                       
        return 0;
}

4***13**8
*587**1*4
1****49**
89*2*74*1
*41***27*
7*2451*89
*173**846
**4178592
28*64**1*

429513768
658792134
173864925
896237451
541986273
732451689
917325846
364178592
285649317

import java.util.*;
import java.io.*;
import java.lang.*;

class Grid {
        public static int[][] grid = new int[9][9];
       
        public static void main(String[] args) throws IOException {
                Vector[][] Vgrid = new Vector[9][9];
               
                for (int i = 0; i < 9; i ++)for (int j = 0; j < 9; j ++) Vgrid[i][j] = new Vector();
               
        BufferedReader input = new BufferedReader(new FileReader("grid.txt"));
        for (int r = 0; r < 9; r ++) {
            String str = input.readLine();
            for (int c = 0; c < 9; c ++) {
                if (str.charAt(c) == '*') {
                    grid[c][r] = -1;
                    for (int i = 1; i <= 9; i++) Vgrid[c][r].add(new Integer(i));
                } else {
                    grid[c][r] = str.charAt(c) - '0';
                    Vgrid[c][r].add(new Integer(grid[c][r]));
                }
            }
        }
       
        for (int c = 0; c < 9; c ++) {
            for (int r = 0; r < 9; r ++) {
                if (grid[c][r] < 0) {
                    for (int i = 0; i < 9; i ++) {
                        Vgrid[c][r].remove(new Integer(grid[i][r]));
                        Vgrid[c][r].remove(new Integer(grid[c][i]));
                    }
                    for (int i = 0; i < 3; i ++) for (int j = 0; j < 3; j ++) {
                        Vgrid[c][r].remove(new Integer(grid[((int)c/3)*3 + i][((int)r/3)*3 + j]));
                    }
                }
            }
        }
            
        Solve (Vgrid, 0, 0);
    }

    static void Solve (Vector[][] Vgrid, int c, int r) {
        if (r == 9) {
            for (int row = 0; row < 9; row ++) {
                String str = "";
                for (int col = 0; col < 9; col ++) {
                    str += grid[col][row] + " ";
                }
                System.out.println(str);
            }

         System.out.println("");
            return;
        }
       
        Vector[][] Tgrid = new Vector[9][9];
                for (int m = 0; m < 9; m ++) for (int n = 0; n < 9; n ++) Tgrid[m][n] = (Vector) Vgrid[m][n].clone();

        if (grid[c][r] < 0) {
            for (int i = 0; i < Tgrid[c][r].size(); i ++) { 
                      
                grid[c][r] = ((Integer)Tgrid[c][r].elementAt(i)).intValue();
                Tgrid[c][r].remove(new Integer(grid[c][r]));
               
                for (int j = 0; j < 9; j ++) {
                    if (grid[j][r] < 0) Tgrid[j][r].remove(new Integer(grid[c][r]));
                    if (grid[c][j] < 0) Tgrid[c][j].remove(new Integer(grid[c][r]));
                }
               
                for (int j = 0; j < 3; j ++) for (int k = 0; k < 3; k ++) {
                    Tgrid[((int)c/3)*3 + j][((int)r/3)*3 + k].remove(new Integer(grid[c][r]));
                }
               
                if (c < 8) Solve (Tgrid, c+1, r);
                else Solve (Tgrid, 0, r+1);
               
                grid[c][r] = -1;
                for (int m = 0; m < 9; m ++) for (int n = 0; n < 9; n ++) Tgrid[m][n] = (Vector) Vgrid[m][n].clone();
            }
        } else {
            if (c < 8) Solve (Tgrid, c+1, r);
            else  Solve (Tgrid, 0, r+1);
        }
    }
}

4***13**8
*587**1*4
1****49**
89*2*74*1
*41***27*
7*2451*89
*173**846
**4178592
28*64**1*

4 6 1 8 5 7 9 3 2
2 5 7 9 4 3 1 6 8
9 8 3 6 1 2 7 4 5
5 7 8 2 9 4 3 1 6
1 9 6 3 8 5 2 7 4
3 2 4 7 6 1 5 8 9
7 1 9 4 2 6 8 5 3
6 3 2 5 7 8 4 9 1
8 4 5 1 3 9 6 2 7

4 9 2 7 1 8 6 3 5
6 5 3 4 9 2 1 8 7
8 7 1 6 5 3 9 4 2
1 8 9 2 6 7 3 5 4
2 6 7 3 4 5 8 9 1
3 4 5 9 8 1 7 2 6
5 2 8 1 7 9 4 6 3
7 3 4 8 2 6 5 1 9
9 1 6 5 3 4 2 7 8

            6,7,0, 0,5,0, 0,2,3,
            0,0,0, 2,0,9, 0,0,0,
            0,0,9, 0,4,0, 8,0,0,
             
            3,6,0, 0,0,0, 0,5,2,
            0,0,0, 0,0,0, 0,0,0,
            7,5,0, 0,0,0, 0,4,9,
           
            0,0,7, 0,6,0, 1,0,0,
            0,0,0, 9,0,4, 0,0,0,
            9,4,0, 0,2,0, 0,8,6

4  2  9    5  1  3    7  -  8   
 3  5  8    7  2  9    1  6  4   
 1  7  6    8  -  4    9  2  3   

 8  9  3    2  6  7    4  5  1   
 5  4  1    9  8  -    2  7  -   
 7  6  2    4  5  1    3  8  9   

 9  1  7    3  -  2    8  4  6   
 6  3  4    1  7  8    5  9  2   
 2  8  5    6  4  -    -  1  7

674851923
835279461
129346875
361498752
492735618
758612349
287563194
516984237
943127586

  9 8
6 8 4   9
53   67
497  3 2
   2 1
 5 8  396
  47   53
7   3 4 8
    6 9

?49?87??5
678?4???9
53?9?6784
497653821
???291547
?5?874396
9?47???53
72??394?8
???46?972

var initialPossible : array 1 .. 9, 1 .. 9, 1 .. 9 of boolean
var grid : array 1 .. 9, 1 .. 9 of int

proc loadGrid (fileName : string)

    var file : int
    var line : string

    open : file, fileName, get

    for row : 1 .. 9
        get : file, line
        for col : 1 .. 9
            if line (col) = "*" then
                grid (col, row) := -1
                for i : 1 .. 9
                    initialPossible (col, row, i) := true
                end for
            else
                grid (col, row) := strint (line (col))
                for i : 1 .. 9
                    initialPossible (col, row, i) := false
                end for
            end if
        end for
    end for

    close (file)

    for col : 1 .. 9
        for row : 1 .. 9
            if grid (col, row) < 0 then
                for i : 1 .. 9
                    if grid (i, row) > 0 then
                        initialPossible (col, row, grid (i, row)) := false
                    end if
                    if grid (col, i) > 0 then
                        initialPossible (col, row, grid (col, i)) := false
                    end if
                end for
                for i : 1 .. 3
                    for j : 1 .. 3
                        if grid (((col - 1) div 3) * 3 + i, ((row - 1) div 3) * 3 + j) > 0 then
                            initialPossible (col, row, grid (((col - 1) div 3) * 3 + i, ((row - 1) div 3) * 3 + j)) := false
                        end if
                    end for
                end for
            end if
        end for
    end for

end loadGrid

proc solve (possible : array 1 .. 9, 1 .. 9, 1 .. 9 of boolean, c, r : int)

    if r = 10 then
        for row : 1 .. 9
            for col : 1 .. 9
                put grid (col, row), " " ..
            end for
            put ""
        end for
        return
    end if

    if grid (c, r) < 0 then
        var tempPossible := possible

        for i : 1 .. 9
            if tempPossible (c, r, i) then
                grid (c, r) := i

                for j : 1 .. 9
                    tempPossible (j, r, grid (c, r)) := false
                    tempPossible (c, j, grid (c, r)) := false
                end for

                for j : 1 .. 3
                    for k : 1 .. 3
                        tempPossible (((c - 1) div 3) * 3 + j, ((r - 1) div 3) * 3 + k, grid (c, r)) := false
                    end for
                end for

                if c < 9 then
                    solve (tempPossible, c + 1, r)
                else
                    solve (tempPossible, 1, r + 1)
                end if

                tempPossible := possible

                grid (c, r) := -1
            end if
        end for
    else
        if c < 9 then
            solve (possible, c + 1, r)
        else
            solve (possible, 1, r + 1)
        end if
    end if

end solve

loadGrid ("grid2.txt")
solve (initialPossible, 1, 1)

put "\n\n", Time.Elapsed

5 2 7 3 1 6 4 8 9
8 9 6 5 4 2 7 3 1
3 1 4 9 8 7 5 6 2
1 7 2 4 5 3 8 9 6
6 8 9 2 7 1 3 5 4
4 5 3 6 9 8 2 1 7
9 4 1 8 2 5 6 7 3
7 6 5 1 3 4 9 2 8
2 3 8 7 6 9 1 4 5

92 |83 |
   |   |
  1| 7 |85
---+---+---
13 |   |  8
  8| 4 |6
4  |   | 97
---+---+---
 16| 8 |4
   |   |
   | 17| 69

92 |83 |
   |   |9
 41| 7 |85
---+---+---
13 |   | 48
  8| 4 |6
46 |  8| 97
---+---+---
 16| 8 |4
   |   | 8
   | 17| 69

        public void solve() {
                foundSolution = false;
                findSolution((byte) 0, grid);
        }

        private void findSolution(byte b, byte[][] param0) {   
                if (b == 81) {
                        foundSolution = true;
                        solvedGrid = param0;
                        return;
                }
                byte[][] temp= new byte [9][9];
                for (byte i = 0; i < 9; i++) {
                        for (byte j = 0; j < 9; j++) {
                                temp[i][j] = param0[i][j];
                        }
                }
               
                for (Byte t : getPossibleValues(param0,(byte) (b / 9), (byte) (b % 9))) {
                        if (!foundSolution) {
                                temp[b / 9][b % 9] = t;
                                findSolution((byte)(b+1), temp);
                        } else {
                                return;
                        }
                }
        }

        private TreeSet<Byte> getPossibleValues(byte [] [] param0, byte x, byte y) {
                TreeSet<Byte> returnable = new TreeSet<Byte>();
                if (gridChk[x][y] != CELL_LOCKED) {
                        for (byte i = 0; i <= 9; i++) {
                                returnable.add(i);
                        }
                        for (byte i = 0; i < 9; i++) {
                                returnable.remove(param0[x][i]);
                                returnable.remove(param0[i][y]);
                                returnable.remove(param0[((x / 3) * 3) + (i / 3)][((y / 3) * 3)
                                                + (i % 3)]);
                        }
                } else {
                        returnable.add(param0[x][y]);
                }
                return returnable;
        }

setscreen ("text")

var fi, cl : int
var mString : string
var grid, gCopy : array 1 .. 9, 1 .. 9 of string
var row, col : array 1 .. 2 of int
var bArray : array 1 .. 9 of boolean
var rowToStrArray : array 1 .. 9 of string
var rowLocations : flexible array 1 .. 0 of int
var randNum : int
var randNumString : string := ""
var counter := 1
var noneLeft : boolean := false

open : fi, "data.txt", get

%%%-----------------------------------------------------------------------------------------------%%%

%%% Boolean array initialization

for x : 1 .. 9
    get : fi, mString
    for y : 1 .. 9
        grid (x, y) := mString (y)
        gCopy (x, y) := grid (x, y)
    end for
end for

%%% Row and column storage used for random solution
% proc rowAndColStorage (r : int, c : int)
%     for x : 1 .. 9
%         bArray (x) := true
%     end for
%     for x : 1 .. 9
%         if (grid (r, x) not= "*") then
%             bArray (strint (grid (r, x))) := false
%         end if
%         if (grid (x, c) not= "*") then
%             bArray (strint (grid (x, c))) := false
%         end if
%     end for
% end rowAndColStorage
%
% %%% Three by three storage used for random solutiona
% proc threeByThree (currentR : int, currentC : int)
%     for r : row (1) .. row (2)
%         for c : col (1) .. col (2)
%             if grid (r, c) not= "*" then
%                 bArray (strint (grid (r, c))) := false
%             end if
%         end for
%     end for
% end threeByThree

%%%-----------------------------------------------------------------------------------------------%%%

%%%-----------------------------------------------------------------------------------------------%%%

%%% Normal method functions used for normal method solutions

%%% init the grid to g2
proc inti
    for x : 1 .. 9
        for y : 1 .. 9
            grid (x, y) := gCopy (x, y)
        end for
    end for
end inti

fcn checker : boolean
    for x : 1 .. 9
        for y : 1 .. 9
            if grid (x, y) = "*" then
                result true
            end if
        end for
    end for
    result false
end checker

%%% Rows and columns checker
fcn rowAndColChecker (num : string, r : int, c : int) : boolean
    for x : 1 .. 9
        if (grid (r, x) = num) or (grid (x, c) = num) then
            result false
        end if
    end for
    result true
end rowAndColChecker

%%% Check Three By Three
fcn threeBy3Checker (num : string, r : int, c : int) : boolean
    var x1, y1, x2, y2 : int
    if r <= 3 and c <= 3 then
        x1 := 1
        x2 := 3
        y1 := 1
        y2 := 3
    elsif r <= 3 and (c <= 6 and c >= 4) then
        x1 := 1
        x2 := 3
        y1 := 4
        y2 := 6
    elsif r <= 3 and (c <= 9 and c >= 7) then
        x1 := 1
        x2 := 3
        y1 := 7
        y2 := 9
    elsif (r <= 6 and r >= 4) and (c <= 3) then
        x1 := 4
        x2 := 6
        y1 := 1
        y2 := 3
    elsif (r <= 6 and r >= 4) and (c <= 6 and c >= 4) then
        x1 := 4
        x2 := 6
        y1 := 4
        y2 := 6
    elsif (r <= 6 and r >= 4) and (c <= 9 and c >= 7) then
        x1 := 4
        x2 := 6
        y1 := 7
        y2 := 9
    elsif (r <= 9 and r >= 7) and (c <= 3) then
        x1 := 7
        x2 := 9
        y1 := 1
        y2 := 3
    elsif (r <= 9 and r >= 7) and (c <= 6 and c >= 4) then
        x1 := 7
        x2 := 9
        y1 := 4
        y2 := 6
    elsif (r <= 9 and r >= 7) and (c <= 9 and c >= 7) then
        x1 := 7
        x2 := 9
        y1 := 7
        y2 := 9
    end if
    for x : x1 .. x2
        for y : y1 .. y2
            if grid (x, y) = num then
                result false
            end if
        end for
    end for
    result true
end threeBy3Checker

%%%-----------------------------------------------------------------------------------------------%%%

%%% Main Loop Processing

row (1) := 1
row (2) := 3
col (1) := 1
col (2) := 3

% for r : 1 .. 9
%     for c : 1 .. 9
%         if c > col (2) then
%             col (1) := c
%             col (2) := c + 2
%         end if
%         if grid (r, c) = "*" then
%             %%% NORMAL OLD METHOD
%
%             % for count : 1 .. 9
%             %     if ((rowAndColChecker (intstr (count), r, c)) and (threeBy3Checker (intstr (count), r, c))) then
%             %         grid (r, c) := intstr (count)
%             %         exit
%             %     end if
%             % end for
%
%             %%% RANDOM METHOD BEGINS
%
%             % rowAndColStorage (r, c)
%             % threeByThree (r, c)
%             % loop
%             %     randint (randNum, 1, 9)
%             %     if bArray (randNum) = true then
%             %         grid (r, c) := intstr (randNum)
%             %         for x : 1 .. 9
%             %             for y : 1 .. 9
%             %                 if y = 1 then
%             %                     put ""
%             %                 end if
%             %                 put grid (x, y), "-" ..
%             %             end for
%             %         end for
%             %         put ""
%             %         for x : 1 .. 9
%             %             put x, " ", bArray (x)
%             %         end for
%             %         Input.Pause
%             %         exit
%             %     end if
%             % end loop
%         end if
%         % if grid (r, c) = "*" then
%         %     put r, " ", c
%         % end if
%     end for
%     col (1) := 1
%     col (2) := 3
%     if r > row (2) then
%         row (1) := r
%         row (2) := r + 2
%     end if
% end

%%--------------------------------------------------------------------------------------------

%%% Thrid method solution

%%% Row checker

% for x : 1 .. 9
%     rowToStrArray (x) := ""
% end for
%
% for x : 1 .. 9
%     for y : 1 .. 9
%         rowToStrArray (x) += grid (x, y)
%     end for
% end for
%
% proc rowChecker (num : string)
%     for x : 1 .. 9
%         if index (rowToStrArray (x), num) = 0 then
%             new rowLocations, upper (rowLocations) + 1
%             rowLocations (upper (rowLocations)) := x
%         end if
%     end for
% end rowChecker
%
% fcn colChecker (num : string, c : int) : boolean
%     for x : 1 .. 9
%         if grid (x, c) = num then
%             result true
%         end if
%     end for
%     result false
% end colChecker
%
% proc rowChecker2 (num : string, r : int)
%     for x : 1 .. 9
%         if grid (r, x) = "*" then
%             if not (colChecker (num, x)) then
%                 put "(" + intstr (r) + "," + intstr (x) + ")" + " "
%             end if
%         end if
%     end for
% end rowChecker2
% %%--------------------------------------------------------------------------------------------
%
% for x : 1 .. 9
%     put x, " "
%     free rowLocations
%     rowChecker (intstr (x))
%     for y : 1 .. upper (rowLocations)
%         rowChecker2 (intstr (x), rowLocations (y))
%     end for
%     put ""
% end for

%%--------------------------------------------------------------------------------------------

%Fourth Attempt solution. (Random brute force)

proc solve
    for x : 1 .. 9
        for y : 1 .. 9
            randNumString := ""
            if grid (x, y) = "*" then
                loop
                    randNum := Rand.Int (1, 9)
                    if index (randNumString, intstr (randNum)) <= 0 then
                        randNumString += intstr (randNum)
                    end if
                    if length (randNumString) = 9 then
                        noneLeft := true
                        exit
                    end if
                    exit when (rowAndColChecker (intstr (randNum), x, y) and threeBy3Checker (intstr (randNum), x, y))
                end loop
                if not (noneLeft) then
                    grid (x, y) := intstr (randNum)
                end if
                if noneLeft then
                    return
                end if
            end if
        end for
    end for
end solve

%Plotting the grid
proc display
    for x : 1 .. 9
        for y : 1 .. 9
            if y = 1 then
                put ""
            end if
            put grid (x, y), "-" ..
        end for
    end for
end display

solve

loop
    randNumString := ""
    exit when not (checker)
    if noneLeft then
        noneLeft := false
    end if
    inti
    solve
end loop

display
clock (cl)
put skip, "Time Taken : ", round (cl / 1000), " seconds."