Solve the Sudoku Python

PROGRAM TO SOLVE SUDOKU



# A Utility Function to print the Grid
def print_grid(arr):
    for i in range(9):
        for j in range(9):
            print arr[i][j],
        print ('n')
 
         
# Function to Find the entry in
# the Grid that is still  not used
# Searches the grid to find an
# entry that is still unassigned. If
# found, the reference parameters
# row, col will be set the location
# that is unassigned, and true is
# returned. If no unassigned entries
# remains, false is returned.
# 'l' is a list  variable that has
# been passed from the solve_sudoku function
# to keep track of incrementation
# of Rows and Columns
def find_empty_location(arr, l):
    for row in range(9):
        for col in range(9):
            if(arr[row][col]== 0):
                l[0]= row
                l[1]= col
                return True
    return False
 
# Returns a boolean which indicates
# whether any assigned entry
# in the specified row matches
# the given number.
def used_in_row(arr, row, num):
    for i in range(9):
        if(arr[row][i] == num):
            return True
    return False
 
# Returns a boolean which indicates
# whether any assigned entry
# in the specified column matches
# the given number.
def used_in_col(arr, col, num):
    for i in range(9):
        if(arr[i][col] == num):
            return True
    return False
 
# Returns a boolean which indicates
# whether any assigned entry
# within the specified 3x3 box
# matches the given number
def used_in_box(arr, row, col, num):
    for i in range(3):
        for j in range(3):
            if(arr[i + row][j + col] == num):
                return True
    return False
 
# Checks whether it will be legal
# to assign num to the given row, col
# Returns a boolean which indicates
# whether it will be legal to assign
# num to the given row, col location.
def check_location_is_safe(arr, row, col, num):
     
    # Check if 'num' is not already
    # placed in current row,
    # current column and current 3x3 box
    return not used_in_row(arr, row, num) and
           not used_in_col(arr, col, num) and
           not used_in_box(arr, row - row % 3,
                           col - col % 3, num)
 
# Takes a partially filled-in grid
# and attempts to assign values to
# all unassigned locations in such a
# way to meet the requirements
# for Sudoku solution (non-duplication
# across rows, columns, and boxes)
def solve_sudoku(arr):
     
    # 'l' is a list variable that keeps the
    # record of row and col in
    # find_empty_location Function   
    l =[0, 0]
     
    # If there is no unassigned
    # location, we are done   
    if(not find_empty_location(arr, l)):
        return True
     
    # Assigning list values to row and col
    # that we got from the above Function
    row = l[0]
    col = l[1]
     
    # consider digits 1 to 9
    for num in range(1, 10):
         
        # if looks promising
        if(check_location_is_safe(arr,
                          row, col, num)):
             
            # make tentative assignment
            arr[row][col]= num
 
            # return, if success,
            # ya !
            if(solve_sudoku(arr)):
                return True
 
            # failure, unmake & try again
            arr[row][col] = 0
             
    # this triggers backtracking       
    return False
 
# Driver main function to test above functions
if __name__=="__main__":
     
    # creating a 2D array for the grid
    grid =[[0 for x in range(9)]for y in range(9)]
     
    # assigning values to the grid
    grid =[[3, 0, 6, 5, 0, 8, 4, 0, 0],
          [5, 2, 0, 0, 0, 0, 0, 0, 0],
          [0, 8, 7, 0, 0, 0, 0, 3, 1],
          [0, 0, 3, 0, 1, 0, 0, 8, 0],
          [9, 0, 0, 8, 6, 3, 0, 0, 5],
          [0, 5, 0, 0, 9, 0, 6, 0, 0],
          [1, 3, 0, 0, 0, 0, 2, 5, 0],
          [0, 0, 0, 0, 0, 0, 0, 7, 4],
          [0, 0, 5, 2, 0, 6, 3, 0, 0]]
     
    # if success print the grid
    if(solve_sudoku(grid)):
        print_grid(grid)
    else:
        print "No solution exists"


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

Comments

Post a Comment

Popular posts from this blog

Facing the sun Java

PROGRAM TO FIND THE NUMBER OF BUILDINGS FACING THE SUN class Test {      // Returns count buildings that can see sunlight      static int countBuildings( int arr[], int n)      {          // Initialuze result  (Note that first building          // always sees sunlight)          int count = 1 ;                   // Start traversing element          int curr_max = arr[ 0 ];          for ( int i= 1 ; i<n; i++)          {              // If curr_element is maximum,              // update maximum and increment count              if (arr[i] > curr_max)              {                  count++;                  curr_max=arr[i];              }          }                   return count;      }              // Driver method      public static void main(String[] args)       {          int arr[] = { 7 , 4 , 8 , 2 , 9 };                      System.out.println(countBuildings(arr, arr.length));                  } } OUTPUT 3 CREDITS:  https://www.geeksforgeeks.org/number-buildings
Read more

Snake and Ladder Problem Python

PROGRAM TO SOLVE SNAKE AND LADDER PROBLEM class QueueEntry( object ):      def __init__( self , v = 0 , dist = 0 ):          self .v = v          self .dist = dist     '''This function returns minimum number of dice throws required to. Reach last cell  from 0'th cell in a snake and ladder game. move[] is an array of size N where N is  no. of cells on board. If there is no  snake or ladder from cell i, then move[i]  is -1. Otherwise move[i] contains cell to which snake or ladder at i takes to.''' def getMinDiceThrows(move, N):              # The graph has N vertices. Mark all      # the vertices as not visited      visited = [ False ] * N          # Create a queue for BFS      queue = []          # Mark the node 0 as visited and enqueue it      visited[ 0 ] = True          # Distance of 0't vertex is also 0      # Enqueue 0'th vertex      queue.append(QueueEntry( 0 , 0 ))          # Do a BFS starting from vertex at index 0      qe = QueueE
Read more

Add two numbers represented by linked lists Java

PROGRAM TO ADD TWO NUMBERS REPRESENTED BY LINKED LISTS class LinkedList {        static Node head1, head2;        static class Node {            int data;          Node next;            Node( int d)          {              data = d;              next = null ;          }      }        /* Adds contents of two linked lists and return the head node of resultant list */      Node addTwoLists(Node first, Node second)      {          // res is head node of the resultant list          Node res = null ;          Node prev = null ;          Node temp = null ;          int carry = 0 , sum;            // while both lists exist          while (first != null || second != null ) {              // Calculate value of next              // digit in resultant list.              // The next digit is sum              // of following things              // (i)  Carry              // (ii) Next digit of first              // list (if there is a next digit)              // (ii) Next digit of second    
Read more