Как написать судоку на питоне

base
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[4, 5, 6, 7, 8, 9, 1, 2, 3]
[7, 8, 9, 1, 2, 3, 4, 5, 6]
[2, 3, 4, 5, 6, 7, 8, 9, 1]
[5, 6, 7, 8, 9, 1, 2, 3, 4]
[8, 9, 1, 2, 3, 4, 5, 6, 7]
[3, 4, 5, 6, 7, 8, 9, 1, 2]
[6, 7, 8, 9, 1, 2, 3, 4, 5]
[9, 1, 2, 3, 4, 5, 6, 7, 8]

swap_colums_area
[7, 8, 9, 4, 5, 6, 1, 2, 3]
[1, 2, 3, 7, 8, 9, 4, 5, 6]
[4, 5, 6, 1, 2, 3, 7, 8, 9]
[8, 9, 1, 5, 6, 7, 2, 3, 4]
[2, 3, 4, 8, 9, 1, 5, 6, 7]
[5, 6, 7, 2, 3, 4, 8, 9, 1]
[9, 1, 2, 6, 7, 8, 3, 4, 5]
[3, 4, 5, 9, 1, 2, 6, 7, 8]
[6, 7, 8, 3, 4, 5, 9, 1, 2]

swap_colums_small
[7, 8, 9, 4, 5, 6, 2, 1, 3]
[1, 2, 3, 7, 8, 9, 5, 4, 6]
[4, 5, 6, 1, 2, 3, 8, 7, 9]
[8, 9, 1, 5, 6, 7, 3, 2, 4]
[2, 3, 4, 8, 9, 1, 6, 5, 7]
[5, 6, 7, 2, 3, 4, 9, 8, 1]
[9, 1, 2, 6, 7, 8, 4, 3, 5]
[3, 4, 5, 9, 1, 2, 7, 6, 8]
[6, 7, 8, 3, 4, 5, 1, 9, 2]

swap_colums_small
[7, 8, 9, 4, 5, 6, 1, 2, 3]
[1, 2, 3, 7, 8, 9, 4, 5, 6]
[4, 5, 6, 1, 2, 3, 7, 8, 9]
[8, 9, 1, 5, 6, 7, 2, 3, 4]
[2, 3, 4, 8, 9, 1, 5, 6, 7]
[5, 6, 7, 2, 3, 4, 8, 9, 1]
[9, 1, 2, 6, 7, 8, 3, 4, 5]
[3, 4, 5, 9, 1, 2, 6, 7, 8]
[6, 7, 8, 3, 4, 5, 9, 1, 2]

transposing
[7, 1, 4, 8, 2, 5, 9, 3, 6]
[8, 2, 5, 9, 3, 6, 1, 4, 7]
[9, 3, 6, 1, 4, 7, 2, 5, 8]
[4, 7, 1, 5, 8, 2, 6, 9, 3]
[5, 8, 2, 6, 9, 3, 7, 1, 4]
[6, 9, 3, 7, 1, 4, 8, 2, 5]
[1, 4, 7, 2, 5, 8, 3, 6, 9]
[2, 5, 8, 3, 6, 9, 4, 7, 1]
[3, 6, 9, 4, 7, 1, 5, 8, 2]

swap_colums_small
[7, 1, 4, 8, 2, 5, 6, 3, 9]
[8, 2, 5, 9, 3, 6, 7, 4, 1]
[9, 3, 6, 1, 4, 7, 8, 5, 2]
[4, 7, 1, 5, 8, 2, 3, 9, 6]
[5, 8, 2, 6, 9, 3, 4, 1, 7]
[6, 9, 3, 7, 1, 4, 5, 2, 8]
[1, 4, 7, 2, 5, 8, 9, 6, 3]
[2, 5, 8, 3, 6, 9, 1, 7, 4]
[3, 6, 9, 4, 7, 1, 2, 8, 5]

swap_rows_small
[7, 1, 4, 8, 2, 5, 6, 3, 9]
[8, 2, 5, 9, 3, 6, 7, 4, 1]
[9, 3, 6, 1, 4, 7, 8, 5, 2]
[5, 8, 2, 6, 9, 3, 4, 1, 7]
[4, 7, 1, 5, 8, 2, 3, 9, 6]
[6, 9, 3, 7, 1, 4, 5, 2, 8]
[1, 4, 7, 2, 5, 8, 9, 6, 3]
[2, 5, 8, 3, 6, 9, 1, 7, 4]
[3, 6, 9, 4, 7, 1, 2, 8, 5]

swap_rows_small
[7, 1, 4, 8, 2, 5, 6, 3, 9]
[8, 2, 5, 9, 3, 6, 7, 4, 1]
[9, 3, 6, 1, 4, 7, 8, 5, 2]
[5, 8, 2, 6, 9, 3, 4, 1, 7]
[4, 7, 1, 5, 8, 2, 3, 9, 6]
[6, 9, 3, 7, 1, 4, 5, 2, 8]
[2, 5, 8, 3, 6, 9, 1, 7, 4]
[1, 4, 7, 2, 5, 8, 9, 6, 3]
[3, 6, 9, 4, 7, 1, 2, 8, 5]

swap_rows_area
[7, 1, 4, 8, 2, 5, 6, 3, 9]
[8, 2, 5, 9, 3, 6, 7, 4, 1]
[9, 3, 6, 1, 4, 7, 8, 5, 2]
[2, 5, 8, 3, 6, 9, 1, 7, 4]
[1, 4, 7, 2, 5, 8, 9, 6, 3]
[3, 6, 9, 4, 7, 1, 2, 8, 5]
[5, 8, 2, 6, 9, 3, 4, 1, 7]
[4, 7, 1, 5, 8, 2, 3, 9, 6]
[6, 9, 3, 7, 1, 4, 5, 2, 8]

swap_colums_small
[7, 1, 4, 8, 2, 5, 6, 9, 3]
[8, 2, 5, 9, 3, 6, 7, 1, 4]
[9, 3, 6, 1, 4, 7, 8, 2, 5]
[2, 5, 8, 3, 6, 9, 1, 4, 7]
[1, 4, 7, 2, 5, 8, 9, 3, 6]
[3, 6, 9, 4, 7, 1, 2, 5, 8]
[5, 8, 2, 6, 9, 3, 4, 7, 1]
[4, 7, 1, 5, 8, 2, 3, 6, 9]
[6, 9, 3, 7, 1, 4, 5, 8, 2]

import pygame

pygame.font.init()

screen = pygame.display.set_mode((500, 600))

pygame.display.set_caption("SUDOKU SOLVER USING BACKTRACKING")

img = pygame.image.load('icon.png')

pygame.display.set_icon(img)

x = 0

y = 0

dif = 500 / 9

val = 0

grid =[

        [7, 8, 0, 4, 0, 0, 1, 2, 0],

        [6, 0, 0, 0, 7, 5, 0, 0, 9],

        [0, 0, 0, 6, 0, 1, 0, 7, 8],

        [0, 0, 7, 0, 4, 0, 2, 6, 0],

        [0, 0, 1, 0, 5, 0, 9, 3, 0],

        [9, 0, 4, 0, 6, 0, 0, 0, 5],

        [0, 7, 0, 3, 0, 0, 0, 1, 2],

        [1, 2, 0, 0, 0, 7, 4, 0, 0],

        [0, 4, 9, 2, 0, 6, 0, 0, 7]

    ]

font1 = pygame.font.SysFont("comicsans", 40)

font2 = pygame.font.SysFont("comicsans", 20)

def get_cord(pos):

    global x

    x = pos[0]//dif

    global y

    y = pos[1]//dif

def draw_box():

    for i in range(2):

        pygame.draw.line(screen, (255, 0, 0), (x * dif-3, (y + i)*dif), (x * dif + dif + 3, (y + i)*dif), 7)

        pygame.draw.line(screen, (255, 0, 0), ( (x + i)* dif, y * dif ), ((x + i) * dif, y * dif + dif), 7)  

def draw():

    for i in range (9):

        for j in range (9):

            if grid[i][j]!= 0:

                pygame.draw.rect(screen, (0, 153, 153), (i * dif, j * dif, dif + 1, dif + 1))

                text1 = font1.render(str(grid[i][j]), 1, (0, 0, 0))

                screen.blit(text1, (i * dif + 15, j * dif + 15))

    for i in range(10):

        if i % 3 == 0 :

            thick = 7

        else:

            thick = 1

        pygame.draw.line(screen, (0, 0, 0), (0, i * dif), (500, i * dif), thick)

        pygame.draw.line(screen, (0, 0, 0), (i * dif, 0), (i * dif, 500), thick)     

def draw_val(val):

    text1 = font1.render(str(val), 1, (0, 0, 0))

    screen.blit(text1, (x * dif + 15, y * dif + 15))   

def raise_error1():

    text1 = font1.render("WRONG !!!", 1, (0, 0, 0))

    screen.blit(text1, (20, 570)) 

def raise_error2():

    text1 = font1.render("Wrong !!! Not a valid Key", 1, (0, 0, 0))

    screen.blit(text1, (20, 570)) 

def valid(m, i, j, val):

    for it in range(9):

        if m[i][it]== val:

            return False

        if m[it][j]== val:

            return False

    it = i//3

    jt = j//3

    for i in range(it * 3, it * 3 + 3):

        for j in range (jt * 3, jt * 3 + 3):

            if m[i][j]== val:

                return False

    return True

def solve(grid, i, j):

    while grid[i][j]!= 0:

        if i<8:

            i+= 1

        elif i == 8 and j<8:

            i = 0

            j+= 1

        elif i == 8 and j == 8:

            return True

    pygame.event.pump()   

    for it in range(1, 10):

        if valid(grid, i, j, it)== True:

            grid[i][j]= it

            global x, y

            x = i

            y = j

            screen.fill((255, 255, 255))

            draw()

            draw_box()

            pygame.display.update()

            pygame.time.delay(20)

            if solve(grid, i, j)== 1:

                return True

            else:

                grid[i][j]= 0

            screen.fill((255, 255, 255))

            draw()

            draw_box()

            pygame.display.update()

            pygame.time.delay(50)   

    return False 

def instruction():

    text1 = font2.render("PRESS D TO RESET TO DEFAULT / R TO EMPTY", 1, (0, 0, 0))

    text2 = font2.render("ENTER VALUES AND PRESS ENTER TO VISUALIZE", 1, (0, 0, 0))

    screen.blit(text1, (20, 520))       

    screen.blit(text2, (20, 540))

def result():

    text1 = font1.render("FINISHED PRESS R or D", 1, (0, 0, 0))

    screen.blit(text1, (20, 570))   

run = True

flag1 = 0

flag2 = 0

rs = 0

error = 0

while run:

    screen.fill((255, 255, 255))

    for event in pygame.event.get():

        if event.type == pygame.QUIT:

            run = False 

        if event.type == pygame.MOUSEBUTTONDOWN:

            flag1 = 1

            pos = pygame.mouse.get_pos()

            get_cord(pos)

        if event.type == pygame.KEYDOWN:

            if event.key == pygame.K_LEFT:

                x-= 1

                flag1 = 1

            if event.key == pygame.K_RIGHT:

                x+= 1

                flag1 = 1

            if event.key == pygame.K_UP:

                y-= 1

                flag1 = 1

            if event.key == pygame.K_DOWN:

                y+= 1

                flag1 = 1   

            if event.key == pygame.K_1:

                val = 1

            if event.key == pygame.K_2:

                val = 2   

            if event.key == pygame.K_3:

                val = 3

            if event.key == pygame.K_4:

                val = 4

            if event.key == pygame.K_5:

                val = 5

            if event.key == pygame.K_6:

                val = 6

            if event.key == pygame.K_7:

                val = 7

            if event.key == pygame.K_8:

                val = 8

            if event.key == pygame.K_9:

                val = 9 

            if event.key == pygame.K_RETURN:

                flag2 = 1  

            if event.key == pygame.K_r:

                rs = 0

                error = 0

                flag2 = 0

                grid =[

                [0, 0, 0, 0, 0, 0, 0, 0, 0],

                [0, 0, 0, 0, 0, 0, 0, 0, 0],

                [0, 0, 0, 0, 0, 0, 0, 0, 0],

                [0, 0, 0, 0, 0, 0, 0, 0, 0],

                [0, 0, 0, 0, 0, 0, 0, 0, 0],

                [0, 0, 0, 0, 0, 0, 0, 0, 0],

                [0, 0, 0, 0, 0, 0, 0, 0, 0],

                [0, 0, 0, 0, 0, 0, 0, 0, 0],

                [0, 0, 0, 0, 0, 0, 0, 0, 0]

                ]

            if event.key == pygame.K_d:

                rs = 0

                error = 0

                flag2 = 0

                grid =[

                    [7, 8, 0, 4, 0, 0, 1, 2, 0],

                    [6, 0, 0, 0, 7, 5, 0, 0, 9],

                    [0, 0, 0, 6, 0, 1, 0, 7, 8],

                    [0, 0, 7, 0, 4, 0, 2, 6, 0],

                    [0, 0, 1, 0, 5, 0, 9, 3, 0],

                    [9, 0, 4, 0, 6, 0, 0, 0, 5],

                    [0, 7, 0, 3, 0, 0, 0, 1, 2],

                    [1, 2, 0, 0, 0, 7, 4, 0, 0],

                    [0, 4, 9, 2, 0, 6, 0, 0, 7]

                ]

    if flag2 == 1:

        if solve(grid, 0, 0)== False:

            error = 1

        else:

            rs = 1

        flag2 = 0   

    if val != 0:           

        draw_val(val)

        if valid(grid, int(x), int(y), val)== True:

            grid[int(x)][int(y)]= val

            flag1 = 0

        else:

            grid[int(x)][int(y)]= 0

            raise_error2()  

        val = 0   

    if error == 1:

        raise_error1() 

    if rs == 1:

        result()       

    draw() 

    if flag1 == 1:

        draw_box()      

    instruction()   

    pygame.display.update() 

pygame.quit()    

import pygame

pygame.font.init()

screen = pygame.display.set_mode((500, 600))

pygame.display.set_caption("SUDOKU SOLVER USING BACKTRACKING")

img = pygame.image.load('icon.png')

pygame.display.set_icon(img)

x = 0

y = 0

dif = 500 / 9

val = 0

grid =[

        [7, 8, 0, 4, 0, 0, 1, 2, 0],

        [6, 0, 0, 0, 7, 5, 0, 0, 9],

        [0, 0, 0, 6, 0, 1, 0, 7, 8],

        [0, 0, 7, 0, 4, 0, 2, 6, 0],

        [0, 0, 1, 0, 5, 0, 9, 3, 0],

        [9, 0, 4, 0, 6, 0, 0, 0, 5],

        [0, 7, 0, 3, 0, 0, 0, 1, 2],

        [1, 2, 0, 0, 0, 7, 4, 0, 0],

        [0, 4, 9, 2, 0, 6, 0, 0, 7]

    ]

font1 = pygame.font.SysFont("comicsans", 40)

font2 = pygame.font.SysFont("comicsans", 20)

def get_cord(pos):

    global x

    x = pos[0]//dif

    global y

    y = pos[1]//dif

def draw_box():

    for i in range(2):

        pygame.draw.line(screen, (255, 0, 0), (x * dif-3, (y + i)*dif), (x * dif + dif + 3, (y + i)*dif), 7)

        pygame.draw.line(screen, (255, 0, 0), ( (x + i)* dif, y * dif ), ((x + i) * dif, y * dif + dif), 7)  

def draw():

    for i in range (9):

        for j in range (9):

            if grid[i][j]!= 0:

                pygame.draw.rect(screen, (0, 153, 153), (i * dif, j * dif, dif + 1, dif + 1))

                text1 = font1.render(str(grid[i][j]), 1, (0, 0, 0))

                screen.blit(text1, (i * dif + 15, j * dif + 15))

    for i in range(10):

        if i % 3 == 0 :

            thick = 7

        else:

            thick = 1

        pygame.draw.line(screen, (0, 0, 0), (0, i * dif), (500, i * dif), thick)

        pygame.draw.line(screen, (0, 0, 0), (i * dif, 0), (i * dif, 500), thick)     

def draw_val(val):

    text1 = font1.render(str(val), 1, (0, 0, 0))

    screen.blit(text1, (x * dif + 15, y * dif + 15))   

def raise_error1():

    text1 = font1.render("WRONG !!!", 1, (0, 0, 0))

    screen.blit(text1, (20, 570)) 

def raise_error2():

    text1 = font1.render("Wrong !!! Not a valid Key", 1, (0, 0, 0))

    screen.blit(text1, (20, 570)) 

def valid(m, i, j, val):

    for it in range(9):

        if m[i][it]== val:

            return False

        if m[it][j]== val:

            return False

    it = i//3

    jt = j//3

    for i in range(it * 3, it * 3 + 3):

        for j in range (jt * 3, jt * 3 + 3):

            if m[i][j]== val:

                return False

    return True

def solve(grid, i, j):

    while grid[i][j]!= 0:

        if i<8:

            i+= 1

        elif i == 8 and j<8:

            i = 0

            j+= 1

        elif i == 8 and j == 8:

            return True

    pygame.event.pump()   

    for it in range(1, 10):

        if valid(grid, i, j, it)== True:

            grid[i][j]= it

            global x, y

            x = i

            y = j

            screen.fill((255, 255, 255))

            draw()

            draw_box()

            pygame.display.update()

            pygame.time.delay(20)

            if solve(grid, i, j)== 1:

                return True

            else:

                grid[i][j]= 0

            screen.fill((255, 255, 255))

            draw()

            draw_box()

            pygame.display.update()

            pygame.time.delay(50)   

    return False 

def instruction():

    text1 = font2.render("PRESS D TO RESET TO DEFAULT / R TO EMPTY", 1, (0, 0, 0))

    text2 = font2.render("ENTER VALUES AND PRESS ENTER TO VISUALIZE", 1, (0, 0, 0))

    screen.blit(text1, (20, 520))       

    screen.blit(text2, (20, 540))

def result():

    text1 = font1.render("FINISHED PRESS R or D", 1, (0, 0, 0))

    screen.blit(text1, (20, 570))   

run = True

flag1 = 0

flag2 = 0

rs = 0

error = 0

while run:

    screen.fill((255, 255, 255))

    for event in pygame.event.get():

        if event.type == pygame.QUIT:

            run = False 

        if event.type == pygame.MOUSEBUTTONDOWN:

            flag1 = 1

            pos = pygame.mouse.get_pos()

            get_cord(pos)

        if event.type == pygame.KEYDOWN:

            if event.key == pygame.K_LEFT:

                x-= 1

                flag1 = 1

            if event.key == pygame.K_RIGHT:

                x+= 1

                flag1 = 1

            if event.key == pygame.K_UP:

                y-= 1

                flag1 = 1

            if event.key == pygame.K_DOWN:

                y+= 1

                flag1 = 1   

            if event.key == pygame.K_1:

                val = 1

            if event.key == pygame.K_2:

                val = 2   

            if event.key == pygame.K_3:

                val = 3

            if event.key == pygame.K_4:

                val = 4

            if event.key == pygame.K_5:

                val = 5

            if event.key == pygame.K_6:

                val = 6

            if event.key == pygame.K_7:

                val = 7

            if event.key == pygame.K_8:

                val = 8

            if event.key == pygame.K_9:

                val = 9 

            if event.key == pygame.K_RETURN:

                flag2 = 1  

            if event.key == pygame.K_r:

                rs = 0

                error = 0

                flag2 = 0

                grid =[

                [0, 0, 0, 0, 0, 0, 0, 0, 0],

                [0, 0, 0, 0, 0, 0, 0, 0, 0],

                [0, 0, 0, 0, 0, 0, 0, 0, 0],

                [0, 0, 0, 0, 0, 0, 0, 0, 0],

                [0, 0, 0, 0, 0, 0, 0, 0, 0],

                [0, 0, 0, 0, 0, 0, 0, 0, 0],

                [0, 0, 0, 0, 0, 0, 0, 0, 0],

                [0, 0, 0, 0, 0, 0, 0, 0, 0],

                [0, 0, 0, 0, 0, 0, 0, 0, 0]

                ]

            if event.key == pygame.K_d:

                rs = 0

                error = 0

                flag2 = 0

                grid =[

                    [7, 8, 0, 4, 0, 0, 1, 2, 0],

                    [6, 0, 0, 0, 7, 5, 0, 0, 9],

                    [0, 0, 0, 6, 0, 1, 0, 7, 8],

                    [0, 0, 7, 0, 4, 0, 2, 6, 0],

                    [0, 0, 1, 0, 5, 0, 9, 3, 0],

                    [9, 0, 4, 0, 6, 0, 0, 0, 5],

                    [0, 7, 0, 3, 0, 0, 0, 1, 2],

                    [1, 2, 0, 0, 0, 7, 4, 0, 0],

                    [0, 4, 9, 2, 0, 6, 0, 0, 7]

                ]

    if flag2 == 1:

        if solve(grid, 0, 0)== False:

            error = 1

        else:

            rs = 1

        flag2 = 0   

    if val != 0:           

        draw_val(val)

        if valid(grid, int(x), int(y), val)== True:

            grid[int(x)][int(y)]= val

            flag1 = 0

        else:

            grid[int(x)][int(y)]= 0

            raise_error2()  

        val = 0   

    if error == 1:

        raise_error1() 

    if rs == 1:

        result()       

    draw() 

    if flag1 == 1:

        draw_box()      

    instruction()   

    pygame.display.update() 

pygame.quit()    

You can generate a random sudoku solution board where all numbers are filled in and then remove some of them to create the puzzle. This will ensure that the puzzle always has a solution. Making sure that it has exactly one solution is a bit more challenging (hint: you must leave at least 17 numbers for a 9×9 sudoku)

The algorithm below will generate a NxN random sudoku solution board instantly for N < 1000.

base  = 3
side  = base*base

# pattern for a baseline valid solution
def pattern(r,c): return (base*(r%base)+r//base+c)%side

# randomize rows, columns and numbers (of valid base pattern)
from random import sample
def shuffle(s): return sample(s,len(s)) 
rBase = range(base) 
rows  = [ g*base + r for g in shuffle(rBase) for r in shuffle(rBase) ] 
cols  = [ g*base + c for g in shuffle(rBase) for c in shuffle(rBase) ]
nums  = shuffle(range(1,base*base+1))

# produce board using randomized baseline pattern
board = [ [nums[pattern(r,c)] for c in cols] for r in rows ]

for line in board: print(line)

[6, 2, 5, 8, 4, 3, 7, 9, 1]
[7, 9, 1, 2, 6, 5, 4, 8, 3]
[4, 8, 3, 9, 7, 1, 6, 2, 5]
[8, 1, 4, 5, 9, 7, 2, 3, 6]
[2, 3, 6, 1, 8, 4, 9, 5, 7]
[9, 5, 7, 3, 2, 6, 8, 1, 4]
[5, 6, 9, 4, 3, 2, 1, 7, 8]
[3, 4, 2, 7, 1, 8, 5, 6, 9]
[1, 7, 8, 6, 5, 9, 3, 4, 2]

You can then remove some of the numbers from the sudoku solution to create the puzzle:

squares = side*side
empties = squares * 3//4
for p in sample(range(squares),empties):
    board[p//side][p%side] = 0

numSize = len(str(side))
for line in board:
    print(*(f"{n or '.':{numSize}} " for n in line))

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

For 4×4 up to 36×36 puzzles, you could make a nicer print of the board like this:

def expandLine(line):
    return line[0]+line[5:9].join([line[1:5]*(base-1)]*base)+line[9:13]
line0  = expandLine("╔═══╤═══╦═══╗")
line1  = expandLine("║ . │ . ║ . ║")
line2  = expandLine("╟───┼───╫───╢")
line3  = expandLine("╠═══╪═══╬═══╣")
line4  = expandLine("╚═══╧═══╩═══╝")

symbol = " 1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ"
nums   = [ [""]+[symbol[n] for n in row] for row in board ]
print(line0)
for r in range(1,side+1):
    print( "".join(n+s for n,s in zip(nums[r-1],line1.split("."))) )
    print([line2,line3,line4][(r%side==0)+(r%base==0)])

╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
║ 6 │   │   ║   │   │ 3 ║   │   │ 1 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │ 9 │   ║   │   │   ║   │   │ 3 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 4 │   │ 3 ║   │   │   ║ 6 │   │   ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║   │   │   ║ 5 │ 9 │   ║ 2 │   │ 6 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │   ║   │   │   ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │ 7 ║   │   │   ║   │   │ 4 ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║   │   │   ║   │   │   ║ 1 │ 7 │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │ 2 ║   │   │ 8 ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │ 8 ║   │   │   ║   │ 4 │ 2 ║
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝

[EDIT]

Here are some additional information on the shuffling process …

Shuffling rows is broken down in groups of 3 rows. It is ok to swap groups as a whole but we can’t swap rows across groups without breaking the integrity of the blocks. (the same reasoning applies to columns)

For example:

0 [6, 2, 5,  8, 4, 3,  7, 9, 1]                  -|
1 [7, 9, 1,  2, 6, 5,  4, 8, 3] |  group 0 -|     -| r in shuffle(rBase) 
2 [4, 8, 3,  9, 7, 1,  6, 2, 5] /           |     -|
                                            |
3 [8, 1, 4,  5, 9, 7,  2, 3, 6]            |     -|
4 [2, 3, 6,  1, 8, 4,  9, 5, 7] |  group 1 -| *   -| r in shuffle(rBase)
5 [9, 5, 7,  3, 2, 6,  8, 1, 4] /           |     -|
                                            |
6 [5, 6, 9,  4, 3, 2,  1, 7, 8]            |     -|
7 [3, 4, 2,  7, 1, 8,  5, 6, 9] |  group 2 -|     -| r in shuffle(rBase)
8 [1, 7, 8,  6, 5, 9,  3, 4, 2] /                 -|

                                * for g in shuffle(rBase)

We can swap groups 0,1,2 by moving all 3 of their rows at the same time:

3 [8, 1, 4,  5, 9, 7,  2, 3, 6]            |     -|
4 [2, 3, 6,  1, 8, 4,  9, 5, 7] |  group 1 -|     -| r in shuffle(rBase)
5 [9, 5, 7,  3, 2, 6,  8, 1, 4] /           |     -|
                                            |
6 [5, 6, 9,  4, 3, 2,  1, 7, 8]            |     -|
7 [3, 4, 2,  7, 1, 8,  5, 6, 9] |  group 2 -| *   -| r in shuffle(rBase)
8 [1, 7, 8,  6, 5, 9,  3, 4, 2] /                 -|
                                            |
0 [6, 2, 5,  8, 4, 3,  7, 9, 1]            |     -|
1 [7, 9, 1,  2, 6, 5,  4, 8, 3] |  group 0 -|     -| r in shuffle(rBase) 
2 [4, 8, 3,  9, 7, 1,  6, 2, 5] /           |     -|

                                * for g in shuffle(rBase)

And we can swap between the 3 rows of a group (e.g. 3,4,5) …

0 [6, 2, 5,  8, 4, 3,  7, 9, 1]                  -|
1 [7, 9, 1,  2, 6, 5,  4, 8, 3] |  group 0 -|     -| r in shuffle(rBase) 
2 [4, 8, 3,  9, 7, 1,  6, 2, 5] /           |     -|
                                            |
5 [9, 5, 7,  3, 2, 6,  8, 1, 4]            |     -|
4 [2, 3, 6,  1, 8, 4,  9, 5, 7] |  group 1 -| *   -| r in shuffle(rBase)
3 [8, 1, 4,  5, 9, 7,  2, 3, 6] /           |     -|
                                            |
6 [5, 6, 9,  4, 3, 2,  1, 7, 8]            |     -|
7 [3, 4, 2,  7, 1, 8,  5, 6, 9] |  group 2 -|     -| r in shuffle(rBase)
8 [1, 7, 8,  6, 5, 9,  3, 4, 2] /                 -|

                                * for g in shuffle(rBase)

We CANNOT swap rows across groups (e.g. 1 <—> 3):

0 [6, 2, 5,  8, 4, 3,  7, 9, 1]                  -|
3 [8, 1, 4,  5, 9, 7,  2, 3, 6] |  group 0 -|     -| r in shuffle(rBase) 
2 [4, 8, 3,  9, 7, 1,  6, 2, 5] /           |     -|
                                            |
1 [7, 9, 1,  2, 6, 5,  4, 8, 3]            |     -|
4 [2, 3, 6,  1, 8, 4,  9, 5, 7] |  group 1 -| *   -| r in shuffle(rBase)
5 [9, 5, 7,  3, 2, 6,  8, 1, 4] /           |     -|
                                            |
6 [5, 6, 9,  4, 3, 2,  1, 7, 8]            |     -|
7 [3, 4, 2,  7, 1, 8,  5, 6, 9] |  group 2 -|     -| r in shuffle(rBase)
8 [1, 7, 8,  6, 5, 9,  3, 4, 2] /                 -|

                                * for g in shuffle(rBase)

See the duplicate 8 in the top left block, duplicate 7 below that, etc.

Single solution puzzle

In order to generate a sudoku puzzle with only one solution you will need a solver function that can tell you if there are more than one solution. The strategy I would suggest is to start with 75% (or more) of the numbers removed, then check that there is only one solution. If there is more than one solution, put back a number and check again. You can put back a number at a random position or select a position where the solutions differ (which will converge faster to a single solution puzzle)

First write a solver that will generate all solutions that it finds (ideally as a generator because we only need the first 2). Here’s a simple one:

def shortSudokuSolve(board):
    size    = len(board)
    block   = int(size**0.5)
    board   = [n for row in board for n in row ]      
    span    = { (n,p): { (g,n)  for g in (n>0)*[p//size, size+p%size, 2*size+p%size//block+p//size//block*block] }
                for p in range(size*size) for n in range(size+1) }
    empties = [i for i,n in enumerate(board) if n==0 ]
    used    = set().union(*(span[n,p] for p,n in enumerate(board) if n))
    empty   = 0
    while empty>=0 and empty<len(empties):
        pos        = empties[empty]
        used      -= span[board[pos],pos]
        board[pos] = next((n for n in range(board[pos]+1,size+1) if not span[n,pos]&used),0)
        used      |= span[board[pos],pos]
        empty     += 1 if board[pos] else -1
        if empty == len(empties):
            solution = [board[r:r+size] for r in range(0,size*size,size)]
            yield solution
            empty -= 1

Starting with a solution variable with all numbers present and board variable containing the puzzle with 3/4 of numbers cleared, you can add numbers back to the board until there is only one way to solve it:

solution=[[9, 5, 3, 1, 6, 7, 4, 2, 8],
          [4, 2, 8, 3, 5, 9, 7, 6, 1],
          [7, 6, 1, 8, 2, 4, 9, 5, 3],
          [5, 8, 4, 9, 3, 6, 2, 1, 7],
          [6, 3, 9, 7, 1, 2, 5, 8, 4],
          [2, 1, 7, 4, 8, 5, 6, 3, 9],
          [3, 4, 5, 6, 9, 1, 8, 7, 2],
          [8, 7, 2, 5, 4, 3, 1, 9, 6],
          [1, 9, 6, 2, 7, 8, 3, 4, 5]]    
board=[ [0, 0, 0, 0, 0, 0, 0, 0, 8],
        [0, 2, 0, 0, 5, 0, 7, 6, 0],
        [0, 6, 0, 0, 0, 0, 0, 0, 3],
        [5, 0, 0, 0, 0, 0, 2, 0, 7],
        [0, 3, 0, 0, 1, 0, 0, 0, 0],
        [2, 0, 0, 4, 0, 0, 0, 3, 0],
        [0, 0, 0, 6, 0, 0, 0, 0, 0],
        [8, 0, 0, 0, 0, 0, 0, 0, 0],
        [1, 0, 0, 2, 7, 0, 0, 4, 0]]
    
import random
from itertools import islice
while True:
    solved  = [*islice(shortSudokuSolve(board),2)]
    if len(solved)==1:break
    diffPos = [(r,c) for r in range(9) for c in range(9)
               if solved[0][r][c] != solved[1][r][c] ] 
    r,c = random.choice(diffPos)
    board[r][c] = solution[r][c]

output:

╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
║   │   │   ║   │   │ 7 ║   │   │ 8 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │ 2 │   ║   │ 5 │   ║ 7 │ 6 │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │ 6 │   ║ 8 │   │ 4 ║   │   │ 3 ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║ 5 │   │   ║   │   │   ║ 2 │   │ 7 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │ 3 │   ║   │ 1 │   ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 2 │   │   ║ 4 │   │   ║   │ 3 │   ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║   │ 4 │   ║ 6 │   │   ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 8 │   │   ║   │   │   ║ 1 │   │ 6 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 1 │   │   ║ 2 │ 7 │   ║   │ 4 │   ║
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝

Note that this will work in a reasonable time for 9×9 sudoku boards but you will need a much better/faster solver function for larger boards

Also note that this will often produce «easy» puzzles as it will add in more numbers than absolutely necessary in some cases. Choosing the minimum set of numbers to add back-in would require a layered or backtracking approach which would be a bit more complex and much slower to run. Starting out with more empty spaces (e.g. 80% or more) will have a good chance of producing a more difficult puzzle within a reasonable timeframe.

Решатель судоку в Python — это упражнение или проект начального уровня для студентов колледжей. Написание кода для решения судоку с использованием языка Python делает его проще и проще.

Судоку — это логическая игра-головоломка, в которой игроки вставляют числа от одного до девяти в сетку с девятью квадратами, разделенными на девять меньших квадратов, так что каждое число встречается один раз в горизонтальной строке, вертикальной строке и квадрате. Эта игра довольно популярна среди любителей математики. Обычно судоку печатают в ежедневных газетах, а решение публикуют на следующий день.

В этой статье рассматривается написание кода на Python для решения головоломки судоку с использованием метода рекурсии. Сначала мы займемся графическим интерфейсом, а затем приступим к решению головоломки.

Создание решателя судоку с графическим интерфейсом с использованием языка Python

Мы будем создавать решатель судоку с графическим интерфейсом, используя IDE Jetbrains Pycharm . Поскольку мы создаем впечатляющее решение для судоку с графическим интерфейсом, мы импортируем библиотеку Tkinter. Давайте начнем:

Импорт библиотеки и написание кода

Импортируйте все из Tkinter и создайте экземпляр для окна Tkinter. Установите заголовок окна как «Решатель судоку». Теперь задайте размеры окна с помощью метода Geometry. Мы принимаем размеры окон как 324×550 пикселей.

Создайте метку, которая будет указывать на использование программы. Поместите метку в 0-ю строку и первый столбец, используя метод сетки. Установленный диапазон столбца, равный 10, центрирует метку в окне.

Теперь создайте еще одну метку, которая будет использоваться, если головоломка судоку не может быть решена, и инициализируйте ее пустой строкой. Цвет переднего плана для метки ошибки в нашем случае будет красным. Используйте метод Grid, чтобы поместить метку в 15-ю строку и 1-й столбец, диапазон столбцов до 10 и отступы до 5.

Создайте метку для успеха решения судоку. Вы можете скопировать код предыдущей метки, изменить цвет переднего плана на зеленый и назвать метку решенной.

Давайте создадим пустой словарь для хранения каждой ячейки входной сетки. Определите функцию проверки для управления вводом в ячейки. В качестве аргумента принимает значение ячейки.

Блок кода:

from tkinter import *
root = Tk()
root.title("Решатель судоку")
root.geometry("324x550")

label = Label(root, text="Заполните цифры и нажмите кнопку решить").grid(row=0, column=1, columnspa=1)

errLabel = Label(root, text="", fg="red") errLabel.grid(row=15, column=1, columnspan=10, pady=5)

solvedLabel = Label(root, text="", fg="green")
solvedLabel.grid(row=15, column=1, columnspan=10, pady=5)

Напишите функцию проверки

Напишите код для проверки значения, является ли оно цифрой или пустой строкой, позволяющей пользователям удалить значение. Чтобы ограничить ввод только одной цифрой и проверить, меньше ли значение 2, верните значение логического выражения.

Блок кода:

cells = {}
def ValidateNumber(P):
out = (P.isdigit() or P == "") and len(P) < 2
return out

Регистрация функции и написание другой функции для разделения судоку на сетки 3×3

Зарегистрируйте функцию в окне, используя метод корневой регистрации. Разделите сетку судоку 9 × 9 на более мелкие фрагменты 3 × 3, написав функцию. Это примет номер строки, номер столбца и цвет фона в качестве аргумента.

Используйте цикл for с диапазоном из трех, который будет указывать строки. Используйте другой цикл for внутри него, чтобы указать столбцы. Теперь создайте виджет ввода шириной 5, bg в качестве цвета фона, а по центру выровняйте текст с помощью Justify. Кроме того, подтвердите клавишу, чтобы подтвердить функцию при нажатии клавиши.

Подтвердите команду кортежем зарегистрированной функции и кода подстановки %P, который передаст новое значение в функцию при изменении. Поместите виджет на сумму номера строки как i+1 строку и сумму номера столбца как j+1. Вы можете установить прилипание к новому, что сделает его липким со всех сторон. Установите для padx и pady значение 1, а для внутреннего заполнения значение 5.

Теперь сохраните виджет записи в словаре с кортежем номеров строк и столбцов, которые мы использовали для размещения виджета в качестве ключа.

Блок кода:

reg = root.register(ValidateNumber)
defdraw3x3Grid(row, column, bgcolor):
for i in range(3):
forj in range(3):
e = Entry(root, width=5, bg=bgcolor, justify="center", validate="key", validatecommand=(reg,"%P"))

e.grid(row=row+i+1, column=column+j+1, sticky="nsew", padx=1, pady=1, ipady=5) 
cells[(row+i+1, column+j+1)] = e

Напишите функцию для рисования сетки 9 × 9

Мы напишем функцию для создания сетки 9×9. Мы использовали двухцветную комбинацию для этой сетки. Первый цвет означает значение. Используйте цикл for в диапазоне 1, 10 и размер шага 3 для строки №. Используйте другой цикл for внутри с диапазоном 0, 9 с размером шага 3.

Теперь вызовите функцию 3×3 и передайте номер строки, номер столбца и цвет. Чтобы чередовать цвета, используйте условие if. Если значением переменной цвета является первый цвет, мы установим его на второй цвет. В противном случае мы установим его на первый цвет. При написании цветовых кодов следите за регистром букв.

Блок кода:

def draw9x9Grid():
color = "#D0MT"
for rowNo in range(1, 10, 3):
for colNo in range(0, 9, 3):
draw3x3Grid(rowNo, colNo, color)
if color == "#Doffff":
color = "#ffffd0"
else:
color = "#Doffff"

Напишите функцию для очистки судоку

Мы напишем функцию очистки значений для судоку, которая очистит значения в каждой ячейке сетки. Во-первых, удалите ошибки и метки успеха. Опять же, повторите строки и столбцы. Диапазон для строки будет 2, 11, а диапазон для столбцов будет 1, 10.

Вызвать виджет записи, который мы сохранили в словаре, в данной строке и столбце. Используйте метод удаления виджета ввода, чтобы удалить его значение от индекса 0 до конца.

Блок кода:

defclearValues():
errLabel.configure(text="")
solvedLabel.configure(text="")
for row in range(2, 11):
for col in range(1, 10):
cell = cells[(row, col)]
cell.delete(0, "end")

Напишите функцию для получения ввода от пользователя

Напишите функцию получения значений и объявите пустой список для хранения значений для каждой ячейки для каждой строки. Снова очистите все метки, чтобы очистить текст, если он есть. Используйте цикл for для перебора диапазона 2, 11 для строк и 1, 10 для столбцов. Теперь получите значение ячеек, используя метод get виджетов ввода. Если значение представляет собой пустую строку, мы добавим 0 к списку строк. В противном случае добавьте в список целочисленное значение.

После окончания цикла добавьте список строк в список доски.

Блок кода:

defgetValues():
board = []
errLabel.configure(text="")
solvedLabel.configure(text="")
for row in range(2, 11):
rows = []
for col in range(1, 10):
val = cells[(row, col)].get()
if val = ""
rows. append(0)
else:
rows.append(int(val))
board.append(rows)

Написание кода для кнопок

Используя виджет кнопки, создайте кнопку. Установите команду для получения значений, текста для решения и ширины на 10. Теперь поместите кнопку в 20-ю строку и первый столбец с диапазоном столбцов 5, как 20.

Создайте еще одну кнопку, скопировав тот же код, установите ее команду на очистку значений и текст на очистку. Поместите эту кнопку в 5-й столбец.

Блок кода:

btn = Button(root, command=getValues, text="Solve", width=10)
btn.grid(row=20, column=1, columnspan=5, pady=20)

btn = Button(root, command=clearValues, text="Clear", width=10)
btn.grid(row=20, column=1, columnspan=5, pady=20)

Вызов функций

Вызовите функции сетки 9×9 и метод основного цикла root, чтобы запустить экземпляр нашего созданного окна.

draw9x9Grid()
root.mainloop()

Написание кода

Сначала мы объявим переменную, которая будет содержать количество строк и столбцов. Напишите вопрос, который будет проверять данное число для данной строки или столбца. Это примет судоку, номер строки, номер столбца и номер в качестве аргументов. Чтобы проверить, существует ли такое же число в той же строке, мы будем использовать цикл for в диапазоне 9. Условие цикла for выглядит следующим образом: если номер данной строки и i-го столбца равен num, мы вернемся ЛОЖЬ.

Точно так же мы проверим, существует ли такое же число в том же столбце. Используйте цикл for в диапазоне 9. Если номер данного столбца и j-й строки равен num, мы вернем false.

Теперь нам нужно проверить, существует ли такое же число в его конкретной сетке 3×3. Начальная строка будет строкой, вычтенной из модуля строки 3. Начальным столбцом будет столбец, вычтенный из модуля столбца 3.

Используйте два вложенных цикла в диапазоне от трех. Если число в начальной строке плюс i-я строка и начальный столбец плюс j-й столбец равны num, мы вернем False. В конце функции мы вернем True, которая будет выполнена, если ни одно из предыдущих условий не будет выполнено.

Блок кода:

N = 9

defisSafe(sudoku, row, col, num):
for i in range(9):
ifsudoku[row][i] - num:
return False

for i in range(9):
ifsudoku[i][col] == num:
return False

startRow = row - row % 3
startCol = col - col % 3
for i in range(3):
for j in range(3):
ifsudoku[startRow + i][startCol + j] =num:
return False
return Truc

Напишите функцию для присвоения значений не назначенным местоположениям

Мы напишем функцию решения судоку для присвоения значений не назначенным позициям. Это будет включать матрицу судоку, начальный номер строки и начальный номер столбца в качестве аргументов.

Давайте проверим, равна ли строка N-1, а столбец равен n. Если условие преобладает, мы вернем true. Это условие будет базовым, так как мы будем использовать рекурсию для решения головоломки. После того, как последний столбец будет достигнут, мы перейдем к следующему столбцу. Если столбец равен n, мы добавим единицу к строке и установим столбец обратно в ноль. Теперь мы проверим, присвоен ли номер текущему местоположению.

Если число в данной строке и столбце больше нуля, мы вернем функцию решения судоку для следующего столбца. Используйте цикл for в диапазоне 1, N+1 для проверки каждого числа от 1 до 9.

Теперь мы проверим, можно ли присвоить это число заданной строке и столбцу, используя функцию, которую мы написали ранее. Если можно присвоить номер, мы присвоим его в судоку. Допустим, присвоенный номер правильный. Мы также проверим возможность со следующей колонкой.

В блоке кода циклов мы переназначим 0, поскольку наше предположение было неверным, и оно подтверждает следующее значение. Верните false в конце блока кода функций.

Блок кода:

startCol = col - col % 3 
for i in range(3):
for j in range(3):
if sudoku[startRow + i][startCol + j] == num:
return False
return True



defsolveSudoku(sudoku, row, col):
ifrow== N - 1 and col == N:
return True

ifcol == N: 
row += l 
col = 0

ifsudoku[row][col] > 0:
return solveSudoku(sudoku, row, col + 1)

for num in range(1, N + 1):
if isSafe(sudoku, row, col, num):
sudoku[row][col] = num

if solveSudoku(sudoku, row, col + 1):
return True

sudoku[row][col] = 0
return False

Напишите функцию для решенной судоку

Мы напишем функцию, которая будет возвращать решенную судоку, если она разрешима. Это примет судоку в качестве аргумента. Чтобы узнать, разрешима ли судоку, используйте условие if. Мы вернем судоку, если это разрешимо. В противном случае мы вернем No.

Сохраните этот файл как Solver.py в той же папке, где вы сохранили файл GUI.

Блок кода:

det solver(sudoku):
if solveSudoku(sudoku, 0, 0):
return sudoku
else:
return "no"

Импорт функции решения в файл GUI

Откройте файл GUI и импортируйте функцию решения из файла Solver.py. Напишите функцию обновления значений, которая будет обновлять ячейки и отображать решение судоку. В качестве аргумента будет использоваться матрица судоку.

Вызовите функцию решения и передайте ей судоку. Если решение не равно NO, используйте цикл for в диапазоне 2, 11. Внутри цикла for используйте другой цикл for с диапазоном 1, 10. Удалите существующие значения из ячейки. Используйте метод вставки, чтобы вставить значение в 0-й индекс.

Значением будет число строк минус вторая строка и столбец минус первый столбец. Вычитаем 2 и 1 соответственно, так как матрица нулевая.

После того, как цикл установлен, текст решаемой метки для судоку решается с использованием метода конфигурации. В остальной части мы установим текст меток ошибок, чтобы решение не существовало.

from tkinter import * 
from solver import solve 
root = Tk() 
root.title("Решатель судоку") 
root.geometry("324x550")

Вызов значений обновления

Вызовите функцию получения значений в конце и передайте матрицу доски.

На данный момент наша окончательная программа готова к выполнению.

Вывод

Вы можете создать решатель судоку, используя метод рекурсии, как мы сделали здесь. Но разработка решателя судоку с графическим интерфейсом требует большего внимания к вашим навыкам кодирования и упрощает решение головоломок судоку.

Этот пост разделен на части для удобства сопровождения кода. Надеюсь, вам понравилось читать эту статью.