Wednesday, June 24

Sudoku programming: Advance reasoning

The preset() function in the previous blog is not powerful enough to solve many existing sudoku games, if any at all. After going back to study how my wife solve the games, and discussed with some sudoku hobbyists, a new reasoning logic is added into the program. It is the last version in https://github.com/BenLin0/sudoku as this blog is being written.

I added the new logic into the existing program as a standalone function SetPossibleNumbers(). If I refactor the code, some part of it can be combined into the previous preset() function, or the function name should be renamed better to reflect the true functionality of it.

In this new SetPossibleNumbers(), I took advantage of the dynamic typing of Python, to give a set of possible values for each empty (undecided) cell:

    for i in range(9):
        for j in range(9):
            if board[i][j] != 0 and type(board[i][j]) is int :
                continue
            board[i][j] = set()
            for trynum in [1, 2, 3, 4, 5, 6, 7, 8, 9]:
                if not conflict(board, i, j, trynum):
                    board[i][j].add(trynum)

With the support of knowing possible numbers of each cell, this reasoning logic is deployed:
If in one row there are 2 cells exclusively can only have 2 possible numbers, such as (3,6) in cell 1, and (3,6) in cell 2, then we know number 3 and number 6 can only be in these two cells, not in any other cells of the same row. Then I can remove these 2 numbers from the possible value of other cells.
Of course, the same column, the same block can apply the same rule too.

The number "2" in this reasoning rule can be change to any number n. For example, if in a row , cell 1 has possible values (6, 7, 8), cell 2 has possible values (6, 7), cell 3 has possible values (7, 8), then we know the number 6, 7, 8 are exclusively in these 3 cells, then they can't be in other cells.

The coding of this reasoning logic is not very pretty, so I will leave it in the github site. But with this new logic, most of the games I found can be resolved, before calling the brute-force backtracking function trysudoku(). 

I think I can add one more logic into the program shortly:
If in one block, all the possible cells for one specific number is in the same row, then the specific number must be in this 3 cells of this row: it can not be in other cells of the same row. 

It would be better to draw a sudoku to explain this logic. Let's leave it until it is implemented.

Now you just need to do it git clone:
git clone https://github.com/BenLin0/sudoku.git

then create a text file with the sudoku game you want to solve (use the samples in  test/ folder), and run the program:
python3 sudoku.py test/sudoku1.txt 

then you will see the reasoning steps (not very pretty) and the final result.


Have fun programming!

Sudoku programming: Adding logic into the already-logically-perfect program

As I already have a backtracking program that can perfectly solve any solvable sudoku, I am ready to add logic reasoning into it, after the board is loaded, before the backtracking trysudoku() function is called. Yes, as the last resort, the trysudoku() will be in action if the sudoku is not completely solved after the logic reasoning part is deployed.

The new function is called preset(). Apparently when I was writing this part, I only thought of it as a preprocess before running the main course trysudoku(). Anyway, in the second commit of the project, you can see this new present() function has these logic reasoning parts:

Part 1, walk though all empty cells to determine whether only one possible number suitable (not conflict with other elements). If there is only one possible number, then set this number. 

        count = 0
	for i in range(9):
        for j in range(9):
            if board[i][j] != 0:
                continue
            onlyonefit = false
            fitnum = 0
            for trynum in [1, 2, 3, 4, 5, 6, 7, 8, 9]:
                if not conflict(board, i, j, trynum):
                    if onlyonefit == false:
                        onlyonefit = true
                        fitnum = trynum
                    else:
                        onlyonefit = false
                        break   #jump out of trynum
            if onlyonefit == true:
                board[i][j] = fitnum
		count += 1


Yes this simple logic works for some sudoku games.  I should make this part as a function and call it repeatedly until there is no cell being set (count == 0). 

Part 2, for each row, loop thought number [1..9]. If the number already exists in this row, forget it; otherwise, count how many possible cells this number is possible to be set in. If there is only one cell this number can set in (in this row), then the number has to be set in this cell.


    for i in range(9):
        for trynum in [1, 2, 3, 4, 5, 6, 7, 8, 9]:
            possiblesitenum = 0
            possiblesite = 0
            Found = False
            for j in range(9):
                if type(board[i][j]) is int:
                    if board[i][j] == trynum:
                        Found = True
                        break   #found the number.
                else:   #is a set
                    if trynum in board[i][j]:
                        possiblesitenum += 1
                        possiblesite = j
            if Found == False and possiblesitenum == 1:
                logging.info("This num {} can only be in one site {} of this column {}".format(trynum, possiblesite, i))
                board[i][possiblesite] = trynum
                count += 1

After checking each row, do the same checking to each column, and each block.

Again, this is also simple logic: Each [1...9] number must show up in a row once, and only once. If there is only one cell available for a number for one row/column/block, then the number must be in this cell.

Aha, after reading the program again, I found I did call the preset() function (including the Part 1 and Part 2) repeatedly until there is no cell being set (count == 0). 

Done with this logic, I am able to commit this code, and get back to paper sudoku to learn more logic. To be continue.

Labels: ,

Sudoku programming: Classic Backtracking Problem

It was 2018, and the source code I mentioned in this post can be accessed in https://github.com/BenLin0/sudoku

That day my wife had problem with the sudoku game she was working on. So I said:" Let me make a program for you."

The first program was pretty simple, and you can get it from the commit history of the mentioned github: The first step is to design the input format of the sudoku file, such as:

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

(Original Sudoku game)


In theory, if you are building a modern phone app for sudoku, you would be using the camera to snap the picture of a paper-printed sudoku and get the input feed into the program, in the same way I just designed.

With this design, I can easily read the sudoku in to a 2D array, or a list of list, as saying in Python:


board=[]
def loadsudoku(filelocation):
    with open(filelocation, encoding="utf-8") as sudokufile:
            for line in sudokufile:
                if line.startswith("#"):
                    continue    #comment line
                if line.strip():
                    col = line.split(",")
                    column = [int(x.strip()) if x.strip() else 0 for x in col ]
                    board.append(column)

Now the board to the sudoku is ready, the next step is to try each number in each empty cell, using brute-force recursive function. 
def trysudoku(x, y):
    while board[x][y] != 0:
        x, y = getnext(x, y)
        if y == 9:
            return  1   # get to the 10th line, so this is the end!
    for trynum in [1, 2, 3, 4, 5, 6, 7, 8, 9]:   
        if conflict(board, x, y, trynum):
            continue
        board[x][y] = trynum
        nextx, nexty = getnext(x,y)
        if nexty == 9:
            return  1   #end!
        result = trysudoku(nextx, nexty)
        if result == 1:
            return 1
        else:
            board[x][y] = 0  # clean it, for the next trynum.
    return -1   #failed after trying all [1..9] number in this [x,y] position.

There are 2 support functions here: getnext() and conflict(). The getnext() is to get the next cell. We try to get the next cell in the same row; if we get to the end of the row, we will get the first cell of next row. The conflict() function is to test whether the new number is able to by apply to the current cell, whether it conflict with the known cells of the current row, current column, and column block.

So, this program is completed, when a new sudoku board is given, every number is tried in the cells from top left corner to bottom right corner brute-forcely. If a conflict is found for the current cell, we try a bigger number; if all [1..9] numbers are tried, we backtrack to previous cell to try another number. There are 2 possible results:
1, We successfully fill all the cells, now getnext() get to the 10th row ( y == 9 in the program). return 1.
2, We already backtrack to the first level, tried all the possible numbers [1...9] but failed. return -1.

Pretty classic backtracking algorithm. Mission complete


As I presented this program to my wife, and showed her how it worked, she disliked it. She said:"Any robot can do that. What I need is some logic thinking to support me when I am stuck in some steps." 

So I have to update my program to add some logic into the already-logically-perfect program. To be continue.

Sunday, June 7

这是什么垃圾?谈垃圾的分类

我不是要讨论去年在上海、今年在北京开始实施的垃圾分类。总体来说这两个地方的垃圾分类比传统的增加了堆肥垃圾和填埋垃圾的分类,搞得太严,反而碰到了阻力。我先说完分类再说这个吧。

垃圾这样分类:

1,有毒垃圾。生活中碰到的最主要的有毒垃圾是水银,包括传统体温计里的水银和荧光灯、节能灯的水银。一个朋友的节能灯打碎了,用吸尘器收拾碎片,吸尘器把水银吸进后经过滤网把水银蒸气喷出来,夫妻俩马上就中毒倒下了。这真是大意不得。换下来的节能灯、传统体温计请用塑料袋装上,密封好,交到专门的地方,比如卖出这些商品的商店应该有专门的垃圾桶接受这些有毒物品。

其次是药品。专指处方药。非处方药/中药没有什么太大的副作用,跟填埋垃圾一起埋下去处理,问题不大。处方药有各种各样的问题,所以如果不确定,要丢弃时还是交到医院里由专人处理。

然后,电池。历史上,所有电池都需要回收的,后来(1992年左右开始)一般的普通电池采用了安全材料,就不需要回收了,只有充电电池还采用有毒的材料,请用心处理、回收。普通电池若大量堆放在一起,反而容易着火燃烧,所以平时电池用废了,就直接丢到垃圾桶就好,不要积缵一大堆在抽屉,再扔到同一个垃圾桶中。
注:上面这个“普通电池随便扔”是全世界通用的,中国、美国都这样,除了美国加州。加州还在采用90年代旧的回收方式。你看着开心就好。


2,可回收垃圾。这个词在不同的地方有不同的含义。比如在商业场所,“可回收垃圾”垃圾桶大多只接受塑料瓶、可乐瓶等可以直接卖钱的物品;更广义一些,玻璃、塑料制品、纸盒等都可以回收,但是如果纸盒很脏,例如装了饭菜的纸盒,实际回收处理中是被丢弃的,所以你放到回收桶里,反而是平添了回收处理的工作量,而没有取得“回收”的好处。塑料制品,一般标有1、2、3、4、5的可以回收,而标6、7的,以及没有标记的,就只能直接填埋了:
Plastic resin codes

泡沫包装是不能回收的。现在网购很流行,快递行业用了很多泡沫,对环境不友好!



3,堆肥垃圾。国内也有叫“厨余垃圾”、“湿垃圾”,在上海实施时搞得很复杂,最开始时大家以为:

为之上海垃圾管理处还特地发文表示龙虾所有都算湿垃圾。
总而言之,只要是能腐烂的,能堆肥的,都是这类垃圾。或者说,“猪能吃的都是湿垃圾”。我所在的一个城市还曾经给全市人民每户发一个黑色的堆肥桶,让大家每天把这类厨余垃圾丢到桶里发酵堆肥,然后可以埋在后院当肥料。理想很美好,但是这东西很发臭,引来苍蝇嗡嗡嗡,我就一直没有去取回家。

上海垃圾分类执行中还有一个新词叫做“破袋”。这是一个动词,表示你用塑料袋装着湿垃圾拿到垃圾桶的时候,不能把整袋扔进湿垃圾桶里,要袋子里的湿垃圾倒进湿垃圾桶,然后把空塑料袋扔进干垃圾桶。这么一“破袋”,场面就不太好看了,先别说湿垃圾桶里的臭气,单是那油渍飞溅的破袋场面,就让上班出门顺手扔垃圾的穿着体面的白领退而却步。


4,其他垃圾。上海叫做“干垃圾”。总之,其他方式都处理完了,剩下的这些,或者填埋,或者焚烧。没有什么更好的办法。现在城市越来越大,快递越来越多,填埋场、焚烧炉总忙不过来。所以希望大家多使用可回收物品,少制造垃圾。




为了给后代一个更好的地球!

Labels: