DEV Community: Bartosz Raubo

sudoku solver - Some additions

Bartosz Raubo — Sun, 08 Aug 2021 19:58:12 +0000

August Additions

So, now that the sudoku algo is in place, it would be nice to make it usable. I want to add a couple of things:

Making it pretty - give the display of the puzzles some love
System for inputting sudokus you find online/in RL.
Ability to store puzzles (and solutions)
Ability to have a little demo mode
Diplay how long it took to find the solution.
and a menu system to tie it all together.

Making it pretty

First thing I touched - just a small function Sudoku.display_board() to print out the information in a visually pleasing manner based on an example I found through Google Image search.

def display_board(puzzle):
        print('\n')
        print('+-------+-------+-------+')
        for y in range(0, len(puzzle)):
            print(f'| {puzzle[y][0]} {puzzle[y][1]} {puzzle[y][2]} ' +
                    f'| {puzzle[y][3]} {puzzle[y][4]} {puzzle[y][5]} ' +
                    f'| {puzzle[y][6]} {puzzle[y][7]} {puzzle[y][8]} |')
            if y in [2, 5, 8]:
                print('+-------+-------+-------+')

The way the func is designed allows for partial boards to be printed - this was kind of accidental but helps with the feedback of information when inputting the board - see below.

Puzzle Input

So in an ideal world, I would just want to be able to take a picture of a sudoku, or screenshot, and have that be solved. But that is a little beyond me for now.

Instead, I used an input function that asks you to type in the puzzle row by row, with 0 representing missing values. It is not the most graceful solution perhaps, but it does allow me to quite easily feed in the input into the solution function.

def input_puzzle():
        puzzle = []
        input_msg = 'Input the known values.\nIf value is blank, input 0.\nEg. 530070000\n'
        while len(puzzle) < 9:
            valid = False
            while not valid:
                new_row = input(input_msg)
                puzzle.append(Sudoku.convert_row(new_row))
                valid = Sudoku.validate_row(new_row, puzzle)
                if not valid:
                    puzzle.pop()
                    print('Try Again\n\n')
        return puzzle

Convert_row turns the input into a list.

The one thing I regret is having to validate each row after it is typed. It is very annoying because most of the time I got the row right, and repeatedly validating got tedious. Then again, when a mistake is made, it mean not only having to start the puzzle again, but also having to complete input of any further rows. Which would be really shit. So its a judgement call between a small amount of constant annoyance or rare catastrophes. Hmmm.

You can't even press Enter several times... that will just register the row as incomplete. Perhaps it should recognise that if you're just tapping Enter, you've given up on the process.

[Rest later...]

Solving sudoku - notes from a tutorial

Bartosz Raubo — Sat, 17 Jul 2021 17:43:25 +0000

I have been working on a little Sudoku solver, mainly in order to familiarise myself with Atom and try to reinforce the testing-first approach.

Nothing fancy, just an implementation of a tutorial by ComputerPhile. Testing was made easier by the recursive function returns a value instead of logging the console output. The benefit of this is that it can therefore be incorporated into other code.

At the heart of the software lies a recursive algorithm, that I'm going to talk about to crystallise my thinking:

def next_value(puzzle):
    for y in range(0, 9):
        for x in range(0, 9):
            if puzzle[y][x] == 0:
                for n in range(1, 10):
                    if Sudoku.poss(puzzle, x, y, n):
                        puzzle[y][x] = n
                        if Sudoku.next_value(puzzle):
                            return puzzle
                        puzzle[y][x] = 0
                return
    return puzzle

What it does: goes through each list in the array and when it hits a zero, it replaces it with the first possible number (checked using the poss function).

Then next_value() calls itself, and so the process continues until it encounters a '0' with no possible solution - it then backtracks - returns through the layers of the function until it reaches a point where more than one value is possible, and proceeds as above with the next possible value.

This is where the code diverges from ComputerPhile's tutorial:

if Sudoku.next_value(puzzle):
    return puzzle

This passes up the answer from the last run of the recursive function to the allow the final return puzzle to provide us with a solution, rather than 'None'.

The poss function (that checks whether a number is allowed) is simple enough - it checks a input value against the rows and columns according to the rules of Sudoku. The more complicated aspect of these checks are the 3x3 squares. This is dealt with as follows (I take no credit for it - it is taken verbatim from ComputerPhile):

x_sq = (x//3)*3
y_sq = (y//3)*3
for a in range(0, 3):
    for b in range(0, 3):
        if puzzle[y_sq+a][x_sq+b] == n:
            return False

The // operator is Floor Division. It returns full values, so 3//3 == 1, but 2//3 == 0. This allows squares to be defined - the first three checks will all floor divide to 0, so script can check through all and only the values in the 3x3 square.

At some point it would be good to incorporate an easy way to input puzzles. There are also some tutorials for building a GUI to show the puzzle being solved (albeit much slower that the runtime of the function) - I hope to look into those.

The code is available here.

Scan.co.uk sales scraper

Bartosz Raubo — Sun, 27 Dec 2020 22:44:22 +0000

I was working today on a scraper that grabs the sale items from Scan.co.uk and collects the data in .csv file. Nothing fancy - its sole value is educational. And fittingly, the simple bs4 script threw up two issues that seem worth mentioning.

HTTP Error 403 - access to the server was not authorised, the html could not be grabbed. How frustrating!
x.findAll() does not return all result - I was trying to grab 6 'li' containers, but only 4 were ever found by the function. What do?

HTTP Error 403: Forbidden

This is related to urllib headers - the website does not want to be wrapped in in dealing with requests from countless scrapers, so requests headed urllib are blocked.

To get around this, you must obscure the fact you are running a scraping bot. The simplest way to do this is by using headers, as follows:

req = Request(my_url, headers={'User-Agent': 'Mozilla/5.0'})
page = urlopen(req)
page_html = page.read()
page.close()

At first, did this not work for me (It's User-Agent not User_Agent, bwap bwap).

So here's also another, apparently older solution, from user Zeta over on StackOverflow:

import urllib.request

class AppURLopener(urllib.request.FancyURLopener):
    version = "Mozilla/5.0"

uClient_opener = AppURLopener()
uClient = uClient_opener.open(my_url)

This appears to be a legacy solution, and not preferred. In the end, both solutions worked for me, typos aside.

x.findAll() does not return all results

product_list = product_categories[x].findAll('li')

The above code should have returned 6 results, but I could never get it to go above 4.

Some googling suggested that this was a problem with html_parser. Suggested solution - use html5lib.

This is what parsing the html with BeautifulSoup looked like before:

page_soup = soup(page_html, 'html_parser')
product_categories = page_soup.findAll('div', {'class':'category'})

The changes to the code are minimal - just replace the html_parser variable with html5lib:

import html5lib

page_soup = soup(page_html, 'html5lib')
product_categories = page_soup.findAll('div', {'class':'category'})

And it works! len(product_list) returns the correct 6 I was looking for.

Hope someone finds this helpful.